Linked List in C Programming
1. What is a Linked List?
A linked list is a linear data structure where each element (called a node) contains two parts:
- Data: The value stored in the node.
- Pointer (or link): A reference to the next node in the sequence.
Unlike arrays, linked lists do not store data in contiguous memory locations. Instead, each node points to the next, forming a chain-like structure.
2. Why Use a Linked List?
- Dynamic size: It grows or shrinks as needed.
- Efficient insertion/deletion: Especially at the beginning and middle of the list.
- No memory wastage: Uses only as much memory as needed.
3. Types of Linked Lists
A. Singly Linked List
Each node contains a single pointer to the next node. The last node points to NULL.
B. Doubly Linked List
Each node contains two pointers: one to the next node and one to the previous node. Allows bidirectional traversal.
C. Circular Linked List
The last node points back to the first node, forming a loop. Can be singly or doubly circular.
4. Basic Structure of a Linked List Node
In C, a typical singly linked list node is structured as:
struct Node {
int data;
struct Node* next;
};
This creates a self-referential structure.
5. Fundamental Operations on a Linked List
| Operation | Description |
|---|---|
| Insertion | Add a node at the beginning, end, or a specific position |
| Deletion | Remove a node from a specific position |
| Traversal | Visit all the nodes and display or process their data |
| Search | Find a node with a specific value |
| Count | Count the number of nodes |
6. Linked List vs Array
| Feature | Array | Linked List |
|---|---|---|
| Memory Allocation | Static | Dynamic |
| Insertion/Deletion | Costly (shifting elements) | Efficient (pointer updates) |
| Access Time | Fast (direct indexing) | Slower (sequential traversal) |
| Wastage of Memory | Possible (unused space) | Minimal |
7. Advantages of Linked Lists
- Dynamic size
- Efficient memory usage
- Fast insertions and deletions (compared to arrays)
8. Disadvantages of Linked Lists
- More memory per node due to the pointer field
- Slower access (no direct indexing)
- Complex pointer management
9. Common Use Cases
- Stacks and queues (can be easily implemented using linked lists)
- Symbol tables in compilers
- Memory management (e.g., free lists)
- Graph representations
A linked list is a powerful and flexible data structure that offers dynamic memory usage and efficient insertion and deletion operations. In C, it is implemented using structures and pointers. While linked lists require more complex pointer manipulation compared to arrays, they provide greater flexibility in memory management and real-time data operations.