Linked Lists and Trees

linked list explained

Linked list explained: a linked list stores items as nodes, each holding data and a reference to the next node, so nodes can sit anywhere in memory. It trades fast indexing for cheap rewiring, and a tree extends it with several next pointers.

This essay is part of our programming essays. It follows one idea from a single chain of nodes to a branching tree, and it uses the same node shape and the same traversal logic throughout.

How a linked list is stored

A linked list is a sequence in which each node contains data and a reference to the next node, as Youcademy’s data structure guide describes it. The reference is a pointer: a value that says where the next node lives. A node does not need to sit next to its neighbour, because the pointer carries the location.

The marker is drawn with a dark tip, and the graph has tick marks along both axes.

Programiz uses a treasure hunt as an analogy: each clue includes the information about the next clue. You can only reach clue three by following clue two. Its C version of a node is a struct with a data item and a pointer to another struct node.

Head, tail and the end of the chain

The head node is the only node that no other node points to. The last node points to nothing, which is how code recognises the end of the list. When you loop over a list, you stop when the next reference is empty (null in many languages, None in Python).

Singly linked lists

In a singly linked list, each node points only to the next node, enabling forward traversal. That limit shapes everything below: you can walk forward from the head, but you cannot step backwards from a node you are holding.

Linked list vs array

Arrays and linked lists answer different needs. Arrays use contiguous memory locations, while linked list nodes can be stored in non-contiguous memory locations. With adjacent slots, an array can jump straight to any position. With scattered nodes, a linked list must follow the chain.

The bins are evenly spaced and placed in order along the shelf.

That difference explains the costs in the table. Dev.to’s comparison puts it plainly: array lookup is constant time, while the lookup of a value in a linked list is O(n) because it depends on the length.

Operation Linked list cost Planning use
Lookup by position O(n); an array does this in O(1) Pick an array when you index into the data often.
Search for a value O(n) in the worst case Expect to scan the chain from the head.
Traversal O(n), where n is the number of elements Visiting every node costs time in proportion to the list length.
Insert at head or tail O(1) Good for lists that grow at the ends.
Insert at a specific position O(n) in the worst case Finding the position dominates the cost, not the rewiring.
Delete at head O(1) Suits lists that are consumed from the front.
Delete at end or a specific position O(n) Budget for a walk before the delete.

Figures come from Youcademy and Dev.to.

When a linked list is the better choice

Choose a linked list when the data grows and shrinks at the ends and you rarely need the item at a given position. Dev.to notes that fixed-length arrays, as in some compiled languages, are sized in advance, while linked lists get allocated at runtime. A linked list therefore resizes naturally as nodes are added.

Choose an array when lookup by position matters, or when you will mostly read and loop over the data. Many languages also offer resizable arrays, which removes the fixed-size drawback for everyday use. Linked lists also appear inside other structures. Our essay on how do hash tables work shows one place where chains of nodes turn up.

Inserting and deleting nodes

Inserting a node means rewiring pointers, not moving data. Programiz describes the step as pointing the new node’s next pointer at the node that should follow it. The sequence for a singly linked list is:

  1. Create the new node. Give it its data and let its next reference start empty.
  2. Point it at the following node. The new node’s next now references the node that will come after it.
  3. Update the previous node. Its next pointer now references the new node, which completes the link.

Do the steps in this order. If you redirect the previous node first, you lose the only reference to the rest of the chain.

Deletion runs the same logic in reverse: the previous node’s next pointer skips over the node being removed. At the head, this is O(1) because there is no previous node to find. Deleting at the end or at a chosen position needs a walk to find the right neighbour, which is why those cases cost O(n).

One Node class for lists and trees

A tree is a linked list whose nodes carry more than one next pointer. The Programiz guide frames linked list practice as preparation to learn more advanced data structures like graphs and trees, and the node idea carries straight over. In Python, a list node holds an item and a next reference that starts as None:

Line numbers run down the left edge, and the code is blurred toward the edges of the frame.

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

Walking the list is a loop that follows next until it reaches None. The loop starts with node = head and repeats while node is not None, doing its work and then setting node = node.next.

From one next pointer to many

For a binary tree, replace the single next with a left and a right pointer. The root plays the role of the head, and a node with no children plays the role of the tail, with empty pointers marking the end of each branch. Insertion is the same rewiring as before. Lookup is still not by position: you follow pointers from the root. Because a node can point in more than one direction, a tree has more than one way to visit its nodes.

Traversing a tree: depth-first vs breadth-first

A linked list has only one traversal order, front to back. A tree has two common ones. Depth-first traversal follows one branch as far as it goes before backing up to try the next. Breadth-first traversal visits the nodes level by level, starting at the root and moving outward.

The two orders differ in the structure that holds the nodes waiting to be visited. Depth-first work is naturally handled with a stack or recursion, and breadth-first work with a queue. Programiz lists both stacks and queues as places where linked lists are implemented, so the same node-and-pointer machinery sits behind both orders.

Choose depth-first when you need to finish one branch completely before moving on. Choose breadth-first when nodes nearer the root matter first.

If you like thinking in terms of small composable pieces, the same node-and-reference idea shows up again in the practical introduction to functional programming.

Frequently asked questions

What other kinds of linked list exist?

A doubly linked list has nodes with addresses to both the previous and the next node, so you can walk in either direction. A circular linked list connects the first and last nodes, so the chain loops back on itself.

Why learn linked lists before trees?

A tree reuses the node-and-pointer idea with more pointers per node. Once you can follow and rewire the single next pointer of a list, a left and right pointer is a small step.

Where are linked lists used inside other structures?

According to Dev.to, hash tables, graphs, stacks, queues, and dequeues all utilize linked lists internally.