Arrays vs linked lists: when to use each

The physical difference

Contiguous values versus connected nodes

An array keeps elements next to one another, which makes indexed access fast and works well with CPU caches. A linked list stores separate nodes connected by references.

Linked nodes can live in different memory locations, so reaching the tenth node requires following the first nine links.

Complexity with context

Insertion cost depends on what you already know

Inserting near the start of an array shifts later elements. Inserting after a known linked-list node changes a few references. But finding that node may still require a linear traversal.

Linked lists also use extra memory for references and usually have poorer cache locality.

• Array index access: O(1)
• Linked-list index access: O(n)
• Array append: amortized O(1)
• Known-node linked insertion: O(1)

See the pointer change

Insert without losing the rest of the list

Save the old next reference before connecting the previous node to the new node. Drawing the links first prevents accidental disconnection.

class Node:
    def __init__(self, value, next_node=None):
        self.value = value
        self.next = next_node

def insert_after(node, value):
    node.next = Node(value, node.next)