Linked List Field Notes

0Why linked lists exist

Both store items in order. The difference is where the items live in memory and how you find the next one.

1Singly linked list

The node: two things in a box

A ListNode is an object with exactly two fields. val holds the data. next holds a reference (also called a pointer): the memory address of another node. In Python, "no node" is written None. NeetCode's videos say null; it is the same idea.

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None     # a new node points nowhere

Building a chain by hand

Create three nodes, then set each next to the following node. Only the last node keeps next = None.

ListNode1 = ListNode("red")
ListNode2 = ListNode("blue")
ListNode3 = ListNode("green")

ListNode1.next = ListNode2    # red  → blue
ListNode2.next = ListNode3    # blue → green
ListNode3.next = None         # green is the end (already None, shown for clarity)

Traversal: walk the chain

Traverse means "visit every node from first to last". You cannot jump. You start at the head and follow next until you hit None.

cur = head            # cur = "the node I am standing on"
while cur:            # stops when cur becomes None
    print(cur.val)
    cur = cur.next    # step forward

Append at the tail: 2 lines

Because we keep a tail pointer, adding to the end does not need a walk. Two pointer changes, O(1).

ListNode4 = ListNode("yellow")
tail.next = ListNode4     # step 1: old last node now points to the new node
tail = ListNode4          # step 2: move the tail label to the new node

Delete a node: skip it

To delete a node you never "erase" it. You make the node before it point past it. Suppose we delete blue (the node after head):

head.next = head.next.next
# head.next      is blue
# head.next.next is green
# so: red now points to green; blue is skipped

Circular list: the infinite loop trap

If the last node's next points back to an earlier node, the list has no end. while cur: never sees None and runs forever.

Full class with head and tail

class SinglyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, val):
        node = ListNode(val)
        if self.tail:                # list has nodes
            self.tail.next = node
            self.tail = node
        else:                        # list is empty: head and tail are the same node
            self.head = self.tail = node

    def delete_after(self, node):
        # removes node.next (the node AFTER the one you hold)
        if node is None or node.next is None:
            return
        removed = node.next
        node.next = removed.next
        if removed is self.tail:      # deleted the last node? move tail back
            self.tail = node

    def to_list(self):
        out, cur = [], self.head
        while cur:
            out.append(cur.val)
            cur = cur.next
        return out

2Doubly linked list

Same as a singly linked list, plus one extra pointer per node: prev, which points to the previous node. Cost: a little more memory and one more pointer to update on every change. Benefit: you can walk backwards, and you can delete a node when you only hold that node (no need for the node before it).

class DNode:
    def __init__(self, val):
        self.val = val
        self.prev = None
        self.next = None

Insert at end: 3 lines, in order

ListNode4 = DNode(4)
tail.next = ListNode4      # ① old tail → new node
ListNode4.prev = tail      # ② new node ← old tail
tail = tail.next           # ③ move the tail label

Delete at end

Here prev pays off. In a singly linked list you cannot delete the tail in O(1) because you do not know the node before it. In a doubly linked list, tail.prev gives it to you instantly.

ListNode2 = tail.prev      # ① grab the node before the tail
ListNode2.next = None       # ② cut the forward arrow
tail = ListNode2           # ③ move the tail label back
# optional: old_tail.prev = None  (helps garbage collection, not required)

Front operations (the animations in the lesson)

Same idea, mirrored. Insert at front: new node's next is the old head, old head's prev is the new node, then move head. Delete at front: grab head.next, set its prev to None, move head.

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def insert_end(self, val):
        node = DNode(val)
        if self.tail:
            self.tail.next = node
            node.prev = self.tail
            self.tail = node
        else:
            self.head = self.tail = node

    def insert_front(self, val):
        node = DNode(val)
        if self.head:
            node.next = self.head
            self.head.prev = node
            self.head = node
        else:
            self.head = self.tail = node

    def delete_end(self):
        if not self.tail:
            return None
        val = self.tail.val
        if self.tail is self.head:        # only one node → list becomes empty
            self.head = self.tail = None
        else:
            before = self.tail.prev
            before.next = None
            self.tail = before
        return val

    def delete_front(self):
        if not self.head:
            return None
        val = self.head.val
        if self.head is self.tail:
            self.head = self.tail = None
        else:
            after = self.head.next
            after.prev = None
            self.head = after
        return val

