Linked List

Category: Data Structures
Tags: #datastructures#linkedlist

A Linked List or Singly Linked List is a linear data structure which collectively represents a sequence of data. In this tutorial, we will learn about the implementation of a singly linked list and various operations on it like insertion, deletion and traversal of a Linked List.

Implementation of Linked List (Singly Linked List)

Table of contents

A Linked List (also known as Singly Linked List) is a collection of nodes in which each node is pointing to next node and last node point to null.

SIngly Linked List example

Declaration of type node for Linked List

We have to create a data structure or Node which contains two part i.e, first part will contain the data to be stored and second will store address of next such node. We can create this by using user defined data type.

SIngly Linked List node

Python
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
JavaScript
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

Traversing the Linked List

Traversing means visiting all the node once i.e, we want to read all the data available in the linked list. We can do so by visiting all the nodes one by one and reading data available in each node.

Simply, use a temporary node and initialize it with the head node so that we can start with the begining of the list and then go through all the nodes one by one till the last node is reached. And we can get the last node by checking the next value of node i.e., if next value of node is null then this is the end of node.

SIngly Linked List traversal

Python
def traverse(self):
    if self.head:
        temp = self.head

        while temp is not None:
            print(temp.data)
            temp = temp.next
    else:
        print(None)
JavaScript
traverse() {
  if (this.head) {
    let temp = this.head;
    while (temp != null) {
      console.log(temp.data);
      temp = temp.next;
    }
  } else {
    console.log(null);
  }
}

Length of a Linked List

To find length of a linked list we can simply use a temporary variable and initialize it by assigning the head node. Now, move it to every node one by one and increase the counter variable.

Singly Linked List length

Python
def length(self):
    count = 0
    temp = self.head
    while temp:
        temp = temp.next
        count += 1
    return count
JavaScript
length() {
  let count = 0;
  let temp = this.head;
  while (temp) {
    temp = temp.next;
    count += 1;
  }
  return count;
}

Insertion in a Linked List

Insertion in a Linked List can be done in following three ways:

  1. Insertion of new node at the begining
  2. Insertion of new node at the end
  3. Insertion of new node at given position (middle or some random location)

Insertion at the begining of the Linked List

While inserting a node at the begining position, two situation may arise:

  1. Insertion when Linked List is emtpy: In this case we can simply create a new node and put the value in data part and null into the next part (which is already done in Class Node constructor) then assign it to the head.
  2. Insertion when Linked List is not empty: In this case create a new node, add value into the data part and assign the node pointed pointed by head to next of newly created node and then head will now point to new node.

Singly Linked List insertion at begining

Python
def insert_at_start(self, data):
    new_node = Node(data)
    new_node.next = self.head
    self.head = new_node
JavaScript
insertAtStart(data) {
  const newNode = new Node(data);
  newNode.next = this.head;
  this.head = newNode;
}

Insertion at the end of the Linked List

While inserting a node at the end position, two situation may arise:

  1. Insertion when Linked List is emtpy: In this case we can simply create a new node and put the value in data part and null into the next part (which is already done in Class Node constructor) then assign it to the head.
  2. Insertion when Linked List is not empty: In this case create a new node, and then traverse till the end of the Linked List then add the new node in the next part of last node and put null into the next part because it is the last node now.

Singly Linked List insertion at the end

Python
def insert_at_end(self, data):
    new_node = Node(data)
    if self.head:
        temp = self.head
        while temp.next:
            temp = temp.next
        temp.next = new_node
    else:
        self.head = new_node
JavaScript
insertAtEnd(data) {
  const newNode = new Node(data);
  if (this.head) {
    let temp = this.head;
    while (temp.next) {
      temp = temp.next;
    }
    temp.next = newNode;
  } else {
    this.head = newNode;
  }
}

Insertion at given position in the Linked List

While inserting at any given position following 3 situation may arise based on user input:

  1. Insertion at the begining: In this case, simply call the function used to insert at begining.
  2. Insertion at the end: In this case, simply call the function used to insert at the end.
  3. Insertion at any random position: In this case, use a temporary variable and initialize with the head pointer traverse till the given position - 1 and then insert the new node by adjusting the next pointers.

Singly Linked List insertion at given position

Python
def insert_at_position(self, pos, data):
    if pos < 0 or pos >= self.length():
        raise 'Enter a valid postion'
    else:
        if pos == 0:
            self.insert_at_start(data)
        elif pos == self.length()-1:
            self.insert_at_end(data)
        else:
            temp = self.head
            for _ in range(pos-1):
                temp = temp.next
            new_node = Node(data)
            new_node.next = temp.next
            temp.next = new_node
