Linked List Data Structure

Linked list is one of many data structures in computer science having close relations to Arrays (Lists), I would be using arrays and list interchangeably throughout this article. It tends to solve one major drawbacks of Array data structure which is having the content of the list contiguous in memory, This means that if you have an array of integers, for example, the memory addresses for these integers will be sequential. This contiguous structures is essential in arrays to allow for efficient access to elements through index calculations and facilitates better cache utilisation. 

This is all fine and good but imaging we don't know how many blocks on memory to allocate to the particular list (for dynamic lists), it's difficult for the Operating System to efficiently manage memory. Some programing languages tends to solve this in their own way, for instance in Javascript as the list grows is the next block of memory is not available for the next item, it moves the entire list to a different part of memory for it to be contiguous in a process known as dynamic resizing.

Linked list comes to the rescue in the sense that element of the list don't have to be contiguous in memory, they can be anywhere which makes it more efficient in memory. Each items of the list (Node) has a pointer to the next element on the list or null of there is no more element on the list.

1.1 Creating a Linked List

In the basic form, a linked list is just a collection of Nodes with two pointers, one pointing to the head and another pointing to the tail on the list. A Node is a single item in a list, a node itself contains a value and a pointer to the next node on the list

A simple Representation of a linked list as you can see from the diagram above, each node has a pointer to the next node or null if no next node exist and the Linked List keeps track of the head and tail at all points. 

Linked List Under the Hood

1.2 Creating a Node

To create a linked list class we first have to create a node, since a linked list is just a collection of nodes. I would be using Javascript for the purpose of this demonstration

Class Node {
  constructor(value){
    this.value = value //current value of the node
    this.next = null  // pointer to the next node or null
  }
}

Next we create the Linked list class

Class LinkedList {
  constructor(value){
    this.head = new Node(value)
    this.tail = this.head
    this.length = 1
  }
}

Like I said earlier, the linked list keeps track of the head, tail and the length of the list, at the point of initialisation a new node is created and assigned to both the head and the tail since at this point the list has only one item which is both the head and the tail.

const newList = new LinkedList(4) //creates a link with a value of 4

Time complexity of various methods in a linked list versus arraysNext we implement the various operation that happens on the list, these operations are shown in the diagram below as well as their time complexity

2.3 Operations on a linked list

a)Push:
This is adds a node to the end of the list. The sequence of operations that happens are as follows

1. A new node is created
2. If the list is empty, point both the head and the tail to the new node created. End.
3. point the next value on the tail (since its the last item) to the new node
4. reassign the tail value to the new node
5. increase the length
6. End

push(value){
  const newNode = new Node(value)
  if(!this.head){
    this.head = newNode
    this.tail = newNode
    this.length++
  }else{
    this.tail.next = newNode
    this.tail = newNode
    this.length++
  }
}

b) Pop:

This is a little more complicated that the push method and a few more edge cases to look at. The Pop method removes an item from the end of the list, the sequence of operations are as follows. 

1. if the list is empty, do nothing
2. if only one item is in the list set the head and tail to null
3. move the tail to the previous item in the list
4. set the next property of the tail to null
5. decrement the length
6. End

This is an O(n) operation since we need to iterate over the entire list to get the previous element from the tail

pop(){
  if(!this.head) return undefined
  if(this.length == 1) {
    const temp = this.head
    this.head = null
    this.tail = null
    this.length--
    return temp
  }
  let prevNode = null
  let currentNode = this.head
  while(currentNode.next){
    const temp = currentNode.next
    prevNode = currentNode
    currentNode = temp
  }
  this.tail = prevNode
  this.tail.next = null
  this.length--

  return currentNode
}

b) Unshift:
This adds a new node to the beginning of the list, the sequence of operations are as follows

1. create a new node
2. if the list is empty, point the head and tail to the new node created and increment the length. End.
3. make the next value of the new node created point to the head of the list
4. move the head pointer over to the new node created
5. increment the length
6. End

unshift(value){
 const newNode = new Node(value)
  if(!this.head){
    this.head = newNode
    this.tail = newNode
  }else{
    newNode.next = this.head
    this.head = newNode
  }
  this.length++
}

d) Shift:
The shift operation removes an item from the beginning of a list. The edge cases here are similar to the pop operations, the shift method has the following sequence of operations are as follows

1. if the list is empty return undefined
2. if only one items is present set the head and tail to null and set the length 0
3. set the head pointer the the next value in the list
4. decrement the length
5. End