3Queue

A queue is not a new structure; it is a linked list with two rules. Add only at the back (enqueue). Remove only from the front (dequeue). NeetCode names the two ends left (front) and right (back). Compare with a stack, which is LIFO: last in, first out.

The full queue, with the empty-list cases handled

class Queue:
    def __init__(self):
        self.left = None     # front: dequeue here
        self.right = None    # back:  enqueue here

    def enqueue(self, val):
        newNode = ListNode(val)
        if self.right:                   # queue is non-empty
            self.right.next = newNode
            self.right = self.right.next
        else:                            # queue is empty
            self.left = self.right = newNode

    def dequeue(self):
        if not self.left:                # queue is empty: nothing to return
            return None
        val = self.left.val
        self.left = self.left.next
        if not self.left:                # we just removed the last node
            self.right = None            # right must not point at a dead node
        return val

In real Python code

Do not build a queue from scratch in an interview unless asked. Use collections.deque. A deque ("deck", double-ended queue) supports O(1) add and remove at both ends.

from collections import deque

q = deque()
q.append(1)        # enqueue at the back
q.append(2)
q.popleft()        # dequeue from the front → 1
q.appendleft(0)    # also allowed: add at front
q.pop()            # also allowed: remove from back

# NEVER do this for a queue:
lst = [1, 2, 3]
lst.pop(0)         # O(n): every element shifts left

Where you will use a queue next: breadth-first search (BFS) on trees and graphs. BFS is "visit everything 1 step away, then everything 2 steps away". A queue keeps that order for you. Trees are the next big topic in the course.

4Three moves that solve most linked list problems

The lessons teach the structure. Interviews test these three moves on top of it. Learn them as muscle memory.

Move 1: Reverse with prev / cur / nxt

Walk the list once. At each node, save where you are going, flip the arrow to point backwards, then move both markers forward.

def reverse_list(head):
    prev, cur = None, head
    while cur:
        nxt = cur.next      # 1. save next  (or you lose the rest of the list)
        cur.next = prev     # 2. flip the arrow
        prev = cur          # 3. move prev forward
        cur = nxt           # 4. move cur forward
    return prev             # prev is the new head

Move 2: Dummy node

Deleting the head is a special case because nothing points to it. Fix: put a fake node in front so every real node has a node before it. Return dummy.next at the end.

def remove_value(head, target):
    dummy = ListNode(0)
    dummy.next = head
    cur = dummy                        # cur always stands BEFORE the node we inspect
    while cur.next:
        if cur.next.val == target:
            cur.next = cur.next.next   # skip it (same trick as section 1)
        else:
            cur = cur.next
    return dummy.next                  # the real head, even if the old head was removed

Move 3: Slow and fast pointers

Two walkers. Slow moves 1 step, fast moves 2. When fast hits the end, slow is at the middle. If the list has a cycle, fast laps slow and they meet.

def middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

5Big-O summary

Say these out loud in interviews. The star always means: "if I already hold a reference to the node at that spot".

Why singly delete-at-end is O(n): you need the node before the tail, and a singly list gives you no way to go back. You must walk from the head. Python list's O(1)* at end is "amortized": occasionally it copies to a bigger array.

6Mistakes to watch for

7Practice, in this order

Notes do not make you good at this. Solving does. Do these on LeetCode with no notes open, then check against the templates above.

Your next step today: LeetCode 206. Write it from memory, run it, then read the reverse diagram again and compare.

8Self-check

Answer out loud before opening. If you cannot answer in one breath, reread that section.