LINKED LIST
A linked list is a linear data structure that consists of a
sequence of elements, called nodes, each of which contains two components: the
data part and a reference (or pointer) to the next node in the sequence. The
last node points to `null`, signifying the end of the list.
Why Use Linked Lists?
Linked lists offer several advantages over arrays,
particularly in scenarios where:
- Dynamic Size: Unlike arrays, linked lists do not require a predefined size, allowing them to grow and shrink dynamically as elements are added or removed.
- Efficient Insertions/Deletions: Linked lists enable easy insertion and deletion of elements without the need to shift elements, as is necessary in arrays. This is because elements in a linked list are not stored in contiguous memory locations.
- Memory Allocation: Linked lists allocate memory as needed, making them memory-efficient, especially for unpredictable workloads.
Types of Linked Lists
- Linked lists come in various forms, each with its own characteristics:
- Singly Linked List: Each node points to the next node, with the last node pointing to `null`.
- Doubly Linked List: Each node contains pointers to both the next and the previous nodes, allowing traversal in both directions.
- Circular Singly Linked List: The last node points back to the first node, forming a circle.
- Circular Doubly Linked List: Similar to the doubly linked list, but with the last node pointing back to the first node and the first node pointing to the last node.
Advantages of Linked Lists
- Dynamic Data Structure: The size of a linked list can vary according to the needs of the program.
- Easy Insertion/Deletion: No need to shift elements as in arrays.
- Memory Efficient: Memory is allocated only as needed.
Disadvantages of Linked Lists
- Memory Usage: Linked lists require extra memory for storing pointers.
- Traversal: Accessing elements is slower since nodes must be traversed sequentially.
- Reverse Traversal: Difficult in singly linked lists; easier in doubly linked lists but at the cost of additional memory.
Applications of Linked Lists
- Polynomial Representation: Useful for operations on polynomials.
- Sparse Matrices: Can represent sparse matrices efficiently.
- Dynamic Memory Allocation: Used in dynamic memory allocation systems.
- Data Structures: Implementation of stacks, queues, trees, and graphs.
Operations on Linked Lists
- Insertion: Adding a new node.
- Deletion: Removing a node.
- Display: Showing the elements of the list.
- Search: Finding a node with a specific key.
Complexity of Linked Lists
- Time Complexity: Insertion and deletion operations have O(1) time complexity, while search operations have O(n) time complexity.
- Space Complexity: The space complexity for storing a linked list is O(n), where n is the number of nodes.