Linked List is a linear data structure consisting of a collection of nodes which are stored in separated physical memory locations
There are multiple types of Linked List. In this article, we will learn about the singly and doubly linked list. We will also implement some Linked List common operations including
Traversal: traverse all elements in a Linked List
Add First and Add Last: add a new element into the head and the tail of a Linked List
Remove First and Remove Last: remove the first and last element of a Linked List
We can manage a Linked List by using only the head node or using both head and tail nodes to reduce the time complexity of Add Last and Remove Last operations
Singly Linked List
Each node in a singly linked list comprises two parts, the data and the pointer which is linked to the next node. The next pointer of the tail node is linked to null
In Java, the node object of a singly linked list can be represented as below
class Node {
public int data;
public Node next;
public Node(int data) {
this.data = data;
}
}
The type of data variable can be any. The type of next variable has to be the class itself
The following example is a singly linked list implementation in Java. The linked list is managed via a head node
public class MyLinkedList {
Node head;
public void addFirst(int data) {
if (head == null) {
head = new Node(data);
return;
}
Node newNode = new Node(data);
newNode.next = this.head;
this.head = newNode;
}
public void addLast(int data) {
if (head == null) {
head = new Node(data);
return;
}
Node currentNode = this.head;
while (currentNode.next != null) {
currentNode = currentNode.next;
}
currentNode.next = new Node(data);
}
public void removeFirst() {
if (this.head == null) return;
this.head = this.head.next;
}
public void removeLast() {
if (this.head == null) return;
if (this.head.next == null) {
this.head = null;
return;
}
Node currentNode = this.head;
while (currentNode.next.next != null) {
currentNode = currentNode.next;
}
currentNode.next = null;
}
public void traversal() {
Node currentNode = this.head;
while (currentNode != null) {
System.out.printf("%d ", currentNode.data);
currentNode = currentNode.next;
}
System.out.println();
}
public static void main(String[] args) {
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addLast(2);
myLinkedList.addLast(6);
myLinkedList.addFirst(9);
System.out.println("Traverse all elements");
myLinkedList.traversal();
System.out.println("Remove the first node");
myLinkedList.removeFirst();
myLinkedList.traversal();
System.out.println("Remove the last node");
myLinkedList.removeLast();
myLinkedList.traversal();
}
static class Node {
public int data;
public Node next;
public Node(int data) {
this.data = data;
}
}
}
Output
Traverse all elements
9 2 6
Remove the first node
2 6
Remove the last node
2
Time complexity
Operation Time complexity
--------------------------------
Traversal O(n)
Add first O(1)
Add last O(n)
Remove first O(1)
Remove last O(n)
Doubly Linked List
Each node in a doubly linked list comprises three parts, the data and two pointers in which one is linked to previous node and the other is linked to next node. The previous pointer of the head node is linked to null while the next pointer of the tail node is linked to null
In Java, the node object of a doubly linked list can be represented as below
static class Node {
public int data;
public Node previous;
public Node next;
public Node(Node previous, int data, Node next) {
this.previous = previous;
if (previous != null) previous.next = this;
this.data = data;
this.next = next;
if (next != null) next.previous = this;
}
}
The type of data variable can be any. The type of previous and next variable has to be the class itself
The following example is a doubly linked list implementation in Java. The linked list is managed via both head and tail nodes to reduce the time complexity of Add and Remove Last operations
public class MyDoublyLinkedList {
Node head;
Node tail;
public void addFirst(int data) {
Node newNode = new Node(null, data, this.head);
this.head = newNode;
if(this.tail == null) this.tail = this.head;
}
public void addLast(int data) {
Node newNode = new Node(this.tail, data, null);
this.tail = newNode;
if(this.head == null) this.head = this.tail;
}
public void removeFirst() {
if (this.head == null) return;
this.head = this.head.next;
if (this.head == null) this.tail = null;
this.head.previous = null;
}
public void removeLast() {
if (this.head == null) return;
if (this.head.next == null) {
this.head = null;
this.tail = null;
return;
}
Node beforeTail = this.tail.previous;
beforeTail.next = null;
this.tail = beforeTail;
}
public void traversal() {
Node currentNode = this.head;
while (currentNode != null) {
System.out.printf("%d ", currentNode.data);
currentNode = currentNode.next;
}
System.out.println();
}
public static void main(String[] args) {
MyDoublyLinkedList myLinkedList = new MyDoublyLinkedList();
myLinkedList.addLast(2);
myLinkedList.addLast(6);
myLinkedList.addFirst(9);
System.out.println("Traverse all elements");
myLinkedList.traversal();
System.out.println("Remove the first node");
myLinkedList.removeFirst();
myLinkedList.traversal();
System.out.println("Remove the last node");
myLinkedList.removeLast();
myLinkedList.traversal();
}
static class Node {
public int data;
public Node previous;
public Node next;
public Node(Node previous, int data, Node next) {
this.previous = previous;
if (previous != null) previous.next = this;
this.data = data;
this.next = next;
if (next != null) next.previous = this;
}
}
}
Output
Traverse all elements
9 2 6
Remove the first node
2 6
Remove the last node
2
Time complexity
Operation Time complexity
--------------------------------
Traversal O(n)
Add first O(1)
Add last O(1)
Remove first O(1)
Remove last O(1)