Linked List in Data Structure: Types, Operations and Examples

Chapter 14 • Data Structure

Linked List in Data Structure: Types, Operations and Examples

Arrays are simple and fast when the amount of data is known in advance, but real programs do not always work with a fixed number of elements. Sometimes new data has to be inserted, old data has to be removed, and the structure needs to grow or shrink while the program is running.

A Linked List handles this situation differently from an array. Instead of keeping all elements together in one continuous block, it stores data inside separate nodes and connects those nodes using links.

Quick Answer: A Linked List is a linear data structure made of nodes. Each node stores data and one or more links that connect it with other nodes. Unlike an array, linked-list nodes do not need to occupy consecutive memory locations. Common types are Singly Linked List, Doubly Linked List and Circular Linked List.

What is a Linked List in Data Structure?

Linked List in Data Structure: Types, Operations and Examples

A Linked List is a collection of connected nodes.

Every node contains some useful data and a link that tells the program where the next node is located.

10 •
→
20 •
→
30 •
→ NULL

In this example, the list contains three nodes with values 10, 20 and 30.

The first node points to the second node, the second points to the third, and the final node points to NULL, which means that the list ends there.

Why Do We Need Linked Lists?

To understand why Linked Lists are useful, first compare them with arrays.

An array normally stores elements in consecutive memory locations. This is why array indexing and memory-address calculations can be performed efficiently. If you want to understand that memory layout in detail, read the earlier chapter on Array Address Calculation in Data Structure.

Linked Lists follow a different approach. Nodes can exist at different memory locations, and links connect them logically.

Array

Elements are usually stored in contiguous memory locations.

10 | 20 | 30 | 40

Linked List

Nodes may exist at different locations but remain connected through pointers.

10 → 20 → 30 → 40 → NULL

Structure of a Linked List Node

In a Singly Linked List, every node usually has two parts:

Basic Node
DATA LINK

1. Data Field

The data field stores the actual value that we want to keep in the list.

For example:

10, 25, "Sahil", Student Record, Product Data

2. Link / Pointer Field

The link field stores information that connects the current node with another node.

In a Singly Linked List, this normally points to the next node.

What is the Head Pointer?

A Linked List needs a way to know where it begins.

The reference to the first node is usually called HEAD.

HEAD →
5 •
→
12 •
→ NULL

If HEAD contains NULL, the Linked List is empty.

HEAD = NULL

Important Features of Linked List

Dynamic Size

Nodes can be created when required, so the list can grow or shrink during program execution.

Non-Contiguous Storage

Nodes do not need to occupy adjacent memory locations.

Link-Based Access

The next element is reached by following a link instead of calculating an array index.

Types of Linked List

The major Linked List types are:

1. Singly Linked List

Each node points only to the next node.

2. Doubly Linked List

Each node keeps links to both the previous and next nodes.

3. Circular Linked List

The final node connects back to the first node instead of pointing to NULL.

1. Singly Linked List

A Singly Linked List is the simplest Linked List type.

Each node contains:

  • data, and
  • a link to the next node.
A •
→
B •
→
C •
→ NULL

Movement normally happens in one direction:

A → B → C

We cannot directly move from C back to B unless we start again from the beginning or store additional information.

2. Doubly Linked List

A Doubly Linked List stores an extra link in every node.

Each node usually contains:

Previous Pointer | Data | Next Pointer
NULL ←
← 10 →
⇄
← 20 →
⇄
← 30 →
→ NULL

A Doubly Linked List allows traversal in both directions.

Forward: 10 → 20 → 30 Backward: 30 → 20 → 10

3. Circular Linked List

A Circular Linked List does not end with a NULL link.

Instead, the last node connects back to the first node.

10 •
→
20 •
→
30 •
↺ HEAD

Conceptually:

10 → 20 → 30 ↑ ↓ └─────────┘

This structure is useful when processing needs to continue repeatedly in a cycle.

Circular Doubly Linked List

A Circular Doubly Linked List combines both ideas:

  • every node has previous and next links, and
  • the first and last nodes are connected.

This makes forward and backward circular traversal possible.

Exam Tip: If a question simply asks “Types of Linked List,” the safest answer is usually Singly Linked List, Doubly Linked List and Circular Linked List. You can mention Circular Doubly Linked List as an extended type if required.

Linked List vs Array

