Exploring Linked Lists: Key Operations in C++, Java, and Python

Here are some common linked list operations along with their algorithm steps and implementation in C++, Java, and Python:

1. Insertion at the Beginning

1. Create a New Node:

   • Allocate memory for a new node.

   • Assign the data value to the new node.

2. Link the New Node to the Current Head:

   • Set the next pointer of the new node to the current head node. This means the new node will now point to the first node in the list.

3. Update the Head Pointer:

   • Move the head pointer to point to the new node. The new node is now the first node in the list.

4. Handle Edge Cases:

   • If the list is initially empty (i.e., the head pointer is NULL), the new node will simply become the head node.

Illustration

Consider a linked list with the following nodes:

rustCopy codeCurrent List:      Head -> [Node1] -> [Node2] -> [Node3] -> NULL

Now, let's insert a new node with data NewNode at the beginning:

1. Create a New Node:

   • New Node created with data = NewNode.

2. Link the New Node:

   • Set newNode.next to point to the current head (Node1).

3. Update the Head Pointer:

   • Update head to point to newNode.

The updated list will look like this:

Updated List:     Head -> [NewNode] -> [Node1] -> [Node2] -> [Node3] -> NULL

C++ Implementation

cppCopy codestruct Node {
    int data;
    Node* next;
};

// Function to insert a new node at the beginning
Node* insertAtBeginning(Node* head, int newData) {
    // Step 1: Create a new node
    Node* newNode = new Node();
    newNode->data = newData;

    // Step 2: Link the new node to the current head
    newNode->next = head;

    // Step 3: Update the head pointer
    head = newNode;

    // Step 4: Return the updated head
    return head;
}

Java Implementation

class Node {
    int data;
    Node next;

    Node(int d) {
        data = d;
        next = null;
    }
}

// Function to insert a new node at the beginning
Node insertAtBeginning(Node head, int newData) {
    // Step 1: Create a new node
    Node newNode = new Node(newData);

    // Step 2: Link the new node to the current head
    newNode.next = head;

    // Step 3: Update the head pointer
    head = newNode;

    // Step 4: Return the updated head
    return head;
}

Python Implementation

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

# Function to insert a new node at the beginning
def insert_at_beginning(head, new_data):
    # Step 1: Create a new node
    new_node = Node(new_data)

    # Step 2: Link the new node to the current head
    new_node.next = head

    # Step 3: Update the head pointer
    head = new_node

    # Step 4: Return the updated head
    return head Analysis

• Time Complexity: O(1)
  (The insertion takes constant time since it only involves updating pointers.)

• Space Complexity: O(1)
  (Only a new node is created, regardless of the size of the list.)

2. Insertion at the End

Algorithm Steps:

1. Create a New Node:

   • Allocate memory for a new node.

   • Assign the data value to the new node.

2. Check if the List is Empty:

   • If the head pointer is NULL, the list is empty, so the new node will become the head of the list.

3. Traverse to the Last Node:

   • If the list is not empty, initialize a temporary pointer to the head and traverse the list to find the last node (the node whose next pointer is NULL).

4. Link the New Node:

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

Illustration

Consider a linked list with the following nodes:

rustCopy codeCurrent List:      Head -> [Node1] -> [Node2] -> [Node3] -> NULL

Now, let's insert a new node with data NewNode at the end:

1. Create a New Node:

   • New Node created with data = NewNode.

2. Check if the List is Empty:

   • The list is not empty; proceed to traverse to the last node.

3. Traverse to the Last Node:

   • Start at the head and move to Node1, then to Node2, and finally to Node3, which is the last node.

4. Link the New Node:

   • Set Node3.next to point to the new node.

The updated list will look like this:

rustCopy codeUpdated List:     Head -> [Node1] -> [Node2] -> [Node3] -> [NewNode] -> NULL

C++ Implementation

cppCopy codestruct Node {
    int data;
    Node* next;
};

