Ugenz Academy/Tutorial

Linkedlist

15 min read2,845 words

Reading progress

Keep learning

Linked List

A Linked List is a linear data structure where elements are stored in separate objects called nodes, and each node contains data plus a link to another node.

The biggest difference from an array is:

Array → elements are stored next to each other in memory.
Linked List → nodes can be anywhere in memory, and pointers connect them.

1. Why Do We Need Linked Lists?

Consider an array:

[10] [20] [30] [40] [50]

Arrays are excellent for accessing elements:

arr[3]

because we can directly calculate where the element is.

But arrays have a problem: inserting or deleting elements in the middle can require shifting many elements.

For example, inserting 25:

Before: 10 20 30 40 50

We need:

10 20 25 30 40 50

Several elements may need to move.

A linked list handles this differently.

10 → 20 → 30 → 40 → 50

If we want to insert 25:

10 → 20 → 25 → 30 → 40 → 50

We can change links instead of shifting every element.

2. What Is a Node?

A linked list consists of nodes.

A basic node contains two things:

┌──────────────┬──────────────┐ │ Data │ Next │ └──────────────┴──────────────┘

For example:

┌──────┬──────┐ │ 10 │ ────────→ └──────┴──────┘

The two parts are:

Data

Stores the actual value.

10

Next

Stores a pointer/reference to the next node.

3. Basic Linked List Structure

Suppose we have:

10 → 20 → 30 → 40 → NULL

It actually looks conceptually like:

┌────┬──────┐ ┌────┬──────┐ ┌────┬──────┐ │ 10 │ ───────→ │ 20 │ ───────→ │ 30 │ ───────→ NULL └────┴──────┘ └────┴──────┘ └────┴──────┘

The last node points to:

NULL

which means:

There is no next node.

4. Head

The linked list needs a starting point.

This is called the head.

head ↓ 10 → 20 → 30 → 40 → NULL

head stores the address/reference of the first node.

If:

head = NULL

then the linked list is empty.

5. Why Is It Called a Linked List?

Because nodes are linked together.

Node 1 ↓ Node 2 ↓ Node 3 ↓ Node 4

The connection is created using pointers.

So:

Data + Link

creates a chain:

10 → 20 → 30 → 40

6. Creating a Node in C++

A simple node can be defined using a struct:

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

Here:

data

stores the value.

And:

next

is a pointer to another Node.

7. Creating a Single Node

Example:

Node* node1 = new Node(); node1->data = 10; node1->next = nullptr;

Conceptually:

node1 ↓ ┌────┬────────┐ │ 10 │ nullptr│ └────┴────────┘

There is currently only one node.

8. Creating Multiple Nodes

We can create:

Node* first = new Node(); Node* second = new Node(); Node* third = new Node();

Then:

first->data = 10; second->data = 20; third->data = 30;

Connect them:

first->next = second; second->next = third; third->next = nullptr;

Now:

first ↓ 10 → 20 → 30 → NULL

9. Understanding ->

When working with a pointer to a structure/class, we use:

->

For example:

first->data

means:

Access the data member of the node pointed to by first.

Similarly:

first->next

means:

Access the next pointer of that node.

10. Creating a Linked List More Cleanly

A common approach:

struct Node { int data; Node* next; Node(int value) { data = value; next = nullptr; } };

Now:

Node* first = new Node(10); Node* second = new Node(20); Node* third = new Node(30); first->next = second; second->next = third;

The result:

10 → 20 → 30 → NULL

11. Traversing a Linked List

Unlike an array, we cannot directly do:

list[3]

Instead, we start at head and follow the links.

Example:

Node* current = head; while(current != nullptr) { cout << current->data << " "; current = current->next; }

Suppose:

head ↓ 10 → 20 → 30 → NULL

Traversal:

current → 10 ↓ current → 20 ↓ current → 30 ↓ current → NULL

Output:

10 20 30

Complexity:

Time = O(n)

because we may visit every node.

12. Inserting at the Beginning

Suppose:

10 → 20 → 30 → NULL

We want to insert:

5

Create a new node:

5

Then:

newNode->next = head;

Now:

5 → 10 → 20 → 30 → NULL

Finally:

head = newNode;

Code:

Node* newNode = new Node(5); newNode->next = head; head = newNode;

Complexity

O(1)

This is one of the biggest advantages of a linked list.

13. Inserting at the End

Suppose:

10 → 20 → 30 → NULL

We want:

10 → 20 → 30 → 40 → NULL

Create:

40

Then find the last node:

10 → 20 → 30 → NULL ↑ last

Set:

last->next = newNode;

Result:

10 → 20 → 30 → 40 → NULL

If we only have a head pointer, finding the last node requires traversal.

Therefore:

O(n)

However, if we maintain a tail pointer, insertion at the end can be made O(1).

