Linked List, Data Structures

Linked List

A linked list is a fundamental data structure used in computer science to organize and store data efficiently. Unlike arrays, linked lists consist of nodes, where each node contains data and a reference (or link) to the next node in the sequence. This structure allows for dynamic memory allocation and efficient insertions and deletions, making linked lists highly versatile and useful for various applications.

Comparison with Arrays

Linked lists and arrays are both used to store collections of elements, but they have key differences that affect their performance and usage:

• Memory Allocation:

  • Arrays: Use contiguous memory allocation. The size of the array is fixed at the time of its creation, which can lead to wasted memory if the array is not fully utilized or insufficient memory if it needs to be resized.
  • Linked Lists: Use dynamic memory allocation. Each element (node) is allocated separately, allowing the linked list to grow or shrink in size as needed without reallocating memory for the entire structure.

• Insertion and Deletion:

  • Arrays: Inserting or deleting elements in an array requires shifting elements to maintain the order, which can be time-consuming (O(n) time complexity for both operations).
  • Linked Lists: Insertion and deletion operations are more efficient (O(1) time complexity) as they involve updating pointers rather than shifting elements.

• Access Time:

  • Arrays: Provide constant-time access (O(1)) to elements using their indices, making them suitable for scenarios where frequent access to elements is required.
  • Linked Lists: Require sequential access (O(n) time complexity) to reach a specific element, which can be slower compared to arrays.

Basic Terminologies Related to Linked Lists

Understanding the fundamental terminologies associated with linked lists is essential for grasping their structure and operations:

• Node: The basic unit of a linked list. Each node contains the data to be stored and a pointer (or reference) to the next node in the list.
• Head: The first node in the linked list. It serves as the entry point for accessing the list. If the linked list is empty, the head points to null.
• Tail: The last node in the linked list. In a singly linked list, the tail's next pointer points to null, indicating the end of the list.
• Pointer/Reference: A field in each node that stores the address of the next node in the sequence. This allows the nodes to be linked together.
• Singly Linked List: A type of linked list where each node has a single pointer to the next node. This is the simplest form of a linked list.
• Doubly Linked List: A more complex form of a linked list where each node has two pointers: one to the next node and one to the previous node. This allows traversal in both directions.
• Circular Linked List: A variation of linked lists where the last node points back to the first node, forming a circular structure. This can be implemented as either a singly or doubly linked list.

Creating the Node

In a linked list, a node is the fundamental building block. Each node contains data and a pointer to the next node. Here’s how to define and create a node in C++:

class Node {
public:
    int data;
    Node* next;

    Node(int val) {
        data = val;
        next = nullptr;
    }
};

// Creating a node with data value 10
Node* newNode = new Node(10);

Operations on Linked List

Insertion of Data

Insertion at the Beginning:
To insert a node at the beginning of a linked list, create a new node and set its next pointer to the current head. Then, update the head to this new node.

void insertAtBeginning(Node*& head, int val) {
    Node* newNode = new Node(val);
    newNode->next = head;
    head = newNode;
}

Time Complexity: O(1)

Insertion at the End:
To insert a node at the end of a linked list, traverse to the last node and set its next pointer to the new node.

void insertAtEnd(Node*& head, int val) {
    Node* newNode = new Node(val);
    if (head == nullptr) {
        head = newNode;
        return;
    }
    Node* temp = head;
    while (temp->next != nullptr) {
        temp = temp->next;
    }
    temp->next = newNode;
}

Time Complexity: O(n)

Insertion at a Specific Position:
To insert a node at a specific position, traverse to the node just before the desired position and adjust the pointers accordingly.

void insertAtPosition(Node*& head, int val, int position) {
    Node* newNode = new Node(val);
    if (position == 0) {
        newNode->next = head;
        head = newNode;
        return;
    }
    Node* temp = head;
    for (int i = 0; temp != nullptr && i < position - 1; ++i) {
        temp = temp->next;
    }
    if (temp == nullptr) return; // Position is out of bounds
    newNode->next = temp->next;
    temp->next = newNode;
}

