- \n
- Data<\/li>\n
- Pointer (reference to the next node)<\/li>\n<\/ul>
Unlike arrays, linked list elements are stored in different memory locations and connected using pointers.<\/p>
Example node structure:<\/strong><\/p>
\nstruct Node
\n{
\nint data;
\nstruct Node* next;
\n};<\/p>\n<\/div><\/div>Key characteristics:<\/strong><\/p>
- \n
- Dynamic size<\/li>\n
- Non continuous memory allocation<\/li>\n
- Pointer based structure<\/li>\n
- Efficient insertion and deletion<\/li>\n
- Sequential access of elements<\/li>\n<\/ul>
How Linked Lists Work Internally<\/h2>
A linked list works by connecting nodes through pointers. The first node is called the head, and the last node points to NULL, indicating the end of the list.<\/p>
Structure representation:<\/strong><\/p>
\nHead → Node → Node → Node → NULL<\/p>\n<\/div><\/div>
Each node stores:<\/strong><\/p>
- \n
- The actual data<\/li>\n
- Address of the next node<\/li>\n<\/ul>
Traversal happens by following the next pointer from one node to another.<\/p>
This structure allows linked lists to grow dynamically without needing continuous memory.<\/p>
Types of Linked Lists in Data Structure<\/h2>
1. Singly Linked List<\/h3>
Each node points only to the next node.<\/p>
Example structure:<\/strong><\/p>
\nNode → Node → Node → NULL<\/p>\n<\/div><\/div>
Used in:<\/strong><\/p>
- \n
- Simple data storage<\/li>\n
- Stack implementation<\/li>\n
- Basic traversal problems<\/li>\n<\/ul>
2. Doubly Linked List<\/h3>
Each node contains two pointers:<\/p>
- \n
- Previous pointer<\/li>\n
- Next pointer<\/li>\n<\/ul>
Structure:<\/strong><\/p>
\nNULL ← Node ↔ Node ↔ Node → NULL<\/p>\n<\/div><\/div>
Used in:<\/strong><\/p>
- \n
- Navigation systems<\/li>\n
- Undo\/redo operations<\/li>\n
- Browser history<\/li>\n<\/ul>
3. Circular Linked List<\/h3>
In circular linked lists, the last node points back to the first node instead of NULL.<\/p>
Structure:<\/strong><\/p>
\nNode → Node → Node → First Node<\/p>\n<\/div><\/div>
Used in:<\/strong><\/p>
- \n
- Round robin scheduling<\/li>\n
- Multiplayer games<\/li>\n
- Continuous processing systems<\/li>\n<\/ul>
4. Doubly Circular Linked List<\/h3>
A combination of doubly and circular linked lists where nodes have both previous and next pointers and form a loop.<\/p>
Used in:<\/strong><\/p>
- \n
- Advanced navigation systems<\/li>\n
- Complex memory structures<\/li>\n<\/ul>
Basic Linked List Operations with Coding Examples<\/h2>
1. Traversal<\/h3>
Traversal means visiting each node in the list.<\/p>
Example:<\/strong><\/p>
\nstruct Node* temp = head;<\/p>\n
while(temp != NULL)
\n{
\nprintf(“%d “, temp->data);
\ntemp = temp->next;
\n}<\/p>\n<\/div><\/div>2. Insertion<\/h3>
Insertion at beginning:<\/p>
\nnewNode->next = head;
\nhead = newNode;<\/p>\n<\/div><\/div>This operation takes O(1) time.<\/p>
3. Deletion<\/h3>
Deleting first node:<\/p>
\nhead = head->next;<\/p>\n<\/div><\/div>
Deletion updates pointers instead of shifting elements like arrays.<\/p>
4. Searching<\/h3>
Searching involves checking each node.<\/p>
\nwhile(temp != NULL)
\n{
\nif(temp->data == key)
\nprintf(“Found”);<\/p>\ntemp = temp->next;
\n}<\/p>\n<\/div><\/div>
![\"fsd](\"https:\/\/www.placementpreparation.io\/blog\/wp-content\/uploads\/2025\/06\/fsd-image-web-horizontal.webp\")
<\/a><\/p>