TheAconiteDev

What is a linked list?

Linked List is a linear data structure in which, unlike arrays, elements are stored in non-contiguous memory locations. Each element in a linked list points to the next one in the sequence. To access a specific element in a linked list, we need to traverse to it from the start of the list.

Types of linked lists

Linked lists can be of three types depending upon how their nodes are connected to each other. Each node of a linked list consists of data and pointers (or references) to its next and previous node in the list.

Singly linked list

Singly Linked List

In a singly linked list, each node contains two properties – data and reference to next node. We store the reference to the first node in a variable called head. Next node reference of last node points to null which marks the end of the list.

Doubly linked list

Doubly Linked List

In a doubly linked list, each node contains three properties – reference to previous node, data and reference to next node. Reference to first node is stored in head. Previous node reference of the first node and next node reference of the last node points to null.

Circular linked list

Circular Linked List

Circular linked list is similar to doubly linked list with some differences. First, instead of head we use a sentinel node which is similar to any other node in the list but does not contain any data. Next node reference of the sentinel node points to the first node in the list. Previous node reference of the sentinel node points to the last node of the list. Second, Previous node reference of the first node of the list points to the sentinel node. And, Next node reference of the last node points to the sentinel node.

Linked list operations

Just like other data structures, we can do insertion, deletion and traversal on linked lists. Let’s understand how they are performed on a singly linked list. Concepts discussed below can be easily applied to doubly and circular linked lists with few changes.

Insertion

Insertion in a linked list

Suppose we want to insert a node N between nodes A and B. We will first set the next node reference of N to point to B and then set the next node reference of A to point N which was earlier pointing to B.

Deletion

Deletion in a linked list

Suppose we want to delete a node N between nodes A and B. We will set the next node reference of A to next node reference of N which points to B. By doing this we have removed the reference to node N from the list and it cannot be accessed from any node.

Traversal

Traversal in a linked list

To traverse a list, we maintain a temporary variable current which points to the first node and goes to the last node by using the next node reference of the nodes.

Pseudocode of operations on a singly linked list

Let’s understand linked list operations using their pseudocodes for a singly linked list. These methods can also be used for double and circular linked lists with few changes. Complete implementation of singly, doubly and circular linked lists is given later in the article.

insertAtStart

	public void insertAtStart(T item) {
		Node node = new Node(item);

		if (head != null) {
			node.next = head;
		}

		head = node;
	}

We first check whether the list is empty. If not, we set the next node reference of the new node to the first node of the list. Then we change the head to point to the new node making it the first node of the list.

insertAtEnd

	public void insertAtEnd(T item) {
		Node node = new Node(item);
		Node current = head;

		if (current == null) {
			head = node;
			return;
		}

		while (current.next != null) {
			current = current.next;
		}

		current.next = node;
	}

We first check whether the list is empty. If it is, this operation is the same as inserting at the start of the list. If not, we first traverse to the last node of the list. Next node reference of the last node is set to new node making it the new last node of the list.

insertAtPosition

	public void insertAt(T item, int position) {
		Node node = new Node(item);
		Node current = head;
		Node previous = null;
		int index = 0;

		if (current == null) {
			head = node;
			return;
		}

		while (index < position && current.next != null) {
			previous = current;
			current = current.next;
			index++;
		}

		if (index == position) {
			node.next = current;

			if (previous == null) {
				head = node;
			} else {
				previous.next = node;
			}
		} else {
			current.next = node;
		}
	}

Similar to previous methods, if the list is empty, we just insert the node in the list making it the first node. Otherwise, we traverse to the required position or to the last node if the given position is greater than the size of the list. We also maintain a previous variable which points to the previous node of the current node. If we are at the required position, we insert the new node between the previous and current node. Note that, if previous pointing to null means that we are inserting the node at the first position in the list. If we are not at the required position, we insert the new node at the end of the list.

Exercise – What will happen if the position provided is negative?

	public boolean contains(T item) {
		Node current = head;

		while (current != null) {
			if (current.data.compareTo(item) == 0) {
				return true;
			}

			current = current.next;
		}

		return false;
	}

In this method, we traverse to the last node of the linked list and keep checking if the given item matches with any of node’s data.

deleteFromStart

	public T deleteFromStart() {
		if (head == null) {
			return null;
		}

		Node node = head;
		head = head.next;

		return node.data;
	}

We first check if the list is empty and return null if it is. If not, we point head to the next node reference of the first node of the list and return the data of the deleted node.

