Data structures — Singly linked lists

Singly linked lists are a type of data structure that store values in the form of a list. Within the list each value is considered a node, and each node is connected with the following value in the list (or null in case the element is the last in the list) through a pointer.

The first element of the list is considered the head, and the last element is considered the tail. Like with arrays, the length property is defined as the number of elements the list contains.

The main differences compared with arrays are the following:

• Lists don’t have indexes. Each value only “knows” the values to which its connected though pointers.
• Since lists don’t have indexes, we can’t access values randomly. When we want to access a value, we always have to look for it iterating through the list starting from its head or tail.
• The good thing of not having indexes, is that insertion/deletion in any part of the list is more efficient than with arrays. We just have to redirect the pointers of the “neighbor” values, while in arrays or later values need to be reindexed.

Like any data structure, different methods are implemented with it in order to operate over the data. The most common ones include: push, pop, unshift, shift, get, set, insert, remove and reverse.

Push()

• A function that takes a value as input and creates a new node with it.
• If there’s no head (empty list), it will assign the new node as head and tail.
• If the list isn’t empty, it assigns the new node as tail and connects the previous head with the new node with a “next” pointer.
• It increments the length property by one and returns the list with the added element.

A possible implementation could be the following:

push(val){
        var newNode = new Node(val);
        if(!this.head){
            this.head = newNode;
            this.tail = this.head;
        } else {
            this.tail.next = newNode;
            this.tail = newNode;
        }
        this.length++;
        return this;
    }

Pop()

• A function that erases the last value (tail) of the list.
• If the list is empty it returns undefined.
• It loops through the list until it reaches the tail and erases it.
• It modifies the pointer of the previous value so it points to null, and assigns the previous value as tail.
• It decrements the length property by one and returns the erased element.

A possible implementation could be the following:

pop(){
        if(!this.head) return undefined;
        var current = this.head;
        var newTail = current;
        while(current.next){
            newTail = current;
            current = current.next;
        }
        this.tail = newTail;
        this.tail.next = null;
        this.length--;
        if(this.length === 0){
            this.head = null;
            this.tail = null;
        }
        return current;
    }

unshift()

• A function that takes a value and adds it to the beginning of the list.
• If there’s no head (empty list), it will assign the new node as head and tail.
• If the list isn’t empty, it assigns the new node as the head.

A possible implementation could be the following:

unshift(val){
        var newNode = new Node(val);
        if(!this.head) {
            this.head = newNode;
            this.tail = this.head;
        } else {
            newNode.next = this.head;
            this.head = newNode;
        }
        this.length++;
        return this;
    }

Shift()

• A function that erases the first value (head) of the list.
• If the list is empty it returns undefined.
• It assigns the head property to the next value, decreases the length property by one and returns the erased element value.

A possible implementation could be the following:

shift(){
        if(!this.head) return undefined;
        var currentHead = this.head;
        this.head = currentHead.next;
        this.length--;
        if(this.length === 0){
            this.tail = null;
        }
        return currentHead;
    }

get()

• A function that takes a number (index or position) and retrieves the node with the given position in the list.
• If the index is less than zero or greater than or equal to the length of the list, it returns null.
• Else it loops through the list until the given index is reached and returns that value.

A possible implementation could be the following:

get(index){
        if(index < 0 || index >= this.length) return null;
        var counter = 0;
        var current = this.head;
        while(counter !== index){
            current = current.next;
            counter++;
        }
        return current;
    }

set()

• A function that takes a number (index or position) and a value and modifies the value of the node with the given position in the list.
• If the value isn’t found it returns false. Else, if the operation is completed, it returns true.

A possible implementation could be the following:

set(index, val){
        var foundNode = this.get(index);
        if(foundNode){
            foundNode.val = val;
            return true;
        }
        return false;
    }

insert()

• A function that takes a number (index or position) and a value and inserts the value as a new node with the given position in the list.
• If the value is less than zero or greater than the list’s length, return undefined.
• If the index is the same as the length, push a new node to the list. If the index is zero, unshift a new node.
• Otherwise, using the get method we access the node previous to the position we want to enter the new node, and redirect its pointer to the new node. We direct the pointer of the new node to the node that follows in order.
• Increment the list length and return true.

A possible implementation could be the following:

