Singly linked List.


Introduction to Singly linked list(SLL):-

Firstly, Singly liked list is a data structure(or any data structure for the matter) that stores heterogeneous data. It doesn’t matter if the data is string or numbers or objects or mixture of them. The name Singly linked list comes from the fact that each node is only connected one directionally. In other words, the data in it can only read from one direction( from head node to tail node but not from tail node to head node).  It’s ordered and It’s a list of data just like an array. But there’s a really big distinction in an array. In arrays each item is mapped with its index. On the other hand, a singly linked list just consists of a bunch of elements with no indices who are just pointing to the next element.  

For example, consider a bunch of train cars connected to each other where one car connects to the next one and that one connects to the next one. But there is no index that we use to access data in the car. Technically Train is an example for the doubly linked list as we can go to the next car as well as pervious car. But in this case, assume that once you enter a car the door to the previous car gets locked. So We’ve just started the first one and then moved to the second one moved to the third one moved to the fourth and then moved to the fifth and so on till the last car. Once the very last car is reached again you have to start from the first car and follow a similar process.

Singly linked list terminologies:-

In a singly linked list, every element is called a nodeSo a singly linked list consists of a bunch of nodes. Each and every node in the singly linked list consists of two entries.

  1.  Data.
  2. Address to the next entity.

If the node is the last node then the address to the next node. i.e it could be represented as per our wish either by storing null or -1 etc..Besides this, The very first node in the singly linked list is called as the head nodeThe last node is called the tail node.

While implementing we don’t keep track of every single node in the linked list. Rather we keep track of 3 nodes. They are 

  1. Head node.
  2. Tail node.
  3. The total length of the linked list etc. i.e number of nodes in SLL.

By keeping track of the head and from the head we can figure out the next one. And from there we can figure out the next one all the way until the end. And then also we keep track full length to make things easier.

How a singly linked list is different from an array:-

In an array, adjacent memory locations contain the data. That is to say, when we initialize an array with required length then a single memory is allocated to fit the whole array. When we push the values into the array then they will get placed on the adjacent memory location.
Whereas in the case of singly linked lists nodes are created in random memory locations. But to know where can we find the next element each node has the next block to keep track of the next element address. Thus memory is utilized effectively when required only.
Besides this, an array can hold only homogeneous data, whereas any dat structure can hold heterogeneous data by growing their size dynamically.

Defining a Node:-

Okay, we have seen enough theory. let’s start writing our code. let’s start by defining a class for each node. It just stores a piece of data which we’ll call it value and then it stores a reference to next node which we’ll call next. So let’s define our class and call it Node.