deleteFromEnd

	public T deleteFromEnd() {
		Node current = head;
		Node previous = null;
		T deletedData = null;

		if (current == null) {
			return deletedData;
		}

		while (current.next != null) {
			previous = current;
			current = current.next;
		}

		deletedData = current.data;

		if (previous == null) {
			head = null;
		} else {
			previous.next = null;
		}

		return deletedData;
	}

We traverse to the last node of the list and mark the next node reference of the node pointed by previous to null.

deleteFromPosition

	public T deleteFromPosition(int position) {
		Node current = head;
		Node previous = null;
		T deletedData = null;
		int index = 0;

		if (head == null) {
			return deletedData;
		}

		while (index < position && current.next != null) {
			previous = current;
			current = current.next;
			index++;
		}

		if (index != position) {
			return deletedData;
		}

		deletedData = current.data;

		if (previous == null) {
			head = null;
		} else {
			previous.next = current.next;
		}

		return deletedData;
	}

This is somewhat similar to insertAtPosition except that we delete a node here. Another difference is that we do not delete any node if the position given is not correct. Here, current is pointing to the node which is to be deleted and previous is pointing to the node before it. To delete the current node, we just set the next node reference of previous node to next node reference of the current node. This skips the current node in all list operations and marks it for garbage collection.

Complete implementation

Below is the complete program implementing a singly, doubly and circular list.

package com.theaconitedev;

public interface ILinkedList<T extends Comparable<T>> {

	public void insertAtStart(T item);

	public void insertAt(T item, int position);

	public void insertAtEnd(T item);

	public boolean contains(T item);

	public T deleteFromStart();

	public T deleteFromPosition(int position);

	public T deleteFromEnd();

	public void printList();
}

package com.theaconitedev;

public class SinglyLinkedList<T extends Comparable<T>> implements ILinkedList<T> {

	private Node head;

	private class Node {
		public T data;
		public Node next;

		public Node(T data) {
			this.data = data;
		}
	}

	@Override
	public void insertAtStart(T item) {
		Node node = new Node(item);

		if (head != null) {
			node.next = head;
		}

		head = node;
	}

	@Override
	public void insertAt(T item, int position) {
		Node node = new Node(item);
		Node current = head;
		Node previous = null;
		int index = 0;

		if (current == null) {
			head = node;
			return;
		}

		while (index < position && current.next != null) {
			previous = current;
			current = current.next;
			index++;
		}

		if (index == position) {
			node.next = current;

			if (previous == null) {
				head = node;
			} else {
				previous.next = node;
			}
		} else {
			current.next = node;
		}
	}

	@Override
	public void insertAtEnd(T item) {
		Node node = new Node(item);
		Node current = head;

		if (current == null) {
			head = node;
			return;
		}

		while (current.next != null) {
			current = current.next;
		}

		current.next = node;
	}

	@Override
	public boolean contains(T item) {
		Node current = head;

		while (current != null) {
			if (current.data.compareTo(item) == 0) {
				return true;
			}

			current = current.next;
		}

		return false;
	}

	@Override
	public T deleteFromStart() {
		if (head == null) {
			return null;
		}

		Node node = head;
		head = head.next;

		return node.data;
	}

	@Override
	public T deleteFromPosition(int position) {
		Node current = head;
		Node previous = null;
		T deletedData = null;
		int index = 0;

		if (head == null) {
			return deletedData;
		}

		while (index < position && current.next != null) {
			previous = current;
			current = current.next;
			index++;
		}

		if (index != position) {
			return deletedData;
		}

		deletedData = current.data;

		if (previous == null) {
			head = null;
		} else {
			previous.next = current.next;
		}

		return deletedData;
	}

	@Override
	public T deleteFromEnd() {
		Node current = head;
		Node previous = null;
		T deletedData = null;

		if (current == null) {
			return deletedData;
		}

		while (current.next != null) {
			previous = current;
			current = current.next;
		}

		deletedData = current.data;

		if (previous == null) {
			head = null;
		} else {
			previous.next = null;
		}

		return deletedData;
	}

	@Override
	public void printList() {
		Node current = head;

		while (current != null) {
			System.out.println(current.data);
			current = current.next;
		}
	}

}

package com.theaconitedev;

public class DoublyLinkedList<T extends Comparable<T>> implements ILinkedList<T> {

	private Node head;

	private class Node {
		public Node previous;
		public T data;
		public Node next;

		public Node(T data) {
			this.data = data;
		}
	}

	@Override
	public void insertAtStart(T item) {
		Node node = new Node(item);

		if (head == null) {
			head = node;
			return;
		}

		head.previous = node;
		node.next = head;
		head = node;
	}

