Types of Linked Lists
Depending on how the nodes are connected, linked lists are classified into three types:
A. Singly Linked List
A Singly Linked List is the simplest type of linked list. In this structure, each node contains data and a reference (pointer) to the next node in the sequence. The last node points to null, indicating the end of the list. 
Key Characteristics:
- Unidirectional: You can only traverse the list in one direction (Head $\to$ Tail). You cannot go back to the previous node.
- Memory Efficient: It requires less memory per node compared to a doubly linked list because it only stores one pointer.
Code Node Structure
As seen in your Stack implementation, the node for a singly linked list is defined with just data and next : class Node {
int data;
Node next; // Reference to the next node
public Node(int data) {
this.data = data;
this.next = null; // Ends with null by default
}
}
class Node:
def __init__(self, data):
self.data = data
self.next = None # Reference to the next node
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next; // Reference to the next node
};
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL; // Ends with NULL by default
return newNode;
}
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node* next; // Reference to the next node
Node(int data) {
this->data = data;
this->next = NULL; // Ends with null by default
}
};
- Navigation: Forward only.
- Memory: Uses less memory (only one pointer per node).
- Analogy: A conga line where everyone holds the waist of the person in front.
B. Doubly Linked List
A Doubly Linked List is a more complex structure where each node contains three parts instead of two. It allows traversal in both directions.
Node Architecture:
- Prev: A pointer to the previous node.
- Data: The value stored.
- Next: A pointer to the next node.
Code Implementation
The Node class expands to include the prev pointer. class DoublyNode {
int data;
DoublyNode next;
DoublyNode prev; // New pointer for backward navigation
public DoublyNode(int data) {
this.data = data;
this.next = null;
this.prev = null;
}
}
public class DoublyLinkedList {
DoublyNode head;
// Insert at the beginning
public void push(int data) {
DoublyNode newNode = new DoublyNode(data);
newNode.next = head; // 1. New node points to current head
newNode.prev = null; // 2. New node's prev is null (it's new head)
if (head != null) {
head.prev = newNode; // 3. Old head's prev points to new node
}
head = newNode; // 4. Update head
}
}
class DoublyNode:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None # Pointer for backward navigation
class DoublyLinkedList:
def __init__(self):
self.head = None
# Insert at the beginning
def push(self, data):
newNode = DoublyNode(data)
newNode.next = self.head # 1. New node points to current head
newNode.prev = None # 2. New node's prev is None
if self.head is not None:
self.head.prev = newNode # 3. Old head's prev points to new node
self.head = newNode # 4. Update head
#include <stdio.h>
#include <stdlib.h>
struct DoublyNode {
int data;
struct DoublyNode* next;
struct DoublyNode* prev; // Pointer for backward navigation
};
struct DoublyNode* head = NULL;
// Insert at the beginning
void push(int data) {
struct DoublyNode* newNode = (struct DoublyNode*)malloc(sizeof(struct DoublyNode));
newNode->data = data;
newNode->next = head; // 1. New node points to current head
newNode->prev = NULL; // 2. New node's prev is NULL
if (head != NULL) {
head->prev = newNode; // 3. Old head's prev points to new node
}
head = newNode; // 4. Update head
}
#include <iostream>
using namespace std;
class DoublyNode {
public:
int data;
DoublyNode* next;
DoublyNode* prev; // Pointer for backward navigation
DoublyNode(int data) {
this->data = data;
this->next = NULL;
this->prev = NULL;
}
};
class DoublyLinkedList {
public:
DoublyNode* head;
DoublyLinkedList() {
head = NULL;
}
// Insert at the beginning
void push(int data) {
DoublyNode* newNode = new DoublyNode(data);
newNode->next = head; // 1. New node points to current head
newNode->prev = NULL; // 2. New node's prev is NULL
if (head != NULL) {
head->prev = newNode; // 3. Old head's prev points to new node
}
head = newNode; // 4. Update head
}
};
Advantages vs. Disadvantages
- Pros: Can traverse both ways. Deletion is easier because you have access to the previous node immediately.
- Cons: Consumes more memory (extra pointer). Code is slightly more complex to maintain (must update two pointers for every insertion/deletion).
Real-Life Analogy
Web Browser History: You can click “Back” to go to the previous page (prev pointer) or “Forward” to go to the next page (next pointer). The browser maintains a link in both directions.
C. Circular Linked List
A Circular Linked List is a variation where the list has no end. The last node’s next pointer, instead of pointing to null, points back to the Head (first node). This forms a continuous loop. 
Types of Circular Lists:
- Circular Singly Linked List: Simple nodes, but the tail connects to the head.
- Circular Doubly Linked List: Doubly nodes, where tail connects to head and head connects to tail.
Code Logic (Singly Circular)
Notice that we never set next to null.public class CircularLinkedList {
Node head = null;
Node tail = null;
public void add(int data) {
Node newNode = new Node(data);
if (head == null) {
// If list is empty, point head to new node
head = newNode;
tail = newNode;
newNode.next = head; // Point back to itself
} else {
// Standard insertion
tail.next = newNode; // Old tail points to new node
tail = newNode; // Update tail
tail.next = head; // **CRITICAL**: New tail points back to Head
}
}
// Traversal requires a do-while loop to avoid infinite loops
public void display() {
if (head == null) return;
Node current = head;
do {
System.out.print(current.data + " -> ");
current = current.next;
} while (current != head); // Stop when we return to start
System.out.println("(Head)");
}
}
class Node:
def __init__(self, data):
self.data = data
self.next = None
class CircularLinkedList:
def __init__(self):
self.head = None
self.tail = None
def add(self, data):
newNode = Node(data)
if self.head is None:
# If list is empty
self.head = newNode
self.tail = newNode
newNode.next = self.head # Point back to itself
else:
# Standard insertion
self.tail.next = newNode
self.tail = newNode
self.tail.next = self.head # New tail points back to head
def display(self):
if self.head is None:
return
current = self.head
while True:
print(current.data, "->", end=" ")
current = current.next
if current == self.head:
break
print("(Head)")
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
struct Node* head = NULL;
struct Node* tail = NULL;
void add(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
if (head == NULL) {
// If list is empty
head = newNode;
tail = newNode;
newNode->next = head;
}
else {
tail->next = newNode;
tail = newNode;
tail->next = head;
}
}
void display() {
if (head == NULL) return;
struct Node* current = head;
do {
printf("%d -> ", current->data);
current = current->next;
} while (current != head);
printf("(Head)\n");
}
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int data) {
this->data = data;
this->next = NULL;
}
};
class CircularLinkedList {
public:
Node* head = NULL;
Node* tail = NULL;
void add(int data) {
Node* newNode = new Node(data);
if (head == NULL) {
// If list is empty
head = newNode;
tail = newNode;
newNode->next = head;
}
else {
tail->next = newNode;
tail = newNode;
tail->next = head;
}
}
void display() {
if (head == NULL) return;
Node* current = head;
do {
cout << current->data << " -> ";
current = current->next;
} while (current != head);
cout << "(Head)" << endl;
}
};
Real-Life Analogy
- Monopoly Board Game: The board is a continuous loop. After the last space (Boardwalk), you move right back to the first space (Go).
- Music Playlist (Repeat All): When the last song finishes, the player automatically starts the first song again.
Comparison Table for Your Course
| Feature | Singly Linked List | Doubly Linked List | Circular Linked List |
| Direction | Forward Only | Forward & Backward | Forward (Loops back) |
| Memory | Low (1 pointer) | High (2 pointers) | Low (1 pointer) |
| Insertion | Fast | Moderate (more pointers to update) | Fast |
| End of List | Points to null | Points to null | Points to Head |
| Best Use | Simple stacks/queues | Music players, Undo/Redo | CPU Scheduling, Games |