Types of Linked Lists | DSA in C++ - Software Development PDF Download

Introduction

Linked lists are an essential data structure in computer science and are widely used in various algorithms and applications. They provide an efficient way to store and manipulate data dynamically. In this article, we will explore the different types of linked lists in C++ and provide simple code examples to help beginners understand their usage and implementation.

Singly Linked List

A singly linked list is a linear data structure where each element, called a node, consists of a value and a pointer to the next node. The last node points to NULL, indicating the end of the list. Here's an example of a singly linked list in C++:

class Node {

public:

    int data;

    Node* next;

};

// Creating a singly linked list

Node* head = nullptr;

void insertNode(int value) {

    Node* newNode = new Node();

    newNode->data = value;

    newNode->next = nullptr;

    

    if (head == nullptr) {

        head = newNode;

    } else {

        Node* temp = head;

        while (temp->next != nullptr) {

            temp = temp->next;

        }

        temp->next = newNode;

    }

}

void displayList() {

    Node* temp = head;

    while (temp != nullptr) {

        cout << temp->data << " ";

        temp = temp->next;

    }

}

int main() {

    insertNode(10);

    insertNode(20);

    insertNode(30);

    displayList();  // Output: 10 20 30

    return 0;

}

Doubly Linked List

A doubly linked list is similar to a singly linked list, but each node has two pointers: one pointing to the previous node and the other to the next node. This allows for traversal in both directions. Here's an example of a doubly linked list in C++:

class Node {

public:

    int data;

    Node* prev;

    Node* next;

};

// Creating a doubly linked list

Node* head = nullptr;

void insertNode(int value) {

    Node* newNode = new Node();

    newNode->data = value;

    newNode->prev = nullptr;

    newNode->next = nullptr;

    

    if (head == nullptr) {

        head = newNode;

    } else {

        Node* temp = head;

        while (temp->next != nullptr) {

            temp = temp->next;

        }

        temp->next = newNode;

        newNode->prev = temp;

    }

}

void displayList() {

    Node* temp = head;

    while (temp != nullptr) {

        cout << temp->data << " ";

        temp = temp->next;

    }

}

int main() {

    insertNode(10);

    insertNode(20);

    insertNode(30);

    displayList();  // Output: 10 20 30

    return 0;

}

Circular Linked List

A circular linked list is a variation of a singly or doubly linked list where the last node points back to the first node, creating a circular structure. It can be implemented using either singly or doubly linked list techniques. Here's an example of a circular linked list in C++:

class Node {

public:

    int data;

    Node* next;

};

// Creating a circular linked list

Node* head = nullptr;

void insertNode(int value) {

    Node* newNode = new Node();

    newNode->data = value;

    newNode->next = nullptr;  

    if (head == nullptr) {

        head = newNode;

        newNode->next = head;  // Pointing back to the head

    } else {

        Node* temp = head;

        while (temp->next != head) {

            temp = temp->next;

        }

        temp->next = newNode;

        newNode->next = head;  // Pointing back to the head

    }

}

void displayList() {

    Node* temp = head;

    do {

        cout << temp->data << " ";

        temp = temp->next;

    } while (temp != head);

}

int main() {

    insertNode(10);

    insertNode(20);

    insertNode(30);

    displayList();  // Output: 10 20 30

    return 0;

}

Code Examples

The above code examples demonstrate the creation and display of singly, doubly, and circular linked lists. You can modify these examples to perform other operations such as insertion, deletion, searching, and more.

Sample Problems

Problem 1: Write a function to count the number of nodes in a singly linked list.

int countNodes() {

    int count = 0;

    Node* temp = head;

    while (temp != nullptr) {

        count++;

        temp = temp->next;

    }

    return count;

}

Problem 2: Write a function to reverse a doubly linked list.

void reverseList() {

    Node* current = head;

    Node* temp = nullptr;  

    while (current != nullptr) {

        temp = current->prev;

        current->prev = current->next;

        current->next = temp;

        current = current->prev;

    }   

    if (temp != nullptr) {

        head = temp->prev;

    }

}

Conclusion

Linked lists are powerful data structures that provide flexibility and efficiency in managing dynamic data. Understanding the different types of linked lists, including singly, doubly, and circular, is crucial for building more complex algorithms. By practicing and implementing the provided code examples, you can deepen your understanding of linked lists and enhance your problem-solving skills in programming.