DSAverse

Basics & Data Structures

Loading Data Structures...

Array Access

array[0..5]indexed access

Array

Stack

Queue

DSAverse

Initializing Sorting Algorithms...

Sorting

Trees

Graphs

Preparing interactive visualizations...

Back to Basics

Intermediate

List: Linked List

Watch nodes link and unlink as you traverse, insert, and delete. Understand pointers and sequential access.

Interactive Operations

Pointer Visualization

O(n) Access

Linked List Visualization

Each node contains a value and a next pointer. The last node points to NULL.

Color Legend

DefaultTraversing / TargetFound / CompletedNew node pending

Speed:

HEAD

List is empty — insert to begin

Size

NULL

Head

Dynamic

Allocation

Current Step

Use Insert, Delete, Search, or Access to begin visualization.

Complexity Analysis

O(n)

Access

O(n)

Insert/Delete

O(n)

O(1)*

Head Insert

O(n) Space

Dynamic allocation + pointer per node

*Operations at head are O(1); others require traversal to position.

Operations

Insert

Create node → traverse to position → update pointers

Delete

Traverse → update prev.next to skip deleted node

Access

Follow next pointers from head to target index

Search

Linear traversal comparing values at each node

vs Dynamic Array

O(1) head insert/delete

No shifting — just update a pointer

Unlimited dynamic size

Grows/shrinks without reallocation

No wasted capacity

Allocates exactly what is needed

O(n) access by index

No direct calculation — must traverse

Poor cache locality

Nodes scattered across memory

Test Yourself

Q1/3

What is the time complexity of accessing an element at index k in a linked list?

Implementation

Python

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None
        self.size = 0

    def insert(self, index, value):
        if index < 0 or index > self.size:
            raise IndexError("Index out of bounds")
        new_node = Node(value)
        if index == 0:                      # O(1) head insert
            new_node.next = self.head
            self.head = new_node
        else:                               # O(n) traverse then link
            current = self.head
            for _ in range(index - 1):
                current = current.next
            new_node.next = current.next
            current.next = new_node
        self.size += 1

    def delete(self, index):
        if index < 0 or index >= self.size:
            raise IndexError("Index out of bounds")
        if index == 0:
            value = self.head.value
            self.head = self.head.next
        else:
            current = self.head
            for _ in range(index - 1):
                current = current.next
            value = current.next.value
            current.next = current.next.next
        self.size -= 1
        return value

    def search(self, value):                # O(n) linear scan
        current, index = self.head, 0
        while current:
            if current.value == value:
                return index
            current, index = current.next, index + 1
        return -1

    def access(self, index):               # O(n) traversal
        current = self.head
        for _ in range(index):
            current = current.next
        return current.value

DSAverse

Basics & Data Structures

Loading Data Structures...

Array Access

array[0..5]indexed access

Array

Stack

Queue

Back to Basics

Intermediate

List: Linked List

Watch nodes link and unlink as you traverse, insert, and delete. Understand pointers and sequential access.

Interactive Operations

Pointer Visualization

O(n) Access

Linked List Visualization

Each node contains a value and a next pointer. The last node points to NULL.

Color Legend

DefaultTraversing / TargetFound / CompletedNew node pending

Speed:

HEAD

List is empty — insert to begin

Size

NULL

Head

Dynamic

Allocation

Current Step

Use Insert, Delete, Search, or Access to begin visualization.

Complexity Analysis

O(n)

Access

O(n)

Insert/Delete

O(n)

O(1)*

Head Insert

O(n) Space

Dynamic allocation + pointer per node

*Operations at head are O(1); others require traversal to position.

Operations

Insert

Create node → traverse to position → update pointers

Delete

Traverse → update prev.next to skip deleted node

Access

Follow next pointers from head to target index

Search

Linear traversal comparing values at each node

vs Dynamic Array

O(1) head insert/delete

No shifting — just update a pointer

Unlimited dynamic size

Grows/shrinks without reallocation

No wasted capacity

Allocates exactly what is needed

O(n) access by index

No direct calculation — must traverse

Poor cache locality

Nodes scattered across memory

Test Yourself

Q1/3

What is the time complexity of accessing an element at index k in a linked list?

Implementation

Python

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None
        self.size = 0

    def insert(self, index, value):
        if index < 0 or index > self.size:
            raise IndexError("Index out of bounds")
        new_node = Node(value)
        if index == 0:                      # O(1) head insert
            new_node.next = self.head
            self.head = new_node
        else:                               # O(n) traverse then link
            current = self.head
            for _ in range(index - 1):
                current = current.next
            new_node.next = current.next
            current.next = new_node
        self.size += 1

    def delete(self, index):
        if index < 0 or index >= self.size:
            raise IndexError("Index out of bounds")
        if index == 0:
            value = self.head.value
            self.head = self.head.next
        else:
            current = self.head
            for _ in range(index - 1):
                current = current.next
            value = current.next.value
            current.next = current.next.next
        self.size -= 1
        return value

    def search(self, value):                # O(n) linear scan
        current, index = self.head, 0
        while current:
            if current.value == value:
                return index
            current, index = current.next, index + 1
        return -1

    def access(self, index):               # O(n) traversal
        current = self.head
        for _ in range(index):
            current = current.next
        return current.value