Linked Lists | Data Structures | Cplusplus Tutorial

Introduction to Linked Lists

Linked lists are a fundamental data structure used in computer science. Unlike arrays, linked lists consist of nodes where each node contains a data part and a reference to the next node in the sequence. This structure allows for efficient insertion and deletion operations.

Types of Linked Lists

There are several types of linked lists:

Singly Linked List: Each node points to the next node and the last node points to null.
Doubly Linked List: Each node has pointers to both the next and the previous node.
Circular Linked List: The last node points back to the first node, forming a circle.

Node Structure

In C++, a node can be represented as a class or struct. Here is an example of a node for a singly linked list:

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

Creating a Linked List

To create a linked list, we need to initialize the head pointer to null and then add nodes to the list. Here is an example:

#include <iostream>
using namespace std;

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

int main() {
    Node* head = nullptr;
    Node* second = nullptr;
    Node* third = nullptr;

    head = new Node();
    second = new Node();
    third = new Node();

    head->data = 1;
    head->next = second;

    second->data = 2;
    second->next = third;

    third->data = 3;
    third->next = nullptr;

    return 0;
}

Traversing a Linked List

To traverse a linked list, we start from the head and follow the next pointers until we reach the end of the list. Here is a function to print all elements of a linked list:

#include <iostream>
using namespace std;

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

void printList(Node* n) {
    while (n != nullptr) {
        cout << n->data << " ";
        n = n->next;
    }
}

int main() {
    Node* head = nullptr;
    Node* second = nullptr;
    Node* third = nullptr;

    head = new Node();
    second = new Node();
    third = new Node();

    head->data = 1;
    head->next = second;

    second->data = 2;
    second->next = third;

    third->data = 3;
    third->next = nullptr;

    printList(head);

    return 0;
}

Output: 1 2 3

Inserting a Node

We can insert a new node at the beginning, middle, or end of a linked list. Here is a function to insert a new node at the beginning:

void push(Node** head_ref, int new_data) {
    Node* new_node = new Node();
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}

Deleting a Node

To delete a node in a linked list, we need to find the previous node of the node to be deleted and change its next pointer. Here is a function to delete a node by key:

void deleteNode(Node** head_ref, int key) {
    Node* temp = *head_ref;
    Node* prev = nullptr;

    if (temp != nullptr && temp->data == key) {
        *head_ref = temp->next;
        delete temp;
        return;
    }

    while (temp != nullptr && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }

    if (temp == nullptr) return;

    prev->next = temp->next;
    delete temp;
}

Conclusion

Linked lists are a versatile data structure that provide dynamic memory allocation, efficient insertion, and deletion. Understanding linked lists is fundamental to mastering data structures in computer science.

Linked Lists Tutorial