Time Complexity: O(n)

Traversing a Linked List

To traverse a linked list means to visit each node in the list, starting from the head, and accessing its data or performing operations on it.

void traverseLinkedList(Node* head) {
    Node* temp = head;
    while (temp != nullptr) {
        cout << temp->data << " ";
        temp = temp->next;
    }
}

Time Complexity: O(n)

Deleting Elements from a Linked List

Deleting elements from a linked list involves removing nodes from the list while maintaining the integrity of the structure.

Deletion from the Beginning:
To delete a node from the beginning of a linked list, update the head to point to the next node, and deallocate memory for the removed node.

void deleteFromBeginning(Node*& head) {
    if (head == nullptr) return;
    Node* temp = head;
    head = head->next;
    delete temp;
}

Time Complexity: O(1)

Deletion from the End:
To delete a node from the end of a linked list, traverse to the second-to-last node, update its next pointer to null, and deallocate memory for the last node.

void deleteFromEnd(Node*& head) {
    if (head == nullptr || head->next == nullptr) {
        delete head;
        head = nullptr;
        return;
    }
    Node* temp = head;
    while (temp->next->next != nullptr) {
        temp = temp->next;
    }
    delete temp->next;
    temp->next = nullptr;
}

Time Complexity: O(n)

Deletion from a Specific Position:
To delete a node from a specific position, traverse to the node just before the target position, update its next pointer to skip the target node, and deallocate memory for the removed node.

void deleteAtPosition(Node*& head, int position) {
    if (head == nullptr) return;
    Node* temp = head;
    if (position == 0) {
        head = head->next;
        delete temp;
        return;
    }
    for (int i = 0; temp != nullptr && i < position - 1; ++i) {
        temp = temp->next;
    }
    if (temp == nullptr || temp->next == nullptr) return; // Position is out of bounds
    Node* nodeToDelete = temp->next;
    temp->next = temp->next->next;
    delete nodeToDelete;
}

Time Complexity: O(n)

Searching and Updating Values in a Linked List

Searching for a specific value in a linked list involves traversing the list and comparing each node's data with the target value. Updating the value of a node requires locating the node with the target value and modifying its data field.

Searching for a Value:
To search for a value in a linked list, traverse the list until the target value is found or the end of the list is reached.

bool searchValue(Node* head, int target) {
    Node* temp = head;
    while (temp != nullptr) {
        if (temp->data == target) {
            return true; // Value found
        }
        temp = temp->next;
    }
    return false; // Value not found
}

Time Complexity: O(n)

Updating a Value:
To update the value of a node in a linked list, locate the node with the target value and modify its data field.

void updateValue(Node* head, int oldValue, int newValue) {
    Node* temp = head;
    while (temp != nullptr) {
        if (temp->data == oldValue) {
            temp->data = newValue; // Update value
            return;
        }
        temp = temp->next;
    }
}

Time Complexity: O(n)

Reversing a Linked List

Reversing a linked list involves changing the direction of pointers so that the last node becomes the first node, and so on.

Node* reverseLinkedList(Node* head) {
    Node* prev = nullptr;
    Node* current = head;
    Node* nextNode = nullptr;

    while (current != nullptr) {
        nextNode = current->next; // Store next node
        current->next = prev; // Reverse pointer
        prev = current; // Move pointers one position ahead
        current = nextNode;
    }

    return prev; // New head of the reversed list
}

Time Complexity: O(n)

Full Code Implementation of Singly Linked List

Here's a comprehensive C++ implementation of a singly linked list, encapsulated within a class. The implementation includes various functions such as insertion, deletion, traversal, searching, updating values, and reversing the list.

#include <iostream>
using namespace std;

class LinkedList {
private:
    class Node {
    public:
        int data;
        Node* next;
        Node(int val) {
            data = val;
            next = nullptr;
        }
    };
    Node* head;

public:
    LinkedList() {
        head = nullptr;
    }

    void insertAtBeginning(int val) {
        Node* newNode = new Node(val);
        newNode->next = head;
        head = newNode;
    }