// Function to insert a new node at the end
Node* insertAtEnd(Node* head, int newData) {
    // Step 1: Create a new node
    Node* newNode = new Node();
    newNode->data = newData;
    newNode->next = nullptr;

    // Step 2: Check if the list is empty
    if (head == nullptr) {
        head = newNode;
        return head;
    }

    // Step 3: Traverse to the last node
    Node* current = head;
    while (current->next != nullptr) {
        current = current->next;
    }

    // Step 4: Link the new node
    current->next = newNode;

    // Step 5: Return the head
    return head;
}

Java Implementation

javaCopy codeclass Node {
    int data;
    Node next;

    Node(int d) {
        data = d;
        next = null;
    }
}

// Function to insert a new node at the end
Node insertAtEnd(Node head, int newData) {
    // Step 1: Create a new node
    Node newNode = new Node(newData);

    // Step 2: Check if the list is empty
    if (head == null) {
        head = newNode;
        return head;
    }

    // Step 3: Traverse to the last node
    Node current = head;
    while (current.next != null) {
        current = current.next;
    }

    // Step 4: Link the new node
    current.next = newNode;

    // Step 5: Return the head
    return head;
}

Python Implementation

pythonCopy codeclass Node:
    def __init__(self, data):
        self.data = data
        self.next = None

# Function to insert a new node at the end
def insert_at_end(head, new_data):
    # Step 1: Create a new node
    new_node = Node(new_data)

    # Step 2: Check if the list is empty
    if head is None:
        return new_node

    # Step 3: Traverse to the last node
    current = head
    while current.next:
        current = current.next

    # Step 4: Link the new node
    current.next = new_node

    # Step 5: Return the head
    return head

Complexity Analysis

• Time Complexity: O(n)
  (Linear time, as we may need to traverse the entire list to find the last node.)

• Space Complexity: O(1)
  (Only a new node is created regardless of the size of the list.)

3. Deletion of a Node

Algorithm Steps:

1. Check if the List is Empty:

   • If the head pointer is NULL, the list is empty, and there is nothing to delete.

2. Check if the Node to Delete is the Head:

   • If the node to delete is the head node, update the head pointer to the next node.