	@Override
	public void insertAt(T item, int position) {
		Node node = new Node(item);
		Node current = head;
		int index = 0;

		if (current == null) {
			head = node;
			return;
		}

		while (index < position && current.next != null) {
			current = current.next;
			index++;
		}

		if (index == position) {
			node.next = current;
			node.previous = current.previous;
			
			if (current.previous == null) {
				head = node;
			} else {
				current.previous.next = node;
			}
			
			current.previous = node;
		} else {
			node.previous = current;
			current.next = node;
		}
	}

	@Override
	public void insertAtEnd(T item) {
		Node node = new Node(item);
		Node current = head;

		if (current == null) {
			head = node;
			return;
		}

		while (current.next != null) {
			current = current.next;
		}

		current.next = node;
		node.previous = current;
	}

	@Override
	public boolean contains(T item) {
		Node current = head;

		while (current != null) {
			if (current.data.compareTo(item) == 0) {
				return true;
			}

			current = current.next;
		}

		return false;
	}

	@Override
	public T deleteFromStart() {
		if (head == null) {
			return null;
		}

		T deletedItem = head.data;
		head = head.next;

		if (head != null) {
			head.previous = null;
		}

		return deletedItem;
	}

	@Override
	public T deleteFromPosition(int position) {
		Node current = head;
		T deletedItem = null;
		int index = 0;

		if (current == null) {
			return null;
		}

		while (index < position && current.next != null) {
			current = current.next;
			index++;
		}

		if (index != position) {
			return null;
		}

		deletedItem = current.data;

		if (current.previous == null) {
			head = current.next;

			if (head != null) {
				head.previous = null;
			}
		} else {
			current.previous.next = current.next;

			if (current.next != null) {
				current.next.previous = current.previous;
			}
		}

		return deletedItem;
	}

	@Override
	public T deleteFromEnd() {
		Node current = head;
		T deletedItem = null;

		if (current == null) {
			return null;
		}

		while (current.next != null) {
			current = current.next;
		}

		deletedItem = current.data;

		if (current.previous == null) {
			head = null;
		} else {
			current.previous.next = null;
		}

		return deletedItem;
	}

	@Override
	public void printList() {
		Node current = head;

		while (current != null) {
			System.out.println(current.data);
			current = current.next;
		}
	}

}

package com.theaconitedev;

public class CircularLinkedList<T extends Comparable<T>> implements ILinkedList<T> {

	private Node sentinel;

	private class Node {
		public Node previous;
		public T data;
		public Node next;

		public Node(T data) {
			this.data = data;
		}
	}

	public CircularLinkedList() {
		sentinel = new Node(null);
	}

	@Override
	public void insertAtStart(T item) {
		Node node = new Node(item);

		if (sentinel.next != null) {
			sentinel.next.previous = node;
		}

		node.next = sentinel.next;
		node.previous = sentinel;
		sentinel.next = node;

		if (node.next == null) {
			node.next = sentinel;
		}

		if (sentinel.previous == null) {
			sentinel.previous = node;
		}
	}

	@Override
	public void insertAt(T item, int position) {
		if (sentinel.next == null) {
			insertAtStart(item);
			return;
		}

		Node current = sentinel.next;
		int index = 0;

		while (index < position && current.next != sentinel) {
			current = current.next;
			index++;
		}

		if (index == position) {
			Node node = new Node(item);

			node.next = current;
			node.previous = current.previous;
			current.previous.next = node;
			current.previous = node;
		} else {
			insertAtEnd(item);
		}
	}

	@Override
	public void insertAtEnd(T item) {
		if (sentinel.next == null) {
			insertAtStart(item);
			return;
		}

		Node node = new Node(item);

		sentinel.previous.next = node;
		node.previous = sentinel.previous;
		node.next = sentinel;
		sentinel.previous = node;
	}

	@Override
	public boolean contains(T item) {
		Node current = sentinel.next;

		while (current != sentinel) {
			if (current.data.compareTo(item) == 0) {
				return true;
			}

			current = current.next;
		}

		return false;
	}

	@Override
	public T deleteFromStart() {
		if (sentinel.next == null) {
			return null;
		}

		Node deletedNode = sentinel.next;
		sentinel.next = sentinel.next.next;

		if (sentinel.next == sentinel) {
			sentinel.next = null;
			sentinel.previous = null;
		}

		return deletedNode.data;
	}

	@Override
	public T deleteFromPosition(int position) {
		if (sentinel.next == null) {
			return null;
		}

		Node current = sentinel.next;
		int index = 0;

		while (index < position && current.next != sentinel) {
			current = current.next;
			index++;
		}

		if (index != position) {
			return null;
		}

		if (current.next == sentinel) {
			return deleteFromEnd();
		} else if (current.previous == sentinel) {
			return deleteFromStart();
		} else {
			current.previous.next = current.next;
			current.next.previous = current.previous;

			return current.data;
		}
	}