shift(){
  if(!this.head) return undefined
  const temp = this.head
  if(this.length == 1) {
    this.head = null
    this.tail = null
  }else{
    this.head = this.head.next
  }
    this.length--
    temp.next = null
    return temp
}

e) Get :
The get method is used to return an item at a given index, it takes and index and return a value. Here unlike arrays this operation is an O(n) operation because we have to iterate over the entire list up until the given index in other to get the value at that index. Here are the sequence of operation and the edge case to look out for

1. if given index is less than 0 or greater than the length of the list, return undefined
2. iterate over the list from the head (first item or index 0) up until the given index (i)
3. return the value at that index
4. End

get(index){
  if(index < 0 || index >= this.length) return undefined
  if(index == 0) return this.head
  let currentNode = this.head
  for(let i = 0; i < index; i++){
    currentNode = currentNode.next
  }
  return currentNode
}

f) Set :
The Set method is very similar to the Get method the only difference her is that instead of just getting the value at the given index, we want to change the value at that index. The index here to set must be within the range of the list and since its very similar to the Get method, we are going to reuse that method

1. get the node at the index
2. change the value of that node to the given value
3. increment the length
4. End

set(index, value){
  const node = this.get(index) // reusing the get method defined above
  if(node){
    node.value = value
    this.length++
    return true
  }
  return false
}

g) Insert:
The insert method enters a new value to a given index in the list, unlike the Set method this inserts a new node to the list and does not modify the value of existing nodes in the list. As usual, we handle the edge cases first and the operations are as follows

1. if index is equal to zero (0), reset the head pointer to the new node and the next value of the new node to the previous head (similar to the unshift method). End
2. if the index is outside the bounds of the list, return undefined
3. iterate over the list up until the given index, keeping track of the previous node and the current node
4. set the next value of the previous node to the new node
5. set the next value of the new node to the current node
6. increment the length
7. End

insert(index, value) {
    if (index == 0) return this.unshift(value)
    if(index == this.length) return this.push(value)
    if(index < 0 || index > this.length) return undefined
    const newNode = new Node(value);
    let prevNode = this.head;
    let currentNode = this.head;
    for (let i = 0; i < index; i++) {
      prevNode = currentNode;
      currentNode = currentNode.next;
    }
    prevNode.next = newNode;
    newNode.next = currentNode;
    this.length++
  }

h) Remove:
This removes an item from a particular index in the list, for this we would be reusing some of the method previously created

1. if the index is zero, use the shift method to remove the item from the beginning
2. if the item is at the end of the list, use the pop method to remove the item
3. if the item is out of the bound of the list, return false
4. iterate over the list up until the given index, keeping track of the previous node and the current node
5. set the next value of the previous node to the next value of the current node
6. set the next value of the current node to null
7. decrement the length
8. End

remove(index){
  if (index == 0) return this.shift()
  if(index == this.length) return this.pop()
  if(index < 0 || index > this.length) return undefined
  let prevNode = this.head;
  let currentNode = this.head;
  for (let i = 0; i < index; i++) {
    prevNode = currentNode;
    currentNode = currentNode.next;
  }
  prevNode.next = currentNode.next
  currentNode.next = null
  this.length--
}

i) Reverse:
This is one of the tricky questions that comes up in a coding interview, the process is a little bit more complex but once you understand the pattern to follow you realise it not as complex as you think. With reverse the entire list is swapped and the first becomes the last and so on, top do this we keep track of three variables at all times i.e, the previous value, the current value and the next value. These three pointers are moved as we iterate over the list, for each value we set the next pointer to the previous value. The operations are as follows

1. swap the head and tail pointers
2. define three pointers, (previousNode, currentNode and nextNode)
3. set the previousNode to null, set the currentNode to the head and set the nextNode to the next value currentNode
4. swap the head and the tail pointers
5. iterate over the list and for each node, set the next value of that node to be equal to the previous node
6. End

reverse(){
  if(!this.head) return false
  let prevNode = null
  let currentNode = this.head
  let nextNode = null

  //swap head and tail
  this.head = this.tail
  this.tail = currentNode

  if(this.length == 2) return this

  for(let i = 0; i < this.length; i++){
    nextNode = currentNode.next
    currentNode.next = prevNode
    prevNode = currentNode
    currentNode = nextNode
  }
}

This concludes the major operations on a linked list. All codes can be found on the github link