class Node {
    Object value;
    Node next;
    
public Node(Object value) {
        
super();
        
this.value = value; this.next= null;
    }
}
class Node {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

Defining a Singly Linked List:-

As we have discussed above a singly linked list consists of head node, tail node and length of the singly linked list. So By using the node above a singly linked list can be defined as shown below.
public class SinglyLinkedList {
    public Node head;
    public Node tail;
    public int length;
    public SinglyLinkedList() {
        super();
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
}
class SinglyLinkedList {
    constructor() {
        this.length = 0;
        this.head = null;
        this.tail = null;
    }
}

In the above example code observe that in the constructor we have set head and tail to null and length of the list to 0. This is because we will not have any data when we initialize the singly linked list.

Operations on Singly Linked List:-

1. Push:- 

Push operation adds a new node at the end of the singly linked list i.e to the tail node.
Singly linked list push operation illustration.
But remember that when we push the first node we have to add an additional check for the null condition as the head, tail are null after the initializing it.
The pseudocode for push operation is as shown below.
 Implementation is as shown below.
public SinglyLinkedList push(Object value) {
    Node newNode = new Node(value);
    if (this.head == null) {
        this.head = newNode;
        this.tail = newNode;
    } else {
        this.tail.next = newNode;
this.tail = newNode;
    }
    this.length += 1;
    return this;
}
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 += 1;
        return this;
    }

The time complexity of the push operation is O(1) as we are adding a new node to the tail node and is available on variable tail.

2. Pop:-

Pop operation is used to remove the last node in the singly linked list. 
Singly linked list pop operation illustration.
Even though we have access to the tail node we cant directly make it null. Because we need to update the tail value to the last but one node and reduce the length by 1.
The pseudocode for the pop operation is as shown below.
Pseudocode for pop operation f singly linked list.

Implementation of pop operation is as shown below.

public Object pop() {
        if (this.length == 0) {
            return null;
        }
        else {
            Node current = this.head;
            Node newtail = current;
            while (current.next != null) {
                newtail = current;
                current = current.next;
            }
            this.tail = newtail;
            this.tail.next = null;
            this.length -= 1;
            if (this.length == 0) {
                this.head = null;
                this.tail = null;
            }
            return current.value;
        }
    }
pop() {
        if (this.length === 0) {
            return undefined;
        }
        else {
            var current = this.head;
            var newtail = current;
            while (current.next) {
                newtail = current;
                current = current.next;
            }
            this.tail = newtail;
            this.tail.next = null
            this.length -= 1;
            if (this.length === 0) {
                this.head = null
                this.tail = null;
            }
            return current.value;
        }
    }

The time complexity of the pop operation is O(n) as we have to traverse from head to tail and make last nut one nodes next value to null.

3. Shift:-

Shift operation is used for removing the first element from singly linked list. 
Singly linked list shift operation illustration.

The Pseudocode for shift operation as explained below.

public Object shift() {
        if (this.length == 0) {
            return null;
        }
        if (this.length == 1) {
            Node currentHead = this.head;
            this.head = null;
            this.tail = null;
            this.length = 0;
            return currentHead.value;
        }
        Node currentHead = this.head;
        Node nextHead = currentHead.next;
        this.head = nextHead;
        this.length -= 1;
        return currentHead.value;
    }
shift() {
        if (this.length === 0) {
            return undefined;
        }
        if (this.length === 1) {
            var currentHead = this.head;
            this.head = null;
            this.tail = null;
            this.length = 0;
            return currentHead.value;
        }
        var currentHead = this.head;
        var nextHead = currentHead.next;
        this.head = nextHead;
        this.length -= 1;
        return currentHead.val;
    }

The time complexity of shift operation is O(1) as we remove the head by updating the head.next value as new head.

4. Unshift:-

Unshift operation is used to add a new node in-front of the existing head node. 
Singly linked list unshift illustration.

Pseudocode for the unshift operation is as shown in the below image.
Implementation is as shown below.
public void unshift(Object value) {
        if (this.length == 0) {
            this.push(value); // use the function already defined.
        }
        else {
            Node newHead = new Node(value);
            Node currentHead = this.head;
            newHead.next = currentHead;
            this.head = newHead;
            this.length += 1;
        }
    }
unshift(value) {
        if (this.length === 0) {
            this.push(value) // use the function already defined.
        }
        else {
            var newHead = new Node(value);
            var currentHead = this.head;
            newHead.next = currentHead
            this.head = newHead
            this.length += 1;
        }
    }

As we are just adding a new node at the beginning of singly linked all we have to do is create a new node and make next value of new node to current head. So the time complexity can be generalized as O(1).

5. get:-

Get operation is used to get the element at a given position. 
Pseudocode for the given operation is described below.

The implementation as follows.

public Node get(int index) {
        if (index < 0 || index >= this.length) return null;
        else {
            int i = 0;
            Node currentValue = this.head;
            while (i != index) {
                currentValue = currentValue.next;
                i = i + 1;
            }
            return currentValue.value;
        }
    }
get(index) {
        if (index < 0 || index >= this.length) return null;
        else {
            var i = 0;
            var currentValue = this.head;
            while (i !== index) {
                currentValue = currentValue.next;
                i = i + 1;
            }
            return currentValue.value;
        }
    }

As observed in the above logic, To get a value at a given position we have to repeat a loop that many number of times. So the time complexity can be represented as O(n).

6. set:-

The set operation is used for updating the value at a particular node. 
The process involves traversing the singly linked list until a specified node and replacing the value at that with the new value provided. So pseudocode is as shown in the following picture.
 
public boolean set(int index, Object newValue) {
        Node node = this.get(index);
        if (node != null) {
            node.value = newValue;
            return true;
        }
        return false;
    }
set(index, newValue) {
        var node = this.get(index);
        if (node) {
            node.value = newValue;
            return true;
        }
        return false;
    }

The time complexity of set operation is o(k) as we have to traverse the list till kth position as requested by the user.

7. Insert:-

As part of insert operation we will insert a new node a specific position as requested by the user. The Logic involves traversing the singly linked list and till the specified index and insert a new node and update the next address of the node at index to new node and newly inserted node’s next address to the node after the index+1 length.
Singly linked list insert illustration
The logic we need to follow is as described below.
public boolean insert(int index, Object value) {
        if (index < 0 || index > this.length) {
            return false;
        }
        if (index == this.length) {
            this.push(value);
            return true;
        }
        if (index == 0) {
            this.unshift(value);
            return true;
        }
        Node newNode = new Node(value);
        Node nthNode = this.get(index - 1);
        Node nthNodeNext = nthNode.next;
        nthNode.next = newNode;
        newNode.next = nthNodeNext;
        this.length += 1;
        return true;
    }
insert(index, value) {
        if (index < 0 || index > this.length) {
            return false;
        }
        if (index === this.length) {
            this.push(value)
            return true;
        }
        if (index === 0) {
            this.unshift(value);
            return true;
        }
        var newNode = new Node(value);
        var nthNode = this.get(index - 1);
        var nthNodeNext = nthNode.next;
        nthNode.next = newNode;
        newNode.next = nthNodeNext;
        this.length += 1;
        return true;
    }

The time complexity of the Insert operation depends upon the index at which we want to insert a new node. If the new node needs to be inserted at index 1 then the time complexity is O(1). If the position is 2 then O(2). So for the worst case scenario we can say that the time complexity is O(k) where k is the index at which new node to be inserted.

8. Remove:-

As the name suggests, Remove operation is used for removing a node at a given index. The logic behind it is very similar to inserting a new node. But here we traverse till the node and point next element of node at the given index to the next of the node previous to the node at a given index. 

Singly linked list remove illustration.

The logic for the same is as shown below.

 
 
public Object remove(int index) {
        if (index < 0 || index > this.length) {
            return null;
        }
        if (index == 0) {
            return this.shift();
        }
        if (index == this.length) {
            return this.pop();
        }
        Node previousNode = this.get(index - 1);
        Node deletedNode = previousNode.next;
        previousNode.next = deletedNode.next;
        this.length -= 1;
        return deletedNode;
    }
remove(index) {
        if (index < 0 || index > this.length) {
            return null;
        }
        if (index === 0) {
            return this.shift();
        }
        if (index === this.length) {
            return this.pop();
        }
        var previousNode = this.get(index - 1);
        var deletedNode = previousNode.next;
        previousNode.next = deletedNode.next;
        this.length -= 1;
        return deletedNode;
    }

The time complexity of the remove operation is as same as time complexity of inserting a new node at an index. That is O(k).

Well, That’s it. I think i covered most of the operations on singly linked list. The singly linked list is an easy data structure to understand as it is widely used in various other implementations such as stacks, queues, etc. 

Some of the real life example of the singly linked lists are implementing music player in which you add songs to a playlist, previous and next buttons in the browser etc.

The disadvantage with a singly linked list is, it can only read from one direction i. e from head to tail but not from tail to head. This is where doubly linked list comes into the picture which can be read from both directions. I will be writing about it next in the similar way with pseudocode and implementations. So stay tuned with a coffee.