LINKED LISTS

LINKED LISTS

• A linked list is a collection of nodes arranged in linear form
• Each node stores data and a pointer (or reference) to the next node
• Nodes are connected through pointers, forming a chain
• Not stored sequentially in memory
• Can grow or shrink dynamically as nodes are added or removed

FEATURES OF LINKED LISTS

• Has a head (first node) and a tail (last node)
• Head points to the first node and tail points to NULL
• Nodes are linear but not stored contiguously in memory
• Each node has two parts: data part (stores value), pointer part (stores address of next node)
• Data insertion or deletion can occur anywhere in the list
• Traversal required to reach specific nodes
• Memory is allocated dynamically using pointers

TYPES OF LINKED LISTS

Singly Linked List

• Links move in one direction
• Last node points to NULL

Doubly Linked List

• Links move in forward and backward directions
• Each node stores addresses of both previous and next nodes
• First Node (Head):
• prev pointer → NULL (no node before it)
• next pointer → points to the second node
• Last Node (Tail):
• next pointer → NULL (no node after it)
• prev pointer → points to the second-to-last node

Circular Linked List

• Last node links back to the first node
• Creates a circular chain

NODE STRUCTURE

• Contains data and a pointer to the next node
• Head pointer stores address of the first node
• NULL pointer marks the end of the list

BASIC OPERATIONS ON LINKED LISTS

• Insertion → add a node to the list
• Deletion → remove a node from the beginning of the list
• Display → show all nodes in sequence
• Search → find a node containing a specific key value
• Delete → delete an element/node from the list using a given key

GENERAL LINKED LIST RULES

• Head pointer always stores the address of the first node
• The last node’s next pointer must always be set to NULL
• Not setting NULL can lead to runtime errors
• Each node’s memory must be freed after deletion to avoid memory leaks

INSERTION TYPES

• At beginning of the list
• At middle of the list
• At end of the list

INSERTION AT BEGINNING

• Create a new node
• Link new node to where head was pointing
• Update head to point to new node

INSERTION AT END

• Create a new node and set its next pointer to NULL
• Traverse the list to the last node
• Link the last node’s next pointer to the new node

INSERTION AT MIDDLE (between nodes)

• Create a new node
• Traverse to the position before the insertion point
• Link new node’s next pointer to the next node
• Link previous node’s pointer to the new node

DELETION

• Process of removing a node from the list
• Types of deletion: at the beginning, at the middle, at the end

Deletion at the Beginning

• Copy address of first node to a temporary variable
• Set head to point to the second node
• Free memory of the deleted node

Deletion at the End

• Traverse to the second-last node
• Set its next pointer to NULL
• Free memory of the last node

Deletion in the Middle

• Locate the node to be deleted
• Store address of the previous node
• Set previous node’s pointer to the next node (skip deleted node)
• Free memory of deleted node

OPERATIONS OF A LINKED LIST (FUNCTIONS)

• addLast(value) - Adds the given value to the end/back of the list
• addFirst(value) - Adds the given value to the top/front of the list, The new node becomes the new head of the list
• insert(value, i) - Adds/inserts a value at a specific location i in the list, Position i is counted from the top/front of the list
• size() - Returns the total number of nodes currently in the list
• isEmpty() - Returns true if the list contains no nodes, Condition checked: size == 0
• delete(i) - Removes the node at position i in the list, Returns the value that was stored in the deleted node

SEARCH

• Traverse from head node
• Compare data in each node with target value
• Stop when found or when NULL pointer is reached

ADVANTAGES OF LINKED LISTS

• Dynamic memory allocation
• Efficient insertion and deletion anywhere in the list
• No predefined size limit

DISADVANTAGES OF LINKED LISTS

• Slower traversal compared to arrays
• Extra memory needed for pointers
• Cannot access elements directly (must traverse)

If you are still unsure about how linked lists work, please watch this video.

Remember all notes are more accurate to the CAPE syllabus than videos