JavaScript
insertAtPosition(pos, data) {
  if (pos < 0 || pos >= this.length()) {
    throw "Enter a valid position";
  } else {
    if (pos === 0) {
      this.insertAtStart(data);
    } else if (pos === this.length() - 1) {
      this.insertAtEnd(data);
    } else {
      let temp = this.head;
      for (let i = 0; i < pos; i++) {
        temp = temp.next;
      }
      let newNode = new Node(data);
      newNode.next = temp.next;
      temp.next = newNode;
    }
  }
}

Deletion in a Linked List

Same as insertion deletion in a Linked List can be done in 3 ways:

  1. Deletion of a node from the begining
  2. Deletion of a node from the end
  3. Deletion of a node from given position (middle or some random location)

Deletion from the begining of the Linked List

While deleting a node at the from begining, two situation may arise:

  1. Deletion when Linked List is emtpy: When Linked List is empty throw an error that Linked List is empty.
  2. Deletion when Linked List is not empty: When Linked List is not empty simply shift the head pointer to the next element. For languages like Python, Java etc. which have in built mechanism for garbage collection, can remove the deleted node itself but in case of languages like C or C++ we have to point that node and remove it manually.

Singly Linked List deletion from start

Python
def delete_from_start(self):
    if self.head:
        data = self.head.data
        self.head = self.head.next
        return data
    else:
        raise Exception('Empty linked list')
JavaScript
deleteFromStart() {
  if (this.head) {
    const data = this.head.data;
    this.head = this.head.next;
    return data;
  } else {
    throw "Empty linked list";
  }
}

Deletion from the end of the Linked List

While deleting a node at the from the end, two situation may arise:

  1. Deletion when Linked List is emtpy: When Linked List is empty throw an error that Linked List is empty.
  2. Deletion when Linked List is not empty: When Linked List is not empty traverse the linked list till the second last element and then put null into the next part of this node so that its link with last element can broken. For languages like Python, Java etc. which have in built mechanism for garbage collection, can remove the deleted node itself but in case of languages like C or C++ we have to point that node and remove it manually.

Singly Linked List deletion from end

Python
def delete_from_end(self):
    if self.head:
        current = self.head
        previous = self.head
        while current.next != None:
            previous = current
            current = current.next
        previous.next = None
        return current.data
    else:
        raise Exception('Empty linked list')
JavaScript
deleteFromEnd() {
  if (this.head) {
    let current = this.head;
    let previous = this.head;
    while (current.next != null) {
      previous = current;
      current = current.next;
    }
    previous.next = null;
    return current.data;
  } else {
    throw "Empty linked list";
  }
}

Deletion from given position in the Linked List

While deleting at any given position following 3 situation may arise based on user input:

  1. Deletion from the begining: In this case, simply call the function used to delete from begining.
  2. Deletion from the end: In this case, simply call the function used to delete from the end.
  3. Deletion from any random position: In this case, use two temporary variable and initialize with the head pointer traverse one pointer till the given position and the other till given position - 1 and then delete that node and then adjust the pointers. For languages like Python, Java etc. which have in built mechanism for garbage collection, can remove the deleted node itself but in case of languages like C or C++ we have to point that node and remove it manually.

Singly Linked List deletion from given position

Python
def delete_at_position(self, pos):
    current = self.head
    previous = self.head

    if pos < 0 or pos >= self.length():
        raise 'Enter a valid postion'
    else:
        if pos == 0:
            return self.delete_from_start()
        elif pos == self.length()-1:
            return self.delete_from_end()
        else:
            for _ in range(pos):
                previous = current
                current = current.next
            data = current.data
            previous.next = current.next
            return data
JavaScript
deleteAtPosition(pos) {
  let current = this.head;
  let previous = this.head;

  if (pos < 0 || pos >= this.length()) {
    throw "Enter a valid position";
  } else {
    if (pos === 0) {
      return this.deleteFromStart();
    } else if (pos === this.length() - 1) {
      return this.deleteFromEnd();
    } else {
      for (let i = 0; i < pos; i++) {
        previous = current;
        current = current.next;
      }
      let data = current.data;
      previous.next = current.next;
      return data;
    }
  }
}

Implementation of Linked List

Implementation of a singly linked list with all the function combined with output.

