Source

Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree

Linked List Recap

A linked list stores nodes in memory that is allocated dynamically. Each node has a data part (the value) and a next part (the address of the next node). A pointer called head points to the first node, and the last node points to None (null in C). The basic pros and cons are in Arrays and Linked Lists.

Insertion

To insert a new node after a given node p, only two pointers change and no element is shifted:

  • set the new node's next to p.next
  • set p.next to the new node

Deletion

To delete the node after p, link around it:

  • set p.next to p.next.next
  • the skipped node is no longer reachable from head

Python Sketch

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
 
def insert_after(p, val):
    temp = Node(val)
    temp.next = p.next       # new node points to the old successor
    p.next = temp            # p now points to the new node
 
def delete_after(p):
    if p.next is not None:
        p.next = p.next.next # bypass the deleted node

Cost

Once the position p is known, insertion and deletion take time, which is the main advantage over an array where elements must be shifted. Finding the position (or searching for a value) still needs a walk from head, which is , because there is no direct access by index.

Crash course tip: read whether a question asks for a singly or doubly linked list. A singly linked node has no .prev field, so to delete a node you must keep a pointer to the node before it while you walk.