- [[Linked List Fast and Slow Pointers]] ### General - stores data in ordered manner like array, but is implemented using node objects - each node object will have a **next** pointer, which points to the node representing the next element in the sequence ![[CleanShot 2024-05-17 at 09.16.47.png]] ``` class ListNode: def __init__(self, val): self.val = val self.next = None one = ListNode(1) two = ListNode(2) three = ListNode(3) one.next = two two.next = three head = one print(head.val) print(head.next.val) print(head.next.next.val) ``` ### Pros & Cons vs Array - not relevant for algorithm problems cause choice is made for you, but for real life can consider - main advantage over array is that you can add and remove elements at any position in $O(1)$ - but you have to have a reference to the node at the position you want to do so - otherwise the operation is $O(n)$, cause you have to iterate from head to that point - but either way still much better than normal array, which requires $O(n)$ for adding & removing even from an arbitrary position - main disadvantage is that there is no random access, i.e to an element in between - dynamic arrays under the hood are still fixed sizes, but linked lists are truly dynamic size - but linked lists have more overhead than arrays ### Linked List Usage - traversing a linked list: ``` def get_sum(head): ans = 0 while head: ans += head.val head = head.next return ans ``` - adding a node at specific point i: ``` def add_node(prev_node, node_to_add): node_to_add.next = prev_node.next prev_node.next = node_to_add ``` - deleting a node at specific point i: ``` # Let prev_node be the node at position i - 1 def delete_node(prev_node): prev_node.next = prev_node.next.next ``` ### Types of Linked Lists - typically in interviews you will just a get a singly linked list, where each node only has a pointer to the next node (meaning you can only move forward) - Doubly Linked Lists are where each node also has a pointer to the previous node ``` class ListNode: def __init__(self, val): self.val = val self.next = None self.prev = None # Let node be the node at position i def add_node(node, node_to_add): prev_node = node.prev node_to_add.next = node node_to_add.prev = prev_node prev_node.next = node_to_add node.prev = node_to_add # Let node be the node at position i def delete_node(node): prev_node = node.prev next_node = node.next prev_node.next = next_node next_node.prev = prev_node ``` - Sentinel Nodes are when you keep pointers to a head and tail - is a doubly linked list with head and tail ``` class ListNode: def __init__(self, val): self.val = val self.next = None self.prev = None def add_to_end(node_to_add): node_to_add.next = tail node_to_add.prev = tail.prev tail.prev.next = node_to_add tail.prev = node_to_add def remove_from_end(): if head.next == tail: return node_to_remove = tail.prev node_to_remove.prev.next = tail tail.prev = node_to_remove.prev def add_to_start(node_to_add): node_to_add.prev = head node_to_add.next = head.next head.next.prev = node_to_add head.next = node_to_add def remove_from_start(): if head.next == tail: return node_to_remove = head.next node_to_remove.next.prev = head head.next = node_to_remove.next head = ListNode(None) tail = ListNode(None) head.next = tail tail.prev = head ```