What is the linked list data structure?

Table of contents

What is the linked list data structure?

A linked list is a data structure that stores a sequence of elements called nodes. Each node contains a value and may include a reference to the next node and/or previous node in the sequence.

A linked list can be singly or doubly linked list.

Nodes are containers that contain a value of type T and a reference to another node.

A node can be represented as:

// singly linked list
// where T is a generic type
type Node[T any] struct {
	value T
	next  *Node[T]
}

The first node is called head and the last node is called tail.

Unlike an array, a linked list does not use indexes to access elements. Instead, you have access to nodes, and you must traverse the list sequentially to reach the value you need.

// Doubly linked list:
type Node[T any] struct {
	value T
	next  *Node[T]
	prev *Node[T]
}

Operations in linked list

For each operation, we will consider both singly and doubly linked lists. Some operations might seem straightforward, but the implementation can be tricky as you have to take into account the references to either the next node or the previous node.

Retrieving values

To get a value from a linked list, we have to traverse the list to reach that value. If we want to get the value from the second node, we have to take two steps to reach the second node. This is true for both types of linked lists.

Inserting new values

Inserting a new value into a linked list can be broken down into two steps:

1. Traversing to the point of insertion - an O(n) operation
2. Performing the insertion process itself - our focus

Assuming we are at the point of insertion, we want to insert a new node that contains a value [H] in between two nodes, let’s say [B] and [C]. First we point [H].next (currently nil/undefined) to [C], which [B].next still points to. Then we point [B].next to [H]. In the other order, nothing would remember [C] once [B].next moves.

If our linked list is a doubly linked list, we also have to update the .prevs of all participating nodes.

These actions with the .nexts and .prevs are independent of the list size or size of the node or its value and thus is an O(1) operation.

Deletion of values

Deleting a node works the same way in reverse: point the node before it past it, so nothing in the list leads to it anymore. In a doubly linked list, the node after it also has to point back past it.