A linked list is a collection of linear items. Unlike an array, the elements in the linked list are not stored in contiguous memory locations. Instead, they are linked to one another in a linear fashion. So, this helps to store the dynamic number of data elements.
Insertion and deletion operations work faster by simply interchanging the links. Therefore it is a wise choice to use the Linked List for applications that require frequent insertion/deletion operations. In addition, a linked list is also a foundation for implementing other data structures, such as Stack, Queue, Heap, Hash, Tree, Graph, etc.,
1. Representation
Properties
- Head: The starting point of the Linked List points to the first node.
- Node: Consists of data elements and links.
- Dynamic length: Accommodates the dynamic number of elements.
- Non Continuous memory: Physically not stored in a contiguous memory location in RAM, but the elements are linked to one another.
2. Types of Linked List
The linked list can be categorized as follows based on the method used to link the elements.
2.1. Singly Linked List
Every node consists of a data element and a link to the next node. The singly linked allows traversal only in the forward direction since it does not have the link to its previous node.
2.2. Doubly Linked List
Every node consists of a data element, a link to its previous node, and a link to its next node. So, this allows both forward and backward traversals with a doubly linked list.
2.3. Circular Singly Linked List
In a circular linked list, the last node and the first nodes are connected. This allows performing the circular traversal on data elements.
2.4. Circular Doubly Linked List
A circular linked list can be either singly or doubly based on the links. So, in the circular-doubly linked list, we have links to the previous nodes.
3. Linked List Operations
| Operation | Short Description | Time Complexity (worst) | Space Complexity (worst) |
|---|---|---|---|
| Search | Search the element in the Linked List. A sequential traversal is required to find the element. | O(n) | O(1) |
| Insert | Insert the new node into the Linked List. A new node is inserted directly by setting the links so that it works in O(1) time. | O(1) | O(1) |
| Delete | Delete the node from the Linked List. A node can be removed by simply disconnecting the links so that it works in O(1) time. | O(1) | O(1) |
4. Advantages/Disadvantages
Advantages
- Dynamic in size unlike Array.
- Faster insertion and deletion operations since it has links.
Disadvantages
- Random access to an element is not possible. So, we need to perform the linear traversal.
- Additional memory is required to store the links.
- Also, Non-contiguous memory makes no cache friendly for the CPU.
5. Applications
- Redo and Undo operations use the Singly Linked List.
- Implement the Stack and Queue data structures.
- Also used in Hash Table to prevent the collision.
6. References
- std::forward_list – C++ standard library for the singly linked list.
- std::list – C++ standard library for the doubly linked list.