Data Structures

Linked List: Types, Operations, and Applications

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

Linked List
Linked List
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.

  1. Singly Linked List
  2. Doubly Linked List
  3. Circular Singly Linked List
  4. Circular Doubly Linked List

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.

Singly Linked List Representation
Singly Linked List Representation

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.

Doubly Linked List Representation
Doubly Linked List Representation

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.

Circular Singly Linked List Representation
Circular Singly Linked List Representation

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.

Circular Doubly Linked List Representation
Circular Doubly Linked List Representation

3. Linked List Operations

OperationShort DescriptionTime
Complexity
(worst)
Space
Complexity
(worst)
SearchSearch the element in the Linked List. A sequential traversal is required to find the element.O(n)O(1)
InsertInsert 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)
DeleteDelete 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)
Time and Space Complexity of Linked List Operations

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.
Copyright copyright 2024 Simplerize