    void insertAtEnd(int val) {
        Node* newNode = new Node(val);
        if (head == nullptr) {
            head = newNode;
            return;
        }
        Node* temp = head;
        while (temp->next != nullptr) {
            temp = temp->next;
        }
        temp->next = newNode;
    }

    void insertAtPosition(int val, int position) {
        Node* newNode = new Node(val);
        if (position == 0) {
            newNode->next = head;
            head = newNode;
            return;
        }
        Node* temp = head;
        for (int i = 0; temp != nullptr && i < position - 1; ++i) {
            temp = temp->next;
        }
        if (temp == nullptr) return; // Position is out of bounds
        newNode->next = temp->next;
        temp->next = newNode;
    }

    void deleteFromBeginning() {
        if (head == nullptr) return;
        Node* temp = head;
        head = head->next;
        delete temp;
    }

    void deleteFromEnd() {
        if (head == nullptr) return;
        if (head->next == nullptr) {
            delete head;
            head = nullptr;
            return;
        }
        Node* temp = head;
        while (temp->next->next != nullptr) {
            temp = temp->next;
        }
        delete temp->next;
        temp->next = nullptr;
    }

    void deleteAtPosition(int position) {
        if (head == nullptr) return;
        Node* temp = head;
        if (position == 0) {
            head = head->next;
            delete temp;
            return;
        }
        for (int i = 0; temp != nullptr && i < position - 1; ++i) {
            temp = temp->next;
        }
        if (temp == nullptr || temp->next == nullptr) return; // Position is out of bounds
        Node* nodeToDelete = temp->next;
        temp->next = temp->next->next;
        delete nodeToDelete;
    }

    void traverseLinkedList() const {
        Node* temp = head;
        while (temp != nullptr) {
            cout << temp->data << " ";
            temp = temp->next;
        }
        cout << endl;
    }

    bool searchValue(int target) const {
        Node* temp = head;
        while (temp != nullptr) {
            if (temp->data == target) {
                return true; // Value found
            }
            temp = temp->next;
        }
        return false; // Value not found
    }

    void updateValue(int oldValue, int newValue) {
        Node* temp = head;
        while (temp != nullptr) {
            if (temp->data == oldValue) {
                temp->data = newValue; // Update value
                return;
            }
            temp = temp->next;
        }
    }

    void reverseLinkedList() {
        Node* prev = nullptr;
        Node* current = head;
        Node* nextNode = nullptr;
        while (current != nullptr) {
            nextNode = current->next; // Store next node
            current->next = prev; // Reverse pointer
            prev = current; // Move pointers one position ahead
            current = nextNode;
        }
        head = prev;
    }

    int getLength() const {
        int length = 0;
        Node* temp = head;
        while (temp != nullptr) {
            length++;
            temp = temp->next;
        }
        return length;
    }

    bool isEmpty() const {
        return head == nullptr;
    }

    ~LinkedList() {
        Node* temp;
        while (head != nullptr) {
            temp = head;
            head = head->next;
            delete temp;
        }
    }
};

int main() {
    LinkedList list;

    list.insertAtEnd(10);
    list.insertAtEnd(20);
    list.insertAtEnd(30);
    cout << "List after inserting at the end: ";
    list.traverseLinkedList();

    list.insertAtBeginning(5);
    cout << "List after inserting at the beginning: ";
    list.traverseLinkedList();

    list.insertAtPosition(15, 2);
    cout << "List after inserting at position 2: ";
    list.traverseLinkedList();

    cout << "Length of the list: " << list.getLength() << endl;

    list.deleteFromBeginning();
    cout << "List after deleting from the beginning: ";
    list.traverseLinkedList();

    list.deleteFromEnd();
    cout << "List after deleting from the end: ";
    list.traverseLinkedList();

    list.deleteAtPosition(1);
    cout << "List after deleting at position 1: ";
    list.traverseLinkedList();

    if (list.searchValue(20)) {
        cout << "Value 20 found in the list" << endl;
    } else {
        cout << "Value 20 not found in the list" << endl;
    }

    list.updateValue(15, 25);
    cout << "List after updating value 15 to 25: ";
    list.traverseLinkedList();

    list.reverseLinkedList();
    cout << "List after reversing: ";
    list.traverseLinkedList();

    return 0;
}