3. Traverse the List:

   • If the node to delete is not the head, initialize a temporary pointer to the head and traverse the list until you find the node just before the one to delete (let's call it previous).

4. Link the Previous Node to the Next Node:

   • Update the next pointer of the previous node to skip the node to be deleted and point to the node following it.

5. Free the Memory:

   • If applicable (in languages like C++), deallocate the memory used by the deleted node.

Illustration

Consider a linked list with the following nodes:

Current List:      Head -> [Node1] -> [Node2] -> [Node3] -> NULL

Now, let's delete Node2:

1. Check if the List is Empty:

   • The list is not empty; proceed.

2. Check if the Node to Delete is the Head:

   • Node1 is the head, so we don't delete it.

3. Traverse the List:

   • Start at the head and move to Node1. The previous node is now Node1, and Node2 is the node to delete.

4. Link the Previous Node:

   • Set Node1.next to point to Node3, skipping Node2.

5. Updated List:

Updated List:     Head -> [Node1] -> [Node3] -> NULL

C++ Implementation

struct Node {
    int data;
    Node* next;
};

// Function to delete a node by its key
Node* deleteNode(Node* head, int key) {
    // Step 1: Check if the list is empty
    if (head == nullptr) {
        return head;
    }

    // Step 2: Check if the node to delete is the head
    if (head->data == key) {
        Node* temp = head;
        head = head->next;
        delete temp;  // Free the memory
        return head;
    }

    // Step 3: Traverse the list to find the node to delete
    Node* previous = head;
    Node* current = head->next;
    while (current != nullptr) {
        if (current->data == key) {
            // Step 4: Link previous node to the next node
            previous->next = current->next;
            // Step 5: Free the memory
            delete current;  // Free the memory
            return head;
        }
        previous = current;
        current = current->next;
    }

    // Node with the given key not found
    return head;
}

Java Implementation

class Node {
    int data;
    Node next;

    Node(int d) {
        data = d;
        next = null;
    }
}

// Function to delete a node by its key
Node deleteNode(Node head, int key) {
    // Step 1: Check if the list is empty
    if (head == null) {
        return head;
    }

    // Step 2: Check if the node to delete is the head
    if (head.data == key) {
        return head.next; // Return the new head
    }

    // Step 3: Traverse the list to find the node to delete
    Node previous = head;
    Node current = head.next;
    while (current != null) {
        if (current.data == key) {
            // Step 4: Link previous node to the next node
            previous.next = current.next;
            return head;
        }
        previous = current;
        current = current.next;
    }

    // Node with the given key not found
    return head;
}

Python Implementation

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

# Function to delete a node by its key
def delete_node(head, key):
    # Step 1: Check if the list is empty
    if head is None:
        return head

    # Step 2: Check if the node to delete is the head
    if head.data == key:
        return head.next  # Return the new head

    # Step 3: Traverse the list to find the node to delete
    previous = head
    current = head.next
    while current:
        if current.data == key:
            # Step 4: Link previous node to the next node
            previous.next = current.next
            return head
        previous = current
        current = current.next

    # Node with the given key not found
    return head

Complexity Analysis

• Time Complexity: O(n)
  (Linear time, as we may need to traverse the entire list to find the node to delete.)

• Space Complexity: O(1)
  (Only a few pointers are used, regardless of the size of the list.)

4. Search for an Element

Algorithm Steps:

1. 1. Check if the List is Empty:

      • If the head pointer is NULL, the list is empty, and the element cannot be found.

      2. Initialize a Temporary Pointer:

         • Set a temporary pointer to the head of the list to start the traversal.

      3. Traverse the List:

         • While the temporary pointer is not NULL, check if the data in the current node matches the key you are searching for.

      4. Return the Result:

         • If a match is found, return the node or indicate that the element was found.

         • If the traversal ends without finding the element, return an indication that the element was not found.

Illustration

Consider a linked list with the following nodes:

    Current List:      Head -> [Node1] -> [Node2] -> [Node3] -> NULL

Now, let’s search for the element with data Node2:

1. Check if the List is Empty:

   • The list is not empty; proceed.

2. Initialize a Temporary Pointer:

   • Start at the head, which points to Node1.

3. Traverse the List:

   • Check Node1 (not a match).

   • Move to Node2 (match found).

4. Return the Result:

   • The element is found in Node2.)

C++ Implementation

    struct Node {
        int data;
        Node* next;
    };

    // Function to search for an element in the linked list
    bool search(Node* head, int key) {
        // Step 1: Check if the list is empty
        if (head == nullptr) {
            return false; // Element not found
        }

        // Step 2: Initialize a temporary pointer
        Node* current = head;

        // Step 3: Traverse the list
        while (current != nullptr) {
            if (current->data == key) {
                return true; // Element found
            }
            current = current->next;
        }

        // Step 4: Return the result
        return false; // Element not found
    }

Java Implementation

    class Node {
        int data;
        Node next;

        Node(int d) {
            data = d;
            next = null;
        }
    }

    // Function to search for an element in the linked list
    boolean search(Node head, int key) {
        // Step 1: Check if the list is empty
        if (head == null) {
            return false; // Element not found
        }

        // Step 2: Initialize a temporary pointer
        Node current = head;

        // Step 3: Traverse the list
        while (current != null) {
            if (current.data == key) {
                return true; // Element found
            }
            current = current.next;
        }

        // Step 4: Return the result
        return false; // Element not found
    }