Basis Array Linked List
Memory Usually contiguous Nodes may be non-contiguous
Size Often fixed or resized as a whole Can grow and shrink node by node
Random Access Fast through index Sequential traversal required
Insertion / Deletion May require shifting elements Can be efficient when position/node is known
Extra Memory No link field per element Pointers require extra memory
Cache Locality Usually better Often weaker because nodes may be scattered

Arrays also use concepts such as Row Major and Column Major storage when working with multidimensional data. That topic is explained separately in Row Major vs Column Major Order in Data Structure.

Basic Operations on Linked List

The most important Linked List operations are:

Traversal

Visit nodes one by one.

Insertion

Add a new node.

Deletion

Remove an existing node.

Searching

Find whether a value exists.

Updating

Change data stored in a node.

Counting

Determine the total number of nodes.

Traversal in Linked List

Traversal means visiting every node one by one.

Unlike an array, we cannot normally jump directly to any node using an index.

HEAD →
10 •
→
20 •
→
30 •
→ NULL
Start from HEAD.
Process the current node.
Move to the node stored in the next link.
Repeat until the pointer becomes NULL.

Traversal Algorithm

ptr = head while ptr != NULL print ptr.data ptr = ptr.next

Insertion in Linked List

Insertion means adding a new node to the list.

Common insertion positions are:

  • at the beginning,
  • at the end, and
  • at a specific position or after a particular node.

Insertion at Beginning

Suppose the original list is:

10 → 20 → 30 → NULL

We want to insert 5 at the beginning.

Create a new node containing 5.
Set new.next to the current HEAD.
Update HEAD so that it points to the new node.
Before: HEAD → 10 → 20 → 30 → NULL After: HEAD → 5 → 10 → 20 → 30 → NULL

Pseudocode

newNode.data = 5 newNode.next = head head = newNode
Important: Insertion at the beginning of a Singly Linked List can be performed in constant time when HEAD is available.

Insertion at End

Suppose:

10 → 20 → 30 → NULL

We want to add 40.

Create a new node containing 40.
Set new.next = NULL.
Traverse until the last node is found.
Make the last node point to the new node.
10 → 20 → 30 → 40 → NULL

If the list also maintains a TAIL pointer, insertion at the end can be much faster because traversal to the last node may not be required.

Insertion at a Specific Position

Suppose:

10 → 20 → 40 → NULL

We want to insert 30 between 20 and 40.

Before: 20 → 40 New Node: 30 After: 20 → 30 → 40

The important part is changing links in the correct order so that the rest of the list is not lost.

Deletion in Linked List

Deletion means removing a node while keeping the remaining nodes correctly connected.

Common cases are:

  • delete the first node,
  • delete the last node, and
  • delete a node from a particular position.

Deletion from Beginning

Suppose:

HEAD → 10 → 20 → 30 → NULL

After deleting 10:

HEAD → 20 → 30 → NULL

The HEAD is updated to point to the second node.

Pseudocode

temp = head head = head.next delete temp

Deletion from End

For:

10 → 20 → 30 → NULL

we must reach the node before 30 and change its next field to NULL.

10 → 20 → NULL

In a Singly Linked List, finding the previous node usually requires traversal from HEAD unless extra information is maintained.

Deletion of a Specific Node

Suppose the list is:

10 → 20 → 30 → 40 → NULL

To delete 30, change the next link of 20 so that it points directly to 40.

Before: 20 → 30 → 40 After: 20 ─────→ 40

Searching in Linked List

Searching normally starts from HEAD.

Each node is checked until:

  • the required value is found, or
  • the list ends.

Searching Algorithm

ptr = head while ptr != NULL if ptr.data == key return FOUND ptr = ptr.next return NOT_FOUND

Updating a Linked List Node

Updating means finding a required node and changing its stored data.

Example:

Before: 10 → 20 → 30 Update 20 to 25 After: 10 → 25 → 30

Time Complexity of Linked List Operations

Operation Typical Singly Linked List Complexity Reason
Access by Position O(n) Nodes must usually be followed sequentially
Search O(n) May need to inspect every node
Insert at Beginning O(1) Only HEAD and one link are changed
Delete from Beginning O(1) HEAD can move directly to the next node
Insert at End O(n) without tail Last node must be found
Insert at End O(1) with tail TAIL directly identifies the last node
Delete Known Node / After Known Predecessor Can be O(1) Only local links need modification
Common Exam Mistake: Students often write “Insertion and deletion in Linked List are always O(1).” This is not correct. Updating links may be constant time, but finding the required position can still require O(n) traversal.