	@Override
	public T deleteFromEnd() {
		if (sentinel.next == null) {
			return null;
		}

		Node deletedNode = sentinel.previous;
		deletedNode.previous.next = sentinel;
		sentinel.previous = deletedNode.previous;

		if (sentinel.next == sentinel) {
			sentinel.next = null;
			sentinel.previous = null;
		}

		return deletedNode.data;
	}

	@Override
	public void printList() {
		Node current = sentinel.next;

		while (current != sentinel) {
			System.out.println(current.data);
			current = current.next;
		}
	}

}

package com.theaconitedev;

public class LinkedListImplementation {

	public static void main(String[] args) {
		System.out.println("== Singly Linked List ==");
		operateOnList(new SinglyLinkedList<String>());

		System.out.println("\n== Doubly Linked List ==");
		operateOnList(new DoublyLinkedList<String>());

		System.out.println("\n== Circular Linked List ==");
		operateOnList(new CircularLinkedList<String>());
	}

	public static void operateOnList(ILinkedList<String> list) {
		System.out.println("[Inserting Tony at start]");
		list.insertAtStart("Tony");
		System.out.println("[Current list state]");
		list.printList();

		System.out.println("[Inserting Steve at start]");
		list.insertAtStart("Steve");
		System.out.println("[Current list state]");
		list.printList();

		System.out.println("[Inserting Natasha at end]");
		list.insertAtEnd("Natasha");
		System.out.println("[Current list state]");
		list.printList();

		System.out.println("[Inserting Bruce at position 2 (0 based index)]");
		list.insertAt("Bruce", 2);
		System.out.println("[Current list state]");
		list.printList();

		System.out.println("[Searching for Natasha in list]");
		System.out.println(String.format("%s Natasha", list.contains("Natasha") == true ? "Found" : "Can't find"));

		System.out.println("[Searching for Clint in list]");
		System.out.println(String.format("%s Clint", list.contains("Clint") == true ? "Found" : "Can't find"));

		System.out.println("[Deleting from start]");
		list.deleteFromStart();
		System.out.println("[Current list state]");
		list.printList();

		System.out.println("[Deleting from 1 position]");
		list.deleteFromPosition(1);
		System.out.println("[Current list state]");
		list.printList();

		System.out.println("[Deleting from end]");
		list.deleteFromEnd();
		System.out.println("[Current list state]");
		list.printList();
	}

}

Output

== Singly Linked List ==
[Inserting Tony at start]
[Current list state]
Tony
[Inserting Steve at start]
[Current list state]
Steve
Tony
[Inserting Natasha at end]
[Current list state]
Steve
Tony
Natasha
[Inserting Bruce at position 2 (0 based index)]
[Current list state]
Steve
Tony
Bruce
Natasha
[Searching for Natasha in list]
Found Natasha
[Searching for Clint in list]
Can't find Clint
[Deleting from start]
[Current list state]
Tony
Bruce
Natasha
[Deleting from 1 position]
[Current list state]
Tony
Natasha
[Deleting from end]
[Current list state]
Tony

== Doubly Linked List ==
[Inserting Tony at start]
[Current list state]
Tony
[Inserting Steve at start]
[Current list state]
Steve
Tony
[Inserting Natasha at end]
[Current list state]
Steve
Tony
Natasha
[Inserting Bruce at position 2 (0 based index)]
[Current list state]
Steve
Tony
Bruce
Natasha
[Searching for Natasha in list]
Found Natasha
[Searching for Clint in list]
Can't find Clint
[Deleting from start]
[Current list state]
Tony
Bruce
Natasha
[Deleting from 1 position]
[Current list state]
Tony
Natasha
[Deleting from end]
[Current list state]
Tony

== Circular Linked List ==
[Inserting Tony at start]
[Current list state]
Tony
[Inserting Steve at start]
[Current list state]
Steve
Tony
[Inserting Natasha at end]
[Current list state]
Steve
Tony
Natasha
[Inserting Bruce at position 2 (0 based index)]
[Current list state]
Steve
Tony
Bruce
Natasha
[Searching for Natasha in list]
Found Natasha
[Searching for Clint in list]
Can't find Clint
[Deleting from start]
[Current list state]
Tony
Bruce
Natasha
[Deleting from 1 position]
[Current list state]
Tony
Natasha
[Deleting from end]
[Current list state]
Tony