Linked List

What is Linked List?

Linked list is a data structure in which each element is allocated dynamically, and each element or node contains:

  1. A Value (Data)

  2. A Reference (Pointer) to next node in the sequence

Why linked list is better?

  • Dynamic Size: Linked List can be increased any time.

  • Faster Insertion and Deletion than array because only have to update the pointer does not shift the whole array.

Choosing Between Arrays and Linked Lists?

Use Arrays:

  • When fast access to elements by index is necessary. (O(1))

  • When the size of the list is relatively stable or known in advance.

  • When memory usage needs to be optimized due to contiguous storage.

Use Linked Lists:

  • When the size of the list changes frequently and dynamically.

  • When efficient insertions and deletions at the beginning or end of the list are essential.

  • When flexibility and dynamic resizing are more critical than direct access by index.

What are the types of Linked Lists?

Single Linked List:

  • Each node contains data and a reference (pointer) to the next node in the sequence.

  • Traversal is possible only in one direction: from the head to the tail.

Doubly Linked List:

  • Each node contains data and references (pointers) to both the next and previous nodes in the sequence.

  • Allows bidirectional traversal: forward (from head to tail) and backward (from tail to head).

Circular Linked List:

  • Similar to a single linked list, but the last node points back to the first node, forming a circular structure.

Insertion at the Beginning

Algorithm Steps:

  1. Create a new node with given data

  2. Set the next pointer of new node to point to the current head: New->Next = Head

  3. Update the head pointer to point to the new node: Head = New Node

Complexity:

  • Space Complexity: O(1)

  • Time Complexity: O(1)

Insertion at the End

Algorithm Steps:

  1. Create a new node with given data

  2. Set the next pointer of new node to point to the NULL: New->Next = Null

  3. Traverse the list until reaching the last node.

  4. Set the next pointer of the last node to point to the new node.

Complexity:

  • Space Complexity: O(1)

  • Time Complexity: O(n) (as it requires traversing the entire list to find the last node)

Insertion in the Middle of a Linked List

Algorithm Steps:

  1. Create a new node with the given data

  2. Traverse to the node after which the new node should be inserted

  3. Adjust the next pointers:

    • Set the next pointer of the new node to point to the node that currently follows the node at the (position-1)th place.

    • Set the next pointer of the (position-1)th node to point to the new node.

Complexity:

  • Space Complexity: O(1)

  • Time Complexity: O(n-1) where n is the position at which the node is being inserted

Deletion at the Beginning

Algorithm Steps:

  1. If the list is empty, return.

  2. Store the reference to the current head node.

  3. Update the head pointer to point to the next node.

  4. Delete the stored node.

Complexity:

  • Space Complexity: O(1)

  • Time Complexity: O(1)

Deletion at the End

Algorithm Steps:

  1. If the list is empty or has only one node, set head to None and return.

  2. Traverse the list until reaching the second-to-last node.

  3. Update the next pointer of the second-to-last node to None.

  4. Delete the last node.

Complexity:

  • Space Complexity: O(1)

  • Time Complexity: O(n-1) (as it requires traversing the entire list to find the second-to-last node)

Deletion in the Middle of a Linked List

Algorithm Steps:

  1. If the list is empty, there is nothing to delete.

  2. Traverse the list to find the node before the one to be deleted

  3. Adjust the next pointers:

    • Save the pointer to the node to be deleted.

    • Set the next pointer of the (position-1)th node to the next pointer of the node to be deleted.

    • Free the memory of the node to be deleted.

Complexity:

  • Space Complexity: O(1)

  • Time Complexity: O(n-1) where n is the position at which the node is being deleted

How to Reverse a Linked List?

Algorithm

  1. Initialize three pointers:

    • prev: Initially set to NULL. This will eventually become the new head of the reversed list.

    • current: Initially set to the head of the list. This is the node currently being processed.

    • next: Initially set to NULL. This will temporarily store the next node of the current node.

  2. Iterate through the list:

    • Save the next node.

    • Reverse the current node's pointer.

    • Move the prev and current pointers one step forward.

    • Repeat until you reach the end of the list.

  3. Update the head of the list:

    • After the loop, prev will be pointing to the new head of the reversed list. Update the head pointer to prev.

Explanation

  1. Initialization:

    • prev is set to NULL because the new last node (the original head) will point to NULL.

    • current is set to the head of the list to start processing nodes from the beginning.

      • current = head

      • prev = Null

  2. Iteration:

    • next = current->next; saves the next node.

    • current->next = prev; reverses the link, making the current node point to the previous node.

    • prev = current; moves the prev pointer one step forward to the current node.

    • current = next; moves the current pointer one step forward to the next node in the original list.

  3. Update Head:

    • After the loop, prev points to the new head of the reversed list. Update the head pointer to prev

Complexity

  • Time Complexity: O(n)

  • Space Complexity: O(1)

Find Middle Element

Algorithm Steps:

  1. Initialize two pointers, slow and fast, both starting at the head.

  2. Move slow pointer by one step and fast pointer by two steps at each iteration until the fast pointer reaches the end of the list.

  3. The element pointed to by the slow pointer at this point is the middle element.

Complexity

  • Space Complexity: O(1)

  • Time Complexity: O(n)

Find Loop (Floyd's Cycle Detection Algorithm)

Algorithm Steps:

  1. Initialize two pointers, slow and fast, both starting at the head.

  2. Move slow pointer by one step and fast pointer by two steps at each iteration until one of the following conditions is met:

    • Both pointers meet at the same node (loop detected).

    • Fast pointer reaches the end of the list (no loop).

  3. If a loop is detected, reset one of the pointers to the head and move both pointers one step at a time until they meet again. The meeting point is the start of the loop.

Complexity

  • Space Complexity: O(1)

  • Time Complexity: O(n)

PreviousBinary Search Tree(BST)NextGraph

Last updated