Singly vs Doubly vs Circular Linked List

Feature Singly Linked List Doubly Linked List Circular Linked List
Links per Node Usually one Usually two Depends on singly or doubly circular form
Forward Traversal Yes Yes Yes
Backward Traversal No Yes Only in doubly circular form
Last Node Points to NULL Next points to NULL Connects back to first node
Extra Memory Lower Higher Depends on implementation
Best For Simple sequential structures Two-way navigation Repeated cyclic processing

Advantages of Linked List

Dynamic Growth

The list can grow as new nodes are created instead of requiring one fixed continuous block.

Flexible Insertion

Once the correct node is known, insertion may require only a small number of link changes.

Flexible Deletion

Removing a node usually does not require shifting all later elements like an array may require.

Useful Building Block

Linked Lists are used to implement stacks, queues, graph structures and other dynamic data structures.

Disadvantages of Linked List

No direct random access: To reach the fifth node, we usually need to follow previous nodes first.

Extra memory: Every node needs at least one pointer in addition to its data.

Pointer handling: Incorrect link updates can break the list or lose access to nodes.

Weak cache locality: Nodes can be located at different places in memory.

More complex implementation: Insertion and deletion require careful pointer changes.

Applications of Linked List

Stacks

A stack can be implemented using dynamically linked nodes.

Queues

Front and rear nodes can be connected efficiently.

Graph Representation

Adjacency lists commonly use list-like structures to represent neighbours.

Browser Navigation

Two-way navigation concepts can be modelled with doubly linked structures.

Music Playlists

Circular or doubly linked structures can represent previous/next playback.

Memory Management

Free blocks and dynamically allocated objects may be organised using linked structures.

Linked List and Sparse Data Structures

Linked structures are also useful when only a small amount of data exists among many possible positions.

For example, the earlier chapter on Sparse Matrix in Data Structure explained that non-zero matrix elements can be stored using special compact representations. A linked representation is one possible way to connect only the useful non-zero elements instead of storing the complete matrix.

This shows an important Data Structure principle:

Choose representation according to the way data is stored and processed.

Example: Building a Linked List Step by Step

Suppose we want:

10 → 20 → 30 → NULL

Step 1: Create First Node

HEAD → 10 → NULL

Step 2: Add Second Node

HEAD → 10 → 20 → NULL

Step 3: Add Third Node

HEAD → 10 → 20 → 30 → NULL

The important point is that the logical order is created by links. The physical memory locations do not need to appear in the same order.

Simple C Structure for a Singly Linked List Node

struct Node { int data; struct Node *next; };

Here:

  • data stores the value, and
  • next stores the address of another Node.
The code is included only to connect the concept with implementation. For theory exams, first explain the node diagram and working clearly before writing code.

How Memory Works in a Linked List

Suppose three nodes are stored at different memory locations:

Node Memory Address Data Next Address
Node 1 1000 10 4500
Node 2 4500 20 2800
Node 3 2800 30 NULL

Even though the addresses are:

1000 → 4500 → 2800

the logical order is still:

10 → 20 → 30
Memory Trick:

Array says: “Find me by position.”

Linked List says: “Follow my link.”

This one difference explains most of the behaviour of both structures.

Linked List vs Sparse Matrix vs Array Storage

Structure Main Storage Idea Useful When
Array Elements stored in indexed sequence Fast indexed access is important
Linked List Nodes connected using links Dynamic insertion/deletion is important
Sparse Matrix Store mainly useful non-zero data Most matrix positions are zero

Common Mistakes Students Make

1. Saying Linked List uses contiguous memory
A Linked List does not require nodes to be stored next to each other.

2. Forgetting HEAD
HEAD identifies the beginning of the list. Losing HEAD may make the list unreachable.

3. Changing pointers in the wrong order
During insertion or deletion, wrong pointer updates can disconnect the remaining list.

4. Assuming direct index access
A normal Linked List does not support array-style O(1) random access.

5. Forgetting the NULL condition
Traversal of a normal Singly Linked List stops when the pointer becomes NULL.

6. Using NULL as the last link in a Circular Linked List
The last node of a circular list points back to the beginning.

Best Memory Trick for Linked List