14. Tail

The tail is the last node.

Example:

head tail ↓ ↓ 10 → 20 → 30 → 40 → NULL

If we maintain both:

head tail

then we can quickly access both ends.

15. Inserting in the Middle

Suppose:

10 → 20 → 40 → 50

We want to insert 30 after 20.

Create:

30

We need to change the links:

Before:

20 → 40

After:

20 → 30 → 40

Conceptually:

newNode->next = current->next; current->next = newNode;

Result:

10 → 20 → 30 → 40 → 50 → NULL

The actual pointer changes are simple.

But finding the correct position may require traversal.

So the overall complexity is often:

O(n)

if we start only from head.

16. Deleting the First Node

Suppose:

head ↓ 10 → 20 → 30 → NULL

We want to delete 10.

Simply move head:

head = head->next;

Now:

head ↓ 20 → 30 → NULL

The old first node can then be released appropriately in manual-memory C++ code.

Complexity:

O(1)

17. Deleting the Last Node

Suppose:

10 → 20 → 30 → NULL

We want:

10 → 20 → NULL

We need to find the node before 30.

10 → 20 → 30 ↑ previous

Then:

20 → NULL

With a singly linked list and only a head pointer, finding the previous node requires traversal.

Complexity:

O(n)

18. Deleting a Specific Node

Suppose:

10 → 20 → 30 → 40

We want to remove:

30

We need to connect:

20 → 40

Before:

20 → 30 → 40

After:

20 → 40

The node 30 is removed from the chain.

Again, finding it may require traversal.

19. Searching a Linked List

Suppose:

10 → 20 → 30 → 40 → NULL

We want to find 30.

Start at head:

10 → 20 → 30 ↑ ↑ ↑ 1st 2nd Found

Code:

Node* current = head; while(current != nullptr) { if(current->data == 30) { cout << "Found"; break; } current = current->next; }

Worst-case complexity:

O(n)

Unlike an array, we cannot directly jump to the 30th node.

20. Why Can't We Do Random Access?

With an array:

arr[4]

can directly locate the fifth element.

With a linked list:

10 → 20 → 30 → 40 → 50

to reach 50, we generally need:

head ↓ 10 ↓ 20 ↓ 30 ↓ 40 ↓ 50

Therefore accessing the nth node is generally:

O(n)

This is a major difference between arrays and linked lists.

21. Array vs Linked List

FeatureArrayLinked List
Memory layoutContiguousNodes can be scattered
Random accessO(1)O(n)
SearchO(n)O(n)
Insert at beginningUsually O(n)O(1)
Delete at beginningUsually O(n)O(1)
Insert at known nodeShifting may be neededO(1) link changes
Extra pointer memoryNoYes
Fixed-size arrayFixedDynamic
Cache localityUsually goodGenerally less predictable

The important lesson:

Arrays are good for fast access. Linked lists are good when frequent insertions/deletions and flexible size are important.

22. Types of Linked Lists

There are several important types.

1. Singly Linked List

Each node points only to the next node.

10 → 20 → 30 → NULL

2. Doubly Linked List

Each node has:

previous data next

Example:

NULL ← 10 ⇄ 20 ⇄ 30 → NULL

3. Circular Linked List

The last node points back to the first node.

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

These are important topics within linked lists.

23. Singly Linked List

The structure is:

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

Each node has:

data ↓ next ↓ next node

Example:

head ↓ ┌────┬─────┐ ┌────┬─────┐ ┌────┬──────┐ │ 10 │ ─────→ │ 20 │ ─────→ │ 30 │ NULL │ └────┴─────┘ └────┴─────┘ └────┴──────┘

24. Doubly Linked List

A doubly linked list contains two links.

┌─────────┬──────┬─────────┐ │ prev │ data │ next │ └─────────┴──────┴─────────┘

Example:

NULL ← 10 ⇄ 20 ⇄ 30 → NULL

This allows movement in both directions:

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

The tradeoff is that every node requires an additional pointer.

25. Circular Linked List

In a normal singly linked list:

10 → 20 → 30 → NULL

In a circular linked list:

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

The last node points back to the first node.

So there is no NULL at the end.

Circular lists can be useful for things like:

  • Round-robin scheduling
  • Repeated cyclic processing
  • Circular buffers in certain designs

26. Reversing a Linked List

This is one of the most important linked-list problems.

Suppose:

10 → 20 → 30 → NULL

We want:

30 → 20 → 10 → NULL

We can use three pointers:

previous current next

Initially:

previous = NULL current = head

Then repeatedly reverse the link.

Core idea:

next = current->next; current->next = previous; previous = current; current = next;

At the end:

head = previous;

Result:

30 → 20 → 10 → NULL

Complexity:

Time = O(n) Space = O(1)

