Linked Lists

A linked list is an array-like data structure. In a linked list, we can go from one element to the next in similar fashion; however, data is not stored contiguously in RAM. Linked lists are made up of objects known as ListNodes. ListNodes have two attributes: the value and a pointer to the next ListNode.

Figure 1

class ListNode:
    def __init__(self, val):
        # value
        self.val = val
        # pointer
        self.next = None

Like the name implies, a linked list will “link” multiple ListNode objects together.

Figure 2

We can link ListNodes together by setting the pointer value to the next ListNode:

ListNode1.next = ListNode2

Setting the pointer to null will indicate the end of a linked list.

ListNode2.next = ListNode3
ListNode3.next = null

We can traverse a linkedlist easily:

cur = ListNode1
while curr:
    cur = cur.next

All linked lists have a head and a tail pointer. The head points to the beginning and the tail points to the last ListNode object. With static arrays, appending is O(n) time since there is no shifting required. Linked lists are better in this regard — adding new elements is an O(1) time operation (assuming we already have the reference for where to insert). Let’s suppose our linked list only had one node to start:

Figure 3

We would set a pointer to the new node object with tail.next = ListNode4

Figure 4

Now the pointer is pointing to the new list node. Notice how the tail is not updated. Let’s do that now: tail.next = ListNode4

Figure 5

Moving on to deleting ListNode objects. Let’s say we wanted to delete ListNode2.

Figure 6

We can achieve this by updating our head.next. We can chain these commands to move the pointer.

head.next = head.next.next

Figure 7

Doubly Linked Lists build on that and utilize two pointers instead of one. We now have a previous pointer so we can track things in reverse easily:

Figure 8

Adding a new node to the end is similar. The difference is that we need to have our new node point to the previous node as well this time.

# Inserting a third node
tail.next = ListNode3
ListNode3.prev = tail
tail = tail.next

# Deleting third node
ListNode2 = tail.prev
ListNode2.next = null
tail = ListNode2