Python
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def insert_at_start(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def insert_at_end(self, data):
        new_node = Node(data)
        if self.head:
            temp = self.head
            while temp.next:
                temp = temp.next
            temp.next = new_node
        else:
            self.head = new_node

    def insert_at_position(self, pos, data):
        if pos < 0 or pos >= self.length():
            raise 'Enter a valid postion'
        else:
            if pos == 0:
                self.insert_at_start(data)
            elif pos == self.length()-1:
                self.insert_at_end(data)
            else:
                temp = self.head
                for _ in range(pos-1):
                    temp = temp.next
                new_node = Node(data)
                new_node.next = temp.next
                temp.next = new_node

    def delete_from_start(self):
        if self.head:
            data = self.head.data
            self.head = self.head.next
            return data
        else:
            raise Exception('Empty linked list')

    def delete_from_end(self):
        if self.head:
            current = self.head
            previous = self.head
            while current.next != None:
                previous = current
                current = current.next
            previous.next = None
            return current.data
        else:
            raise Exception('Empty linked list')

    def delete_at_position(self, pos):
        current = self.head
        previous = self.head

        if pos < 0 or pos >= self.length():
            raise 'Enter a valid postion'
        else:
            if pos == 0:
                return self.delete_from_start()
            elif pos == self.length()-1:
                return self.delete_from_end()
            else:
                for _ in range(pos):
                    previous = current
                    current = current.next
                data = current.data
                previous.next = current.next
                return data

    def get_first(self):
        if self.head:
            return self.head.data
        else:
            raise Exception('Linked List is empty')

    def get_last(self):
        if self.head:
            current = self.head
            while current.next != None:
                current = current.next
            return current.data
        else:
            raise Exception('Linked List is empty')

    def get_at_position(self, pos):
        if pos < 0 or pos >= self.length():
            raise Exception('Linked List is empty')

        current = self.head
        for _ in range(pos):
            current = current.next
        return current.data

    def traverse(self):
        if self.head:
            temp = self.head

            while temp is not None:
                print(temp.data)
                temp = temp.next
        else:
            print(None)

    def length(self):
        count = 0
        temp = self.head
        while temp:
            temp = temp.next
            count += 1
        return count

ll = LinkedList()
ll.insert_at_end(1)
ll.insert_at_end(2)
ll.insert_at_end(3)
ll.insert_at_end(4)
ll.insert_at_end(5)
ll.traverse()
JavaScript
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
  }

  insertAtStart(data) {
    const newNode = new Node(data);
    newNode.next = this.head;
    this.head = newNode;
  }

  insertAtEnd(data) {
    const newNode = new Node(data);
    if (this.head) {
      let temp = this.head;
      while (temp.next) {
        temp = temp.next;
      }
      temp.next = newNode;
    } else {
      this.head = newNode;
    }
  }

  insertAtPosition(pos, data) {
    if (pos < 0 || pos >= this.length()) {
      throw "Enter a valid position";
    } else {
      if (pos === 0) {
        this.insertAtStart(data);
      } else if (pos === this.length() - 1) {
        this.insertAtEnd(data);
      } else {
        let temp = this.head;
        for (let i = 0; i < pos; i++) {
          temp = temp.next;
        }
        let newNode = new Node(data);
        newNode.next = temp.next;
        temp.next = newNode;
      }
    }
  }

  deleteFromStart() {
    if (this.head) {
      const data = this.head.data;
      this.head = this.head.next;
      return data;
    } else {
      throw "Empty linked list";
    }
  }

  deleteFromEnd() {
    if (this.head) {
      let current = this.head;
      let previous = this.head;
      while (current.next != null) {
        previous = current;
        current = current.next;
      }
      previous.next = null;
      return current.data;
    } else {
      throw "Empty linked list";
    }
  }

  deleteAtPosition(pos) {
    let current = this.head;
    let previous = this.head;

    if (pos < 0 || pos >= this.length()) {
      throw "Enter a valid position";
    } else {
      if (pos === 0) {
        return this.deleteFromStart();
      } else if (pos === this.length() - 1) {
        return this.deleteFromEnd();
      } else {
        for (let i = 0; i < pos; i++) {
          previous = current;
          current = current.next;
        }
        let data = current.data;
        previous.next = current.next;
        return data;
      }
    }
  }

  traverse() {
    if (this.head) {
      let temp = this.head;
      while (temp != null) {
        console.log(temp.data);
        temp = temp.next;
      }
    } else {
      console.log(null);
    }
  }

  length() {
    let count = 0;
    let temp = this.head;
    while (temp) {
      temp = temp.next;
      count += 1;
    }
    return count;
  }
}

const ll = new LinkedList();
ll.insertAtEnd(1);
ll.insertAtEnd(2);
ll.insertAtEnd(3);
ll.insertAtEnd(4);
ll.insertAtEnd(5);
ll.traverse();

Output

1
2
3
4
5
Introduction to Linked list
Doubly Linked List
Author - Abhishek Kumar

Recommended Posts

Introduction to Linked list
Doubly Linked List
Program to find middle element of a Linked List
Program to reverse a linked list