Home » Data Structure

Introduction to Linked List

Last Updated : November 24, 2025

What is linked list?

A linked list is a data structure used for storing data. A linked list has the following properties:

• Successive elements are connected by pointers.
• The last element points to NULL.
• Can grow or shrink in size during program execution.
• Can be made as long as needed. (Until system memory exhausts).
• Doesn’t waste memory space but takes some extra memory for pointers. It allocates memory as it grows.

Link list as an ADT

Link list is an ADT and has the following operations:

Main link list ADT operation:

1. Insert: Insert element to the list
2. Delete: deletes element from the list

Auxiliary link list ADT operations:

1. Delete list: delete and remove the whole list
2. Count: returns the number of elements in the list
3. Find n^th node: Returns the nth node from the beginning of the list

Why Link List?

There are so many data structure all serves the same purpose like link list. So it must come in mind that why link list, not the others.

Before discussing link list it’s necessary to differentiate link list and array. Both are used for same purpose, but we need to differentiate their usage, their operations. That means where using array is suitable and where linked list.

Comparison between array and linklist

Advantage of Arrays

• Simple and easy to use
• Faster access to elements (O (1))

Disadvantage of Arrays

• Wastage of memory as indices may be empty.
• Fixed size - Size of array is static.
• To insert an element at a given position, operation is complex. We may need to shift the existing elements to create vacancy to insert the new element at desired position.

However, problem arising for static array can be overcome through dynamic array.

Advantage of link lists

• Can be expanded at constant time, which is expensive for an array
• No wastage of memory
• Insertion at desired position is relatively easier that inserting in an array

Disadvantage of link lists

• The main disadvantage is that the access time for any single element in a link list is not constant like an array.
• Link list somehow needs additional code to be implemented.

Real-Life Examples of Linked List

Linked lists represent items connected in a sequence where each item points to the next.

• Train coaches connected one after another
• Music playlist where the next song plays automatically
• Chain of people standing in a queue
• Pages in a book connected by “next page” pointers in e-books
• Photo slideshow where each image links to the next
• Navigation steps in Google Maps (next location pointer)
• Browser history moving forward/backward like a doubly linked list
• Bus stops along a fixed route
• Files connected through blocks in a file system (like FAT)

Practical Use Cases of Linked List in Programming

Used when frequent insertions, deletions, or dynamic memory management is required.

• Implementing Stacks & Queues
  Linked lists allow fast insert/delete from head or tail.
• Undo/Redo Functionality in Editors
  Each action is a node linked to previous/next actions (doubly linked list).
• Dynamic Memory Allocation (Operating Systems)
  Free memory blocks are managed using a linked list (e.g., free list).
• Implementing Hash Tables (Chaining Method)
  Each bucket stores collisions using a linked list.
• Graph Adjacency List Representation
  Each node keeps a linked list of its connected nodes.
• Browser Forward/Backward Navigation
  Doubly linked list stores pages to move in both directions.
• Music Player Playlist Implementation
  Each song node points to the next song (circular list).
• Task Scheduling in OS
  Processes/threads are maintained in a linked list in queues.
• LRU Cache (Least Recently Used)
  Doubly linked list + hashmap for fast access and rearrangement.
• Image Viewer Slideshow
  Images linked sequentially for next/previous navigation.

Comparison between link list, array & dynamic array

Parameter	Link list	Array	Dynamic array
Indexing	O(N)	O(1)	O(1)
Insertion/deletion at beginning	O(1)	O(N)(array not full)	O(N)
Insertion at the end	O(N)	O(1)(array not full)	O(1)... array not full O(N)... array full
Deletion at the end	O(N)	O(1)	O(N)
Insertion in the middle	O(N)	O(N)(array not full)	O(N)
Deletion in the middle	O(N)	O(N)(array not full)	O(N)
Wasted space	For pointers	For empty indices	Depends on allocation