Linked Lists
Understanding Dynamic Data Storage



What is a Linked List?

A linked list is a linear data structure where elements (called nodes) are stored in separate memory locations and connected using pointers. Unlike arrays, they don't require contiguous memory.

Each node contains:

Types of Linked Lists

Why Use Linked Lists?

Linked lists offer dynamic memory allocation. Unlike arrays, you don’t need to define the size in advance, and insertions/deletions are faster when done at the start or middle.

How is a Linked List Different from an Array?

AspectArrayLinked List
MemoryContiguousNon-contiguous
Insertion/DeletionSlow (except at end)Fast (O(1) at head)
Access TimeO(1)O(n)

Creating a Node

class Node:
    data
    next

This simple structure stores data and points to the next node. When next is null (or None), it's the last node.

Example: Creating a Linked List

head = Node("A")
head.next = Node("B")
head.next.next = Node("C")

This creates a linked list: A → B → C

Output:

A → B → C → null

Traversing a Linked List

We move from one node to the next until we reach the end.

function traverse(head):
    current = head
    while current is not null:
        print current.data
        current = current.next

Output:

A
B
C

Question:

Why can't we access the 3rd element directly like in an array?

Answer: Because nodes are not stored in order in memory. We must follow each pointer starting from the head until we reach the desired node.

Inserting at the Beginning

function insertAtHead(head, value):
    newNode = Node(value)
    newNode.next = head
    head = newNode
    return head

Inserting at head is O(1) – no traversal is needed.

Inserting at the End

function insertAtEnd(head, value):
    newNode = Node(value)
    if head is null:
        return newNode
    current = head
    while current.next is not null:
        current = current.next
    current.next = newNode
    return head

This operation requires traversal, hence O(n) time complexity.

Deleting a Node by Value

function deleteByValue(head, target):
    if head.data == target:
        return head.next
    current = head
    while current.next is not null and current.next.data != target:
        current = current.next
    if current.next is not null:
        current.next = current.next.next
    return head

Question:

What happens if the value isn’t in the list?

Answer: The loop exits without finding it, and the original list remains unchanged.

Advantages of Linked Lists

Disadvantages

Recap



Welcome to ProgramGuru

Sign up to start your journey with us

Support ProgramGuru.org

Mention your name, and programguru.org in the message. Your name shall be displayed in the sponsers list.

PayPal

UPI

PhonePe QR

MALLIKARJUNA M