Introduction

Similarly to an array, a linked list is a linear sequence of elements. The order of elements in an array is given by their position in a contiguous memory block. Contrastingly, the order of elements in a linked list is maintained by each element holding a reference to the next (see figure 1).

A linked list itself is a simple structure. It holds only a reference to the head; the first element in the linked list.

1
2
3
4
5
6
7
8

type Node struct {
	value int //for simplicity use an int for the data
	next  *Node //reference to the next element in the linked list
}

type LinkedList struct {
	head *Node //first element in the linked list
}

Common use cases include the implementation of stacks and queues, or to handle collisions in a hash table.

Advantages & Disadvantages

Advantages

• Inserting or deleting from the beginning of a linked list is very efficient and has a time complexing of O(1) (or constant time). The same implies if we already have a reference to the element we want to insert after.
• It is a dynamic data structure and can be resized at runtime, unlike an array which is given a fixed sized.
• Due to its dynamic nature, no memory is wasted by reserving memory.

Disadvantages

• More memory is required for each element compared to an array, as each requires a pointer to the next to be stored alongside its data.
• Accessing a node at a given index has a time complexity of O(n) (or linear time), as we have to traverse the list to find it. Random access is not possible because data is not stored in contiguous memory.
• Traversing a list in reverse is not possible unless a doubly-linked list is used, which requires further memory.

Operations

Prepending

Prepending is a simple operation involving adding a new element to the head of the linked list. To prepend a new element, we give its pointer a reference to the element at the head. The head’s pointer is then updated to reference the the new element (see figure 2).

Code example:

1
2
3
4
5

func (l *LinkedList) Prepend(value int) {
	newNode := &Node{value: value} //create a new node
	newNode.next = l.head //point the new node to the node at the head
	l.head = newNode //set the linked list's head to the new node
}

Prepending is inexpensive and has a time complexing of O(1). This compares to O(n) time complexity for the same operation on an array, where n is the array length. This is because an array has to shift the existing elements to make room for the new one.

Inserting After a Node

Given a reference to an existing element in a linked list, inserting a new value involves a similar procedure to prepending (see figure 3). The pointer of the new element is given a reference to the node positioned after the target node. The target node’s pointer is then given a reference to the new node.

Code example:

1
2
3
4
5
6
7
8

func (l *LinkedList) InsertAfter(node *Node, value int) {
	//do not operate if node given is null
	if node != nil {
		newNode := &Node{value: value} //create the new node
		newNode.next = node.next //point the new node to the node after the target node
		node.next = newNode //point the target node to the new node
	}
}

As we already have a reference to the the node we want to insert after, this operation also has a time complexity of O(1). Again, a similar operation on an array would have O(n) time complexity, where n is the number of elements after the insert position.

Appending

Appending to a linked list is conceptually simple; it involves pointing the last element to the new one (see figure 4). To do this we must traverse the linked list until we find an element with a null pointer (the last element), before pointing it to the new element.

Code example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func (l *LinkedList) Append(value int) {
	newNode := &Node{value: value} //create the new node
	//if the linked list is empty, make the new node the head
	if l.head == nil {
		l.head = newNode
		return
	}
	//otherwise, find the last element by traversing nodes
	//until we find one that has a null pointer
	node := l.head
	for node.next != nil {
		node = node.next
	}
	//point the last node to the new one
	node.next = newNode
}

Appending is less efficient than prepending or inserting after particular node, because we have to traverse the entire linked list. This means the time complexity is O(n), where n is the length of the linked list.

Deleting the Head

Deleting the head simply involves changing the node referenced at the head to the next one in the sequence (see figure 5).

Code example:

1
2
3
4
5
6

func (l *LinkedList) DeleteHead() {
	//if there is a head, update it to be the next element
	if l.head != nil {
		l.head = l.head.next
	}
}

Like prepending, removing an element from the head is very efficient and has a time complexity of O(1). The same operation on an array involves shifting the elements positioned after the one being removed. This gives a time complexity of O(n), where n is the number of elements to be shifted.

Deleting a Value

Deleting a value involves traversing the linked list. On each iteration, we check if the value of the next element is the one we want to delete. When the value is encountered, the pointer of the current element is updated to reference the element after the next (see figure 6).

Code example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

func (l *LinkedList) Delete(value int) {
	//if the linked list is empty, do nothing
	if l.head == nil {
		return
	}

	//if the head contains the value,
	//make the head the next element
	if l.head.value == value {
		l.head = l.head.next
		return
	}

	//iterate over the elements until we find an element whose 
	//next sibling contains the value to delete
	node := l.head
	for node != nil && node.next.value != value {
		node = node.next
	}

	//if we have found such a node, point it to the node after the next
	if node != nil {
		node.next = node.next.next
	}

}

The time complexity of deleting a value is O(n), where n is the number of elements we have to traverse.

Accessing by Index

To access an element by its index, we traverse through the elements using their pointers, tracking the number of elements visited until we reach the desired index (see figure 7).

In the below the example, the number of elements visited is tracked by decrementing the requested index.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func (l *LinkedList) NthNode(i int) *Node {
	//don't accept negative numbers
	if i < 0 {
		return nil
	}
	//iterate over the elements, decrementing the index (i)
	//until there are no more nodes or the index is 0
	node := l.head
	for i > 0 && node != nil {
		node = node.next
		i--
	}
	//the node returned will be from the desired index or null
	return node
}

The time complexity for this operation is O(n), where n is the number of elements to traverse. This is this is less efficient than the same operation on an array, which has a time complexity of O(1). Because an array is stored in contiguous memory, any index can be accessed quickly by using an offset from the location of the first element.

Finding a Value

To find a value, the linked list is traversed via the pointers until we reach the node that contains the desired value and return it (see figure 8).

Code example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

func (l *LinkedList) Find(value int) *Node {
	//iterate over the list until there are no more nodes
	//or we find the value we are looking for
	node := l.head
	for node != nil && node.value != value {
		node = node.next
	}
	//return the node containing the value or null
	return node
}

Like with an array, this operation has O(n) time complexity. With both structures, elements have to be traversed until the desired value is found.

Summary

A linked list has an advantage over similar data structures for operations such as inserting and deleting. This can be useful for implementing such things as stacks and queues. Its disadvantages include that it is inefficient to access elements by index and that it requires more memory.

Some key operations were discussed and examples were given for how to implement them. The full code example can be found on Github.