This code defines a LinkedList class with various methods to manipulate the linked list, such as inserting, deleting, traversing, searching, updating values, reversing, checking if the list is empty, and getting the length of the list. The main function demonstrates the usage of these methods.

Doubly Linked List

A doubly linked list is an extension of a singly linked list where each node contains an additional pointer to the previous node, allowing for traversal in both directions. This bidirectional nature offers greater flexibility in certain operations compared to a singly linked list.

Creating a Node

To create a node in a doubly linked list, you need to define a class with data, a pointer to the next node, and a pointer to the previous node.

class DoublyNode {
public:
    int data;
    DoublyNode* next;
    DoublyNode* prev;

    DoublyNode(int val) {
        data = val;
        next = nullptr;
        prev = nullptr;
    }
};

// Creating a node with data value 10
DoublyNode* newNode = new DoublyNode(10);

Advantages Over Singly Linked List

• Bidirectional Traversal:

  • Doubly Linked List: Can be traversed in both forward and backward directions, making it more versatile for operations that require access to previous elements.
  • Singly Linked List: Can only be traversed in one direction.

• Easier Deletion:

  • Doubly Linked List: Deleting a node is easier as you have direct access to the previous node.
  • Singly Linked List: Requires traversal from the head to find the previous node for deletion.

• Efficient Insertion/Deletion:

  • Doubly Linked List: Insertion and deletion operations at both ends (head and tail) and at specific positions are more efficient due to the presence of both next and previous pointers.
  • Singly Linked List: These operations are generally less efficient because the list can only be traversed in one direction.

Time Complexity Advantages

• Deletion of a Node:

  • Doubly Linked List: O(1) if you have a pointer to the node to be deleted because you can directly access the previous node.
  • Singly Linked List: O(n) because you need to traverse from the head to find the previous node.

• Insertion Before a Given Node:

  • Doubly Linked List: O(1) if you have a pointer to the node, as you can directly adjust the pointers of the previous node.
  • Singly Linked List: O(n) as it requires traversal to the previous node.

• Reversing the List:

  • Doubly Linked List: Slightly more efficient due to bidirectional pointers, though both types have O(n) complexity.
  • Singly Linked List: O(n) but requires extra steps to reverse the pointers.

Circular Linked List

A circular linked list is a variation of a linked list where the last node points back to the first node, forming a circular structure. This type of list can be singly or doubly linked and offers benefits in certain scenarios, such as round-robin scheduling.

Creating a Node

To create a node in a circular linked list, you define a class similar to a regular singly or doubly linked list, but with the understanding that the next pointer of the last node points back to the head.

class CircularNode {
public:
    int data;
    CircularNode* next;

    CircularNode(int val) {
        data = val;
        next = nullptr;
    }
};

// Creating a node with data value 10
CircularNode* newNode = new CircularNode(10);

Advantages Over Singly Linked List

• Circular Nature:

  • Circular Linked List: The list can be traversed from any node, making it useful for applications like round-robin scheduling and buffering.
  • Singly Linked List: The list ends at the last node, which does not point back to the head.

• Efficient Circular Traversal:

  • Circular Linked List: Allows continuous traversal without needing to restart from the head after reaching the end.
  • Singly Linked List: Traversal stops at the end, and restarting requires going back to the head.

Time Complexity Advantages

• Insertion at the End:

  • Circular Linked List: O(1) if you maintain a tail pointer, as the new node can be added after the tail, and the tail pointer is updated.
  • Singly Linked List: O(n) as it requires traversal to the end of the list.

• Traversal for Operations:

  • Circular Linked List: O(n) for traversal, but traversal can continue seamlessly from end to start.
  • Singly Linked List: O(n) for traversal, stopping at the end.