✅ Types of Linked Lists

---

✅ 1. Introduction

A Linked List is a dynamic linear data structure made up of nodes, where each node contains data and one or more links (pointers) to other nodes.
Based on how these nodes are connected, linked lists are classified into different types.

---

✅ 2. Types of Linked Lists

The main types of linked lists are:

1. Singly Linked List
2. Doubly Linked List
3. Circular Linked List
4. Circular Doubly Linked List

---

✅ 3. Singly Linked List

✅ Definition

A Singly Linked List is a linked list in which each node contains:

• Data part
• One pointer pointing to the next node

📌 The last node points to NULL, which indicates the end of the list.

---

✅ Representation

HEAD → [Data|Next] → [Data|Next] → [Data|NULL]

---

✅ Node Structure (C)

struct node
{
   int data;
   struct node *next;
};

---

✅ Features

• Traversal is possible only in one direction
• Requires less memory than doubly linked list
• Simple to implement

---

✅ Advantages

1. Dynamic size
2. Efficient insertion and deletion
3. No need for contiguous memory

---

❌ Disadvantages

1. Cannot traverse backward
2. Searching is slow
3. No direct access

---

✅ Applications

• Stack implementation
• Queue implementation
• Polynomial representation

---

✅ 4. Doubly Linked List

✅ Definition

A Doubly Linked List is a linked list in which each node contains:

• Data part
• Two pointers:
  • prev → address of previous node
  • next → address of next node

---

✅ Representation

NULL ← [Prev|Data|Next] ↔ [Prev|Data|Next] → NULL

---

✅ Node Structure (C)

struct dnode
{
   int data;
   struct dnode *prev;
   struct dnode *next;
};

---

✅ Features

• Traversal is possible in both directions
• More flexible than singly linked list

---

✅ Advantages

1. Easy backward traversal
2. Deletion is easier (no need to track previous node)
3. Useful for navigation systems

---

❌ Disadvantages

1. Requires extra memory
2. More complex than singly linked list

---

✅ Applications

• Browser forward/backward navigation
• Undo/Redo operations
• Music player (previous/next song)

---

✅ 5. Circular Linked List

✅ Definition

A Circular Linked List is a linked list in which the last node points back to the first node instead of pointing to NULL.

📌 There is no NULL pointer in circular linked list.

---

✅ Representation

HEAD → [Data|Next] → [Data|Next] → [Data|Next]
  ↑                                         ↓
  ←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←

---

✅ Node Structure

Same as singly linked list:

struct node
{
   int data;
   struct node *next;
};

---

✅ Features

• Traversal starts from any node
• Last node links to first node

---

✅ Advantages

1. No NULL pointer
2. Efficient for circular operations
3. Useful in round-robin scheduling

---

❌ Disadvantages

1. Complex traversal (need stopping condition)
2. Difficult to detect end of list

---

✅ Applications

• CPU scheduling (Round Robin)
• Multiplayer games
• Circular queues

---

✅ 6. Circular Doubly Linked List

✅ Definition

A Circular Doubly Linked List is a combination of:

• Doubly linked list
• Circular linked list

Each node has:

• prev pointer
• next pointer

And:

• Last node’s next points to first node
• First node’s prev points to last node

---

✅ Representation

      ↔ [Prev|Data|Next] ↔ [Prev|Data|Next] ↔
     ↑                                             ↓
     ←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←

---

✅ Advantages

1. Traversal in both directions
2. Efficient insertion and deletion
3. No NULL pointer

---

❌ Disadvantages

1. High memory usage
2. Complex implementation

---

✅ Applications

• Advanced scheduling systems
• Navigation systems
• Real-time applications

---

✅ 7. Comparison of Types of Linked Lists (Quick View)

Type	Pointers per Node	Traversal	Last Node
Singly Linked List	1	Forward only	Points to NULL
Doubly Linked List	2	Forward & Backward	Points to NULL
Circular Linked List	1	Circular Forward	Points to First Node
Circular Doubly Linked List	2	Circular Both Ways	Points to First Node

---

✅ Conclusion

Linked lists are classified based on how nodes are connected.

• Singly linked lists are simple and memory efficient.
• Doubly linked lists support two-way traversal.
• Circular linked lists eliminate NULL pointers and are useful for cyclic operations.
• Circular doubly linked lists provide maximum flexibility but need more memory.

---