if(index < 0 || index > this.length) return false;
        if(index === this.length) return !!this.push(val);
        if(index === 0) return !!this.unshift(val);
        var newNode = new Node(val);
        var prev = this.get(index - 1);
        var temp = prev.next;
        prev.next = newNode;
        newNode.next = temp;
        this.length++;
        return true;

remove()

• A function that takes a number (index or position) removes the node the node with the given position in the list.
• If the value is less than zero or greater than the list’s length, return undefined.
• If the index is the same as the length, pop the last element. If the index is zero, shift the first element.
• Otherwise, using the get method we access the node previous to the position we want to remove, and redirect its pointer to the node next to the one we want to remove.
• Decrement the list length and return the value of the erased node.

A possible implementation could be the following:

if(index < 0 || index >= this.length) return undefined;
        if(index === 0) return this.shift();
        if(index === this.length - 1) return this.pop();
        var previousNode = this.get(index - 1);
        var removed = previousNode.next;
        previousNode.next = removed.next;
        this.length--;
        return removed;

reverse()

• A function that reverses the order of the list in place.
• Swaps head and tail.
• Creates variables called next and prev.
• Creates a variable called node and initializes it to the head property.
• Then loop through the list and: 1) Set next variable to be the next property on whatever node the loop is. 2) Set the next property on the node to be whatever prev is. 3) Set prev to be the value of the node variable. 4) Set the node variable to be the value of the next variable.
• Once the loop is finished, return the list.

A possible implementation could be the following:

var node = this.head;
      this.head = this.tail;
      this.tail = node;
      var next;
      var prev = null;
      for(var i = 0; i < this.length; i++){
        next = node.next;
        node.next = prev;
        prev = node;
        node = next;
      }
      return this;

A full implementation of a singly linked list could be the following:

class Node{
    constructor(val){
        this.val = val;
        this.next = null;
    }
}
class SinglyLinkedList{
    constructor(){
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    push(val){
        var newNode = new Node(val);
        if(!this.head){
            this.head = newNode;
            this.tail = this.head;
        } else {
            this.tail.next = newNode;
            this.tail = newNode;
        }
        this.length++;
        return this;
    }
    pop(){
        if(!this.head) return undefined;
        var current = this.head;
        var newTail = current;
        while(current.next){
            newTail = current;
            current = current.next;
        }
        this.tail = newTail;
        this.tail.next = null;
        this.length--;
        if(this.length === 0){
            this.head = null;
            this.tail = null;
        }
        return current;
    }
    shift(){
        if(!this.head) return undefined;
        var currentHead = this.head;
        this.head = currentHead.next;
        this.length--;
        if(this.length === 0){
            this.tail = null;
        }
        return currentHead;
    }
    unshift(val){
        var newNode = new Node(val);
        if(!this.head) {
            this.head = newNode;
            this.tail = this.head;
        }
        newNode.next = this.head;
        this.head = newNode;
        this.length++;
        return this;
    }
    get(index){
        if(index < 0 || index >= this.length) return null;
        var counter = 0;
        var current = this.head;
        while(counter !== index){
            current = current.next;
            counter++;
        }
        return current;
    }
    set(index, val){
        var foundNode = this.get(index);
        if(foundNode){
            foundNode.val = val;
            return true;
        }
        return false;
    }
    insert(index, val){
        if(index < 0 || index > this.length) return false;
        if(index === this.length) return !!this.push(val);
        if(index === 0) return !!this.unshift(val);
        var newNode = new Node(val);
        var prev = this.get(index - 1);
        var temp = prev.next;
        prev.next = newNode;
        newNode.next = temp;
        this.length++;
        return true;
    }
    remove(index){
        if(index < 0 || index >= this.length) return undefined;
        if(index === 0) return this.shift();
        if(index === this.length - 1) return this.pop();
        var previousNode = this.get(index - 1);
        var removed = previousNode.next;
        previousNode.next = removed.next;
        this.length--;
        return removed;
    }
    reverse(){
      var node = this.head;
      this.head = this.tail;
      this.tail = node;
      var next;
      var prev = null;
      for(var i = 0; i < this.length; i++){
        next = node.next;
        node.next = prev;
        prev = node;
        node = next;
      }
      return this;
    }
    print(){
        var arr = [];
        var current = this.head
        while(current){
            arr.push(current.val)
            current = current.next
        }
        console.log(arr);
    }
}

Complexity

Singly linked lists functions have the following complexities:

• Insertion — O(1)
• Removal — O(n)
• Search — O(n)
• Access — O(n)