Learn Linked List Data Structure - Revision Notes

Introduction to Linked List Data Structure

A linked list is a linear data structure where each element is a separate object (node) containing a reference (link) to the next node in the sequence. Unlike arrays, linked list elements are not stored in contiguous locations; instead, they are linked using pointers.

Importance and Applications of Linked List Data Structure

→ Dynamic Memory Allocation: Linked lists allow dynamic memory allocation, unlike arrays that require fixed size allocation.
Example: Linked lists are useful in situations where the size of data is not known beforehand, like managing memory in operating systems.

→ Implementation of Stacks and Queues: Linked lists are fundamental in implementing other data structures like stacks and queues.
Example: Stacks and queues can be efficiently implemented using singly or doubly linked lists, supporting operations such as push, pop, enqueue, and dequeue.

→ Implementation of Hash Tables: Linked lists are used in hash table implementations to handle collisions.
Example: Hash tables use linked lists to store multiple elements that hash to the same index, managing collisions by chaining.

Key Operations of Linked List Data Structure

→ Insert: Add an element to the linked list.
→ Delete: Remove an element from the linked list.
→ Traverse: Visit each element in the linked list.
→ Search: Find a specific element in the linked list.

Insert Operation in Linked List Data Structure

The insert operation adds an element to the linked list. Here's the algorithm and pseudocode:

Algorithm:

1. Create a new node with the given data.
2. Set the next pointer of the new node to point to the current head of the linked list.
3. Update the head pointer to point to the new node.

Pseudocode:

function insert(head, data):
    newNode = new Node(data)
    newNode.next = head
    head = newNode
    

Delete Operation in Linked List Data Structure

The delete operation removes an element from the linked list. Here's the algorithm and pseudocode:

Algorithm:

1. Find the node to be deleted.
2. Adjust the next pointer of the previous node to skip over the node to be deleted.
3. Delete the node and free memory.

Pseudocode:

function deleteNode(head, key):
    currentNode = head
    // If key is found at head
    if currentNode.data == key:
        head = currentNode.next
        free(currentNode)
        return head

    // Traverse the linked list to find the key
    while currentNode.next != null:
        if currentNode.next.data == key:
            deleteNode = currentNode.next
            currentNode.next = currentNode.next.next
            free(deleteNode)
            return head
        currentNode = currentNode.next

    // Key not found
    return head
    

Traverse Operation in Linked List Data Structure

The traverse operation visits each element in the linked list. Here's the algorithm and pseudocode:

Algorithm:

1. Start from the head of the linked list.
2. Iterate through each node, performing the desired operation.
3. Continue until reaching the end of the linked list (null pointer).

Pseudocode:

function traverse(head):
    currentNode = head
    while currentNode != null:
        // Perform operation on currentNode
        currentNode = currentNode.next
    

Search Operation in Linked List Data Structure

The search operation finds a specific element in the linked list. Here's the algorithm and pseudocode:

Algorithm:

1. Start from the head of the linked list.
2. Iterate through each node, comparing the node's data with the target data.
3. If found, return the node; otherwise, continue until reaching the end of the linked list.

Pseudocode:

function search(head, target):
    currentNode = head
    while currentNode != null:
        if currentNode.data == target:
            return currentNode
        currentNode = currentNode.next
    return null
    

Time Complexity and Space Complexity

Time Complexity: Insertion, deletion, and search operations have an average time complexity of O(n), where n is the number of elements in the linked list, due to traversal.

Space Complexity: The space complexity is O(n), where n is the number of elements in the linked list, due to the storage of elements and pointers.

Advantages of Linked List Data Structure

→ Dynamic Size: Linked lists can grow or shrink in size dynamically.
→ Efficient Insertion and Deletion: Insertion and deletion operations are efficient compared to arrays, especially in large lists.
→ Implementation Flexibility: Supports different types of linked lists (singly, doubly, circular) depending on requirements.

Disadvantages of Linked List Data Structure

→ Memory Overhead: Requires extra memory for storing pointers.
→ No Random Access: Cannot access elements randomly like arrays, requiring traversal from the head.
→ Complexity: More complex to implement and manage compared to arrays.