Python Implementation

    class Node:
        def __init__(self, data):
            self.data = data
            self.next = None

    # Function to search for an element in the linked list
    def search(head, key):
        # Step 1: Check if the list is empty
        if head is None:
            return False  # Element not found

        # Step 2: Initialize a temporary pointer
        current = head

        # Step 3: Traverse the list
        while current:
            if current.data == key:
                return True  # Element found
            current = current.next

        # Step 4: Return the result
        return False  # Element not found

Complexity Analysis

• Time Complexity: O(n)
  (Linear time, as we may need to traverse the entire list in the worst case.)

• Space Complexity: O(1)
  (Only a few pointers are used regardless of the size of the list.)

5. Reversing a Linked List

Steps of the Algorithm

1. Initialize Three Pointers:

   • Set up three pointers: previous (initialized to NULL), current (initialized to the head of the list), and next (to temporarily store the next node).

2. Traverse the List:

   • While the current pointer is not NULL, perform the following steps:

     • Store the next node: next = current.next

     • Reverse the link: current.next = previous

     • Move the previous and current pointers one step forward: previous = current, current = next

3. Update the Head:

   • Once the traversal is complete, update the head of the list to point to the previous node, which will be the new head after reversal.

Illustration

Consider a linked list with the following nodes:

    Current List:      Head -> [Node1] -> [Node2] -> [Node3] -> NULL

Reversal Process:

1. Initialization:

   • previous = NULL

   • current = Head (pointing to Node1)

2. First Iteration:

   • next = current.next (points to Node2)

   • current.next = previous (now Node1.next is NULL)

   • Move pointers: previous = Node1, current = Node2

3. Second Iteration:

   • next = current.next (points to Node3)

   • current.next = previous (now Node2.next points to Node1)

   • Move pointers: previous = Node2, current = Node3

4. Third Iteration:

   • next = current.next (points to NULL)

   • current.next = previous (now Node3.next points to Node2)

   • Move pointers: previous = Node3, current = NULL

5. Update Head:

   • Head now points to previous (which is Node3).

Updated List:

    Updated List:     Head -> [Node3] -> [Node2] -> [Node1] -> NULL

C++ Implementation

    struct Node {
        int data;
        Node* next;
    };

    // Function to reverse the linked list
    Node* reverse(Node* head) {
        // Step 1: Initialize three pointers
        Node* previous = nullptr;
        Node* current = head;
        Node* next = nullptr;

        // Step 2: Traverse the list
        while (current != nullptr) {
            // Store the next node
            next = current->next;
            // Reverse the link
            current->next = previous;
            // Move pointers forward
            previous = current;
            current = next;
        }

        // Step 3: Update the head
        head = previous;
        return head;
    }

Java Implementation

    class Node {
        int data;
        Node next;

        Node(int d) {
            data = d;
            next = null;
        }
    }

    // Function to reverse the linked list
    Node reverse(Node head) {
        // Step 1: Initialize three pointers
        Node previous = null;
        Node current = head;
        Node next = null;

        // Step 2: Traverse the list
        while (current != null) {
            // Store the next node
            next = current.next;
            // Reverse the link
            current.next = previous;
            // Move pointers forward
            previous = current;
            current = next;
        }

        // Step 3: Update the head
        head = previous;
        return head;
    }

Python Implementation

    class Node:
        def __init__(self, data):
            self.data = data
            self.next = None

    # Function to reverse the linked list
    def reverse(head):
        # Step 1: Initialize three pointers
        previous = None
        current = head
        next_node = None

        # Step 2: Traverse the list
        while current:
            # Store the next node
            next_node = current.next
            # Reverse the link
            current.next = previous
            # Move pointers forward
            previous = current
            current = next_node

        # Step 3: Update the head
        head = previous
        return head

Complexity Analysis

• Time Complexity: O(n)
  (Linear time, as we need to traverse the entire list once to reverse it.)

• Space Complexity: O(1)
  (Only a few pointers are used, regardless of the size of the list.)