NODE = Data + Direction

Think of every node as a small box that contains:

VALUE + WHERE TO GO NEXT

For types:

Singly → One direction
Doubly → Two directions
Circular → Comes back again

Quick Comparison for Exams

Node Data + Link
HEAD First node reference
Last Node Next = NULL
Singly Next link only
Doubly Previous + Next
Circular Last connects to first
Search O(n)
Insert at Head O(1)
Main Strength Dynamic structure

Exam Questions with Answers

Q1. What is a Linked List?

A Linked List is a linear Data Structure made up of nodes. Each node stores data and one or more links that connect it with other nodes.

Q2. What is a node?

A node is an individual unit of a Linked List. In a Singly Linked List, it normally contains a data field and a next pointer.

Q3. What is HEAD?

HEAD is the pointer or reference that identifies the first node of a Linked List.

Q4. Name the major types of Linked List.

The major types are Singly Linked List, Doubly Linked List and Circular Linked List.

Q5. Why is Linked List called a dynamic Data Structure?

Because nodes can be created and removed during program execution, allowing the structure to grow or shrink according to requirement.

Q6. What is the difference between Singly and Doubly Linked List?

A Singly Linked List normally contains one next link, while a Doubly Linked List contains both previous and next links and therefore supports traversal in both directions.

5-Mark Exam Answer: Linked List

A Linked List is a linear Data Structure in which elements are stored inside nodes. The nodes do not need to occupy consecutive memory locations. Instead, they are logically connected using pointers or links.

A basic Singly Linked List node contains:

Data | Next

The first node is identified using HEAD, while the next field of the last node contains NULL.

The major types of Linked List are:

  • Singly Linked List
  • Doubly Linked List
  • Circular Linked List

Important operations include traversal, insertion, deletion, searching and updating.

Linked Lists are useful because they can grow dynamically and allow flexible insertion and deletion. However, they require additional pointer memory and do not provide direct array-like random access.

10-Mark Exam Answer: Linked List, Types and Operations

A Linked List is a dynamic linear Data Structure formed using a collection of nodes. Each node contains data and one or more pointers that connect it with other nodes. Unlike an array, Linked List nodes do not need to be stored in contiguous memory locations.

In a Singly Linked List, every node contains a data field and a next pointer:

HEAD → [Data | Next] → [Data | Next] → NULL

The main types of Linked List are:

1. Singly Linked List: Every node points to the next node and traversal occurs mainly in one direction.

2. Doubly Linked List: Every node contains previous and next pointers, allowing movement in both directions.

3. Circular Linked List: The final node points back to the first node instead of NULL.

The important Linked List operations are traversal, insertion, deletion, searching and updating.

Insertion can occur at the beginning, end or a specific position. Deletion can also be performed from different positions by updating the required links.

A Linked List is useful when the size of data changes frequently and insertion or deletion is important. Its disadvantages include extra pointer memory, sequential access and more complex pointer handling.

Linked Lists are commonly used for stacks, queues, graph adjacency lists, playlists and other dynamic structures.

Frequently Asked Questions

Is Linked List a linear Data Structure?

Yes. A Linked List is considered a linear Data Structure because its nodes are logically arranged in a sequence, even though they may not be physically adjacent in memory.

Why does a Linked List not require contiguous memory?

Each node stores a link to another node. Therefore, the program can follow these links even when the nodes are stored at different memory locations.

What is the difference between an array and a Linked List?

An array provides index-based access and normally stores its elements in contiguous memory, while a Linked List connects separately allocated nodes using pointers.

Which Linked List supports backward traversal?

A Doubly Linked List supports backward traversal because each node contains a pointer to its previous node as well as its next node.

Why is Circular Linked List called circular?

Because the last node connects back to the first node, creating a cycle instead of ending with NULL.

Is insertion always O(1) in a Linked List?

No. The actual link update may take constant time, but finding the required insertion position can require O(n) traversal.

Can Linked List be used to implement Stack and Queue?

Yes. Linked Lists are commonly used to create dynamic implementations of stacks and queues.

What is the biggest advantage of Linked List?

Its main advantage is flexibility. Nodes can be added or removed dynamically without requiring all later elements to be shifted as in many array operations.

Tags

Post a Comment

0 Comments
* Please Don't Spam Here. All the Comments are Reviewed by Admin.
Join Telegram Exam updates and free resources