Linked Lists
Node-Based Data Structures

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:

• Data (the value to be stored)
• A reference (or pointer) to the next node

Types of Linked Lists

• Singly Linked List: Each node points to the next one.
• Doubly Linked List: Each node has references to both the next and previous nodes.
• Circular Linked List: The last node connects back to the head node.

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?

Aspect	Array	Linked List
Memory	Contiguous	Non-contiguous
Insertion/Deletion	Slow (except at end)	Fast (O(1) at head)
Access Time	O(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

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

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

• Efficient memory usage
• Faster insertions/deletions (especially in large datasets)
• No need to define size in advance

Disadvantages

• Slow access (O(n) to reach nth element)
• Extra memory usage for storing pointers

Recap

• Linked Lists use dynamic memory.
• Each node stores data and a reference to the next.
• They are ideal when frequent insertion/deletion is required.