by Linked List is a data structure used for storing collection of data where successive elements are connected through pointers and the size of linked list can grow or shrink dynamically. In short, Linked list can be thought as similar to array in which traversal can happen through pointers instead of indexes.
Properties of Linked list
- Last element points to NULL.
- Size can grow or shrunk dynamically.
- Memory can be allocated whenever it’s needed.
Advantages of Linked List
- Linked list can grow until system memory exhausts and growing cost is constant. In case of array, once array size exhausts then a bigger array needs to allocate and older array values needs to copied into this bigger newer arrays which can take lot of time.
- Memory wastage is quite low. In case of array, lot of memory is wasted as we allocate memory at the beginning itself for the whole program period.
- Linked list can be used as a building block for other data structures such as Queues, Stacks, Graphs etc.
Disadvantages of Linked List
- Access time to a element is the biggest drawback of Linked list. Since each element is dynamically allocated and only connected via pointers, hence for accessing a particular element requires traversal of linked list from start to the specific node which is costlier than arrays.
- Each element needs to store one extra pointer in order to point to the next element in the linked list. This memory is overhead which is not needed in case of arrays.
Comparison of Linked List vs Arrays vs Dynamic Arrays
| Parameter | Linked List | Array | Dynamic Array |
| Access time | O(n) | O(1) | O(1) |
| Insertion | O(n) | O(1) | O(1) |
| Deletion | O(n) | O(1) | O(1) |
| Memory Allocation | Heap | Stack | Heap |
Types of Linked List
Singly Linked List
This is the most common Linked list in which every node/element has a next pointer which points to the next node/element in the linked list. Last node of this linked list points to NULL. A simple representation is shown in below picture.
Doubly Linked List
In this linked list every node/element has one next pointer which points to the next node/element in the linked list and one previous pointer which points to the previous node/element in the linked list. A simple representation is shown in below picture.
Advantages of Doubly Linked List
Deletion of a node is comparatively easy as prev node address is stored in the the node along with next node address. In Singly linked list, we need to traverse the list in order to find the previous node of the node which needs
to be deleted.
Disadvantages of Doubly Linked List
- More spaces needed as we are storing one extra previous pointer per node.
- Extra pointer manipulation needed for insertion/deletion of a node.
Important Linked List Topics
- Linked list basic implementation.
- Linked list Insert Operation
- Linked list Search and Traverse Operation
- Linked list Delete Operation
- Linked list Reversal
- Linked list Length calculation
- Linked list Nth node from the end
- Linked list Detect and Remove loop
- Linked list swap two nodes
- Linked list swap k nodes
- Intersection of Two Linked Lists
- Linked List Palindrome
