Data Structures in C++

Previous Lesson

Linked list data structure

Data Structures in C++ Linked list data structure

Linked lists are fundamental data structures in computer science that provide a dynamic way to store and manipulate data. Unlike arrays, which store elements in contiguous memory locations, linked lists use nodes that are connected via pointers. This allows linked lists to efficiently grow or shrink as needed, providing flexibility in managing memory.

Key Characteristics of Linked Lists

  • Nodes: A linked list consists of nodes where each node contains data and a pointer to the next node in the sequence.
  • Head: The starting node of the linked list is known as the head.
  • Tail: The last node in the list, which points to null, indicating the end of the list.
  • Dynamic Size: The list can expand or contract dynamically by adding or removing nodes.

Types of Linked Lists

There are several types of linked lists, each suited for different applications:

1. Singly Linked List

A singly linked list contains nodes with a single pointer to the next node.

struct Node {
    int data;
    Node* next;

    Node(int val) : data(val), next(nullptr) {}
};

2. Doubly Linked List

In a doubly linked list, nodes contain pointers to both the next and previous nodes.

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

    Node(int val) : data(val), next(nullptr), prev(nullptr) {}
};

3. Circular Linked List

A circular linked list is similar to a singly linked list, but the last node points back to the head.

struct Node {
    int data;
    Node* next;

    Node(int val) : data(val), next(nullptr) {}
};

Basic Operations on Linked Lists

Here are some basic operations commonly performed on linked lists:

1. Insertion

  • At Head: Insert a new node at the beginning.
  • At Tail: Insert a new node at the end.
  • At Middle: Insert a new node after a specified node.

Inserting in a Singly Linked List

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

void insertTail(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;
}

void insertAfter(Node* prevNode, int val) {
    if (prevNode == nullptr) return;
    Node* newNode = new Node(val);
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}

2. Deletion

  • From Head: Remove the first node.
  • From Tail: Remove the last node.
  • By Value: Remove a node by its value.

Deleting in a Singly Linked List

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

void deleteTail(Node*& head) {
    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 deleteByValue(Node*& head, int val) {
    if (head == nullptr) return;
    if (head->data == val) {
        Node* temp = head;
        head = head->next;
        delete temp;
        return;
    }
    Node* temp = head;
    while (temp->next != nullptr && temp->next->data != val) {
        temp = temp->next;
    }
    if (temp->next == nullptr) return;
    Node* toDelete = temp->next;
    temp->next = temp->next->next;
    delete toDelete;
}

3. Traversal

Traversing a linked list involves visiting each node sequentially to access or modify data.

Traversing a Singly Linked List

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

Advanced Linked List Operations

  • Reverse: Reversing a linked list to change the order of elements.
  • Merge: Merging two linked lists into one.
  • Sort: Sorting a linked list using algorithms like merge sort.

Reversing a Singly Linked List

Node* reverse(Node* head) {
    Node* prev = nullptr;
    Node* curr = head;
    Node* next = nullptr;

    while (curr != nullptr) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

Applications of Linked Lists

Linked lists are used in various applications:

  • Dynamic Memory Allocation: Linked lists can manage memory dynamically for efficient usage.
  • Implementation of Data Structures: Stacks, queues, and hash tables often use linked lists.
  • Graph Representations: Adjacency lists represent sparse graphs efficiently.

Pros and Cons of Linked Lists

Pros

  • Dynamic Size: Can grow or shrink dynamically without reallocation.
  • Efficient Insertion/Deletion: Especially at the head or tail.

Cons

  • Random Access: Cannot access elements directly by index.
  • Memory Overhead: Additional space for pointers.

Doubly Linked List: An In-Depth Look

A doubly linked list provides a bidirectional structure where each node points to both the next and the previous node. This allows traversal in both directions.

Basic Operations on Doubly Linked Lists

Insertion

void insertHead(Node*& head, int val) {
    Node* newNode = new Node(val);
    newNode->next = head;
    if (head != nullptr) head->prev = newNode;
    head = newNode;
}

void insertTail(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;
    newNode->prev = temp;
}

Deletion

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

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

Circular Linked List: An In-Depth Look

A circular linked list forms a circular structure where the last node points back to the head, forming a loop. This allows for continuous traversal and is often used in applications where the data needs to be processed in a circular manner.

Circular Linked List Operations

Insertion

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

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

Deletion

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

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

Practical Use Cases

  • Operating System Scheduling: Circular linked lists can manage the scheduling of tasks in operating systems.
  • Data Streaming Applications: Doubly linked lists efficiently manage buffers for streaming data.

Conclusion

Linked lists provide flexible and efficient ways to manage dynamic data in C++. Their variations allow them to cater to different scenarios, from basic singly linked lists to complex circular or doubly linked lists. Understanding their operations, advantages, and limitations can help in choosing the right type of linked list for a specific application.

Previous Lesson
Back to Tutorial