The main types of linked lists include:
Singly Linked List:
In a singly linked list, each node contains data and a single reference (pointer) to the next node in the sequence.
- They are simple to implement and require less memory overhead compared to doubly linked lists.
- Traversal in a singly linked list is only possible in the forward direction.
Below is a Java implementation of a singly linked list:
public class SinglyLinkedList {
private static class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
private Node head;
public SinglyLinkedList() {
this.head = null;
}
public void add(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
} else {
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}
}
public void display() {
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
public static void main(String[] args) {
SinglyLinkedList list = new SinglyLinkedList();
list.add(1);
list.add(2);
list.add(3);
list.display(); // Output: 1 2 3
}
}OUTPUT:
1 2 3 Doubly Linked List:
In a doubly linked list, each node contains data and two references (pointers): one to the next node and one to the previous node in the sequence.
- It allows for traversal in both forward and backward directions, making operations like deletion of the last node more efficient compared to singly linked lists.
- It consumes more memory compared to singly linked lists due to the additional pointers.
Below is a Java implementation of a doubly linked list:
public class DoublyLinkedList {
private static class Node {
int data;
Node prev;
Node next;
Node(int data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
private Node head;
private Node tail;
public DoublyLinkedList() {
this.head = null;
this.tail = null;
}
public void add(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
tail = newNode;
} else {
tail.next = newNode;
newNode.prev = tail;
tail = newNode;
}
}
public void displayForward() {
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
public void displayBackward() {
Node current = tail;
while (current != null) {
System.out.print(current.data + " ");
current = current.prev;
}
System.out.println();
}
public static void main(String[] args) {
DoublyLinkedList list = new DoublyLinkedList();
list.add(1);
list.add(2);
list.add(3);
System.out.println("Forward:");
list.displayForward();
System.out.println("Backward:");
list.displayBackward();
}
}OUTPUT:
Forward: 1 2 3
Backward: 3 2 1 Circular Linked List:
In a circular linked list, the last node points back to the first node, forming a circular structure.
- It can be singly or doubly linked. In a singly circular linked list, each node has a single pointer to the next node, and the last node points back to the first node. In a doubly circular linked list, each node has both forward and backward pointers, and the last node points to the first node, and the first node points to the last node.
- They are useful in applications where the list needs to be traversed repeatedly or where elements need to be rotated cyclically.
Below is a Java implementation of a circular linked list:
public class CircularLinkedList {
private static class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
private Node head;
public CircularLinkedList() {
this.head = null;
}
public void add(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
head.next = head; // Point to itself to create circularity
} else {
Node current = head;
while (current.next != head) {
current = current.next;
}
current.next = newNode;
newNode.next = head; // Make the new node point to the head to complete the circle
}
}
public void display() {
if (head == null) {
System.out.println("List is empty");
return;
}
Node current = head;
do {
System.out.print(current.data + " ");
current = current.next;
} while (current != head);
System.out.println();
}
public static void main(String[] args) {
CircularLinkedList list = new CircularLinkedList();
list.add(1);
list.add(2);
list.add(3);
list.display();
}
}OUTPUT:
1 2 3 Doubly Circular Linked List:
- A Doubly Circular Linked List is a variation of a doubly linked list where the last node’s next pointer points back to the first node (head), creating a circular structure.
- Additionally, the previous pointer of the first node (head) points to the last node. This circular arrangement allows for traversal in both forward and backward directions.
Below is a Java implementation of a doubly linked list:
public class DoublyCircularLinkedList {
private static class Node {
int data;
Node prev;
Node next;
Node(int data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
private Node head;
public DoublyCircularLinkedList() {
this.head = null;
}
public void add(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
head.prev = head;
head.next = head;
} else {
Node lastNode = head.prev;
lastNode.next = newNode;
newNode.prev = lastNode;
newNode.next = head;
head.prev = newNode;
}
}
public void displayForward() {
if (head == null) {
System.out.println("List is empty");
return;
}
Node current = head;
do {
System.out.print(current.data + " ");
current = current.next;
} while (current != head);
System.out.println();
}
public void displayBackward() {
if (head == null) {
System.out.println("List is empty");
return;
}
Node current = head.prev;
do {
System.out.print(current.data + " ");
current = current.prev;
} while (current != head.prev);
System.out.println();
}
public static void main(String[] args) {
DoublyCircularLinkedList list = new DoublyCircularLinkedList();
list.add(1);
list.add(2);
list.add(3);
System.out.println("Forward:");
list.displayForward(); // Output: 1 2 3
System.out.println("Backward:");
list.displayBackward(); // Output: 3 2 1
}
}OUTPUT:
Forward: 1 2 3
Backward: 3 2 1 
