LINKED LIST
A linked list is a linear data structure where each element
(called a node) contains a data part and a reference (or link) to the next
element in the sequence. Unlike arrays, linked lists allow for efficient
insertion and deletion of elements because elements are not stored in
contiguous memory locations.
Types of Linked Lists
- Structure: Each node contains data and a reference to the next node.
- Traversal: Only forward traversal is possible.
- Example:
struct node {
int data;
struct node
*next;
};
- Usage: Commonly used when only forward traversal is needed.
2. Doubly Linked List:
- Structure: Each node contains data, a reference to the next node, and a reference to the previous node.
- Traversal: Allows both forward and backward traversal.
- Example:
struct node {
int data;
struct node
*next;
struct node
*prev;
};
- Usage: Useful when traversal in both directions is needed.
3. Circular Linked List:
- Structure: Similar to a singly linked list, but the last node's reference points to the first node, forming a circle.
- Traversal: Can start at any node and loop back to it.
- Example:
struct node {
int data;
struct node
*next;
};
- Usage: Used in scenarios where the list needs to be circular, such as in a round-robin scheduler.
4.Doubly Circular Linked List:
- Structure: Combines features of a doubly linked list and a circular linked list. The last node points to the first node, and the first node's previous reference points to the last node.
- Traversal: Allows bidirectional circular traversal.
- Example:
struct node {
int data;
struct node
*next;
struct node
*prev;
};
- Usage: Suitable for complex data structures that require circular and bidirectional traversal.
These different types of linked lists are suited for various programming scenarios, depending on the needs for traversal direction and memory usage.
