Linked list basics

A linked list stores items in separate nodes scattered in memory. Each node holds a value and a reference (pointer) to the next node; the list itself is just a reference to the first node, the head. The last node points to null (None in Python).

In a singly linked list each node knows only its successor. In a doubly linked list each node also points to its predecessor, which lets you remove a node in O(1) when you hold a reference to it, and walk backwards. A circular list links the last node back to the first.

Compared with an array, a linked list gives up O(1) indexing and cache-friendly contiguous memory, and in return gets O(1) insertion and deletion once you are at the right node, with no shifting of other elements and no resizing.

1. 1Traverse: start with cur = head and repeat cur = cur.next until cur is None. Reaching position k takes k steps, so access is O(n).
2. 2Insert after a node: create the new node, point it at node.next first, then set node.next to the new node. Doing it in the other order loses the rest of the list.
3. 3Insert at the head: new.next = head, then head = new. O(1).
4. 4Delete the node after prev: prev.next = prev.next.next. To delete a node in a singly linked list you need its predecessor, which usually means walking from the head.
5. 5In a doubly linked list, delete node x in O(1): x.prev.next = x.next and x.next.prev = x.prev. Keeping a tail pointer also gives O(1) append.
6. 6Always check edge cases: head is None, the list has one node, and the change happens at the head or the tail.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def build(values):
    """Build a list from a Python list and return its head."""
    dummy = tail = ListNode()
    for v in values:
        tail.next = ListNode(v)
        tail = tail.next
    return dummy.next

def insert_after(node, val):
    node.next = ListNode(val, node.next)   # new node points at the old successor first

def delete_first(head, val):
    """Remove the first node holding val; return the (possibly new) head."""
    if head and head.val == val:
        return head.next
    cur = head
    while cur and cur.next:
        if cur.next.val == val:
            cur.next = cur.next.next          # unlink: skip over the node
            break
        cur = cur.next
    return head

build uses a dummy node so the first append is not a special case. insert_after sets the new node's next before relinking, so nothing is lost. delete_first handles the head separately, then looks one node ahead so it can rewire the predecessor. Insert is O(1) given the node; delete by value is O(n) because of the search.

Cost: Access or search O(n); insert or delete at a known node O(1) (singly needs the previous node, doubly does not); insert at head O(1); append O(1) with a tail pointer. Extra space is one or two pointers per element.