DEV Community

Cover image for Data Structures and Algorithms: Linked Lists
Farai Bvuma
Farai Bvuma

Posted on

Data Structures and Algorithms: Linked Lists

A linked list is a data structure that consists of a chain of nodes, where each node contains some data and a pointer to the next node in the list.

Linked List Node

The first node in a linked list is referred to as the Head whilst the last node is referred to as the Tail. We can reference the position of each node in a linked list similarly to the way we reference position in arrays, where the Head has an index of zero. The tail of a linked list always points to null.

The example below shows a simple linked list containing integers.
Simple linked list

It is worth noting that each node will only reference the following node, and not the node(s) that came before it. This means that a linked list can only be transversed in one direction.

Advantages

  • Elements can be easily added or removed without reorganising the entire structure.
  • Dynamic size, that is to say that the linked list can grow or shrink on demand.
  • No wasted memory at run time, as only the amount of memory for the nodes will be used, increasing or decreasing as necessary.

Disadvantages

  • Random access is not feasible as one would have to traverse the linked list from the beginning whenever one wants to find a specific node.
  • Searching a linked list can be time consuming, having linear time complexity: O(n).
  • Traversal is only possible in one direction

Top comments (0)