This is a very important DSA pattern.

27. Finding the Middle Node

Suppose:

10 → 20 → 30 → 40 → 50

Middle:

30

A very common technique is slow and fast pointers.

slow → moves 1 step fast → moves 2 steps

Example:

slow: 10 → 20 → 30 fast: 10 → 30 → 50

When fast reaches the end, slow is around the middle.

This technique is called the:

Fast and Slow Pointer technique

It is extremely important for linked-list problems.

28. Detecting a Cycle

Consider:

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

The list contains a cycle.

A common solution is Floyd's Cycle Detection Algorithm, also called the Tortoise and Hare algorithm.

Use:

slow → 1 step fast → 2 steps

If there is a cycle, eventually:

slow == fast

This can detect a cycle in:

Time = O(n) Space = O(1)

29. Why Linked Lists Are Dynamic

An array often has a predetermined capacity:

int arr[100];

A linked list can create nodes as needed:

Create node ↓ Connect node ↓ Create another ↓ Connect again

So the list can grow:

10 ↓ 10 → 20 ↓ 10 → 20 → 30 ↓ 10 → 20 → 30 → 40

There is no requirement that all nodes be placed next to each other in memory.

30. Memory of a Linked List

Suppose we have:

10 → 20 → 30

Each node needs:

Data + Pointer

So compared with an array, a linked list has additional memory overhead for pointers.

For example, conceptually:

Array: [10][20][30] Linked List: [10 | next] → [20 | next] → [30 | NULL]

This is one reason linked lists aren't automatically "better" than arrays.

31. Advantages of Linked Lists

1. Dynamic size

Nodes can be added and removed as needed.

2. Easy insertion/deletion

Once the relevant node/position is known, changing links can be very efficient.

3. No need for contiguous memory

Nodes can exist at different memory locations.

4. Useful foundation

Linked lists help you understand:

  • Pointers
  • Dynamic memory
  • References
  • Node-based structures
  • Trees
  • Graphs

32. Disadvantages of Linked Lists

1. No direct/random access

You cannot efficiently do:

list[500]

like an array.

2. Extra memory

Each node needs pointer information.

3. More complicated

Pointers make linked lists harder to understand than arrays initially.

4. Poorer cache locality

Nodes may be scattered around memory, so traversing them can be less cache-friendly than traversing a contiguous array.

5. Searching is still O(n)

A linked list does not automatically make searching faster.

33. Important Complexity Table

For a singly linked list, a typical complexity table is:

OperationComplexity
Access first nodeO(1)
Access nth nodeO(n)
SearchO(n)
Insert at beginningO(1)
Delete first nodeO(1)
Insert after a known nodeO(1)
Delete after a known previous nodeO(1)
Insert at end with only headO(n)
Insert at end with tail pointerO(1)
ReverseO(n)
Find middleO(n)
Detect cycleO(n)

The exact complexity of insertion/deletion depends heavily on whether you already have a pointer to the relevant node.

34. Complete Basic Singly Linked List Example

Here is a simple implementation:

#include <iostream> using namespace std; struct Node { int data; Node* next; Node(int value) { data = value; next = nullptr; } }; int main() { Node* head = new Node(10); head->next = new Node(20); head->next->next = new Node(30); Node* current = head; while(current != nullptr) { cout << current->data << " "; current = current->next; } return 0; }

Output:

10 20 30

The structure is:

head ↓ 10 → 20 → 30 → NULL

35. The Most Important Mental Model

Don't think of a linked list as:

[10][20][30][40]

Think of it as:

next next 10 ─────────→ 20 ─────────→ 30 ─────────→ NULL

Each node says:

"Here is my data, and here is where the next node is."

That is the fundamental idea behind a linked list.

36. Array vs Linked List — The Core Difference

Remember this:

ARRAY [10][20][30][40][50] ↑ Direct access arr[3] → 40 O(1)

versus:

LINKED LIST 10 → 20 → 30 → 40 → 50 ↑ Start here and follow links To reach 40: 10 → 20 → 30 → 40 O(n)

So:

Array → fast access

Linked List → flexible node insertion/deletion

Neither is universally better. The right choice depends on the problem.

Final Summary

A linked list consists of:

Node │ ├── Data │ └── Next pointer

Multiple nodes create:

head ↓ 10 → 20 → 30 → 40 → NULL

The most important concepts you should understand before moving forward are:

  1. Node
  2. Head
  3. Next pointer
  4. NULL
  5. Traversal
  6. Insertion
  7. Deletion
  8. Searching
  9. Singly linked list
  10. Doubly linked list
  11. Circular linked list
  12. Reverse linked list
  13. Slow/fast pointers
  14. Cycle detection
  15. Linked-list complexity

Keep learning. Keep building. Keep growing.

© 2026 Ugenz Academy