Linked Lists in C++

Linked lists are a fundamental data structure and are used widely in programming. They are useful for storing and manipulating data, as well as creating complex algorithms. Linked lists are a type of linear data structure, in which each element is a separate object that contains both data (value) and a link (reference) to the next element in the sequence. In this article, we will discuss linked lists in C++, and we will learn how to implement them using classes, as well as how to traverse, insert and delete elements from linked lists. We will also cover singly linked lists, doubly linked lists, and skip lists.

Overview of Linked Lists

Linked lists are a type of data structure that is used to store and manipulate data in an organized manner. Each element in the list is a separate object, and each object contains both data and a link (reference) to the next element in the sequence. This type of data structure can be used to store and manipulate any type of data, such as numbers, strings, and objects.

Linked lists have several advantages over other types of data structures, such as arrays and trees. For example, they are more efficient in terms of both time and space. They can also grow and shrink dynamically, and can be easily modified by adding or deleting elements.

Implementing Linked Lists Using Classes

Linked lists can be implemented in C++ using classes. Each node in the list is defined as a separate object, and each object contains both data and a link (reference) to the next element in the sequence. The following code snippet shows how to create a simple linked list class in C++:

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

The Node class has two data members: data, which stores the value of the node, and next, which stores the address of the next node in the list.

Singly Linked Lists

A singly linked list is a type of linked list in which each node contains a link (reference) to the next node in the list, but not to the previous node. This type of linked list is often used in applications where data needs to be inserted or deleted from the beginning or end of the list.

The following code snippet shows how to create a singly linked list in C++:

class SinglyLinkedList {
    private:
        Node* head;
        Node* tail;
    public:
        SinglyLinkedList() {
            head = nullptr;
            tail = nullptr;
        }
        void insertAtBeginning(int val) {
            Node* newNode = new Node;
            newNode->data = val;
            newNode->next = head;
            head = newNode;
        }
};

The SinglyLinkedList class has two data members: head, which stores a pointer to the first node in the list, and tail, which stores a pointer to the last node in the list. The insertAtBeginning() method inserts a new node at the beginning of the list.

Doubly Linked Lists

A doubly linked list is a type of linked list in which each node contains both a link (reference) to the next node in the list, and a link to the previous node in the list. This type of linked list is often used in applications where data needs to be inserted or deleted from any position in the list.

The following code snippet shows how to create a doubly linked list in C++:

class DoublyLinkedList {
    private:
        Node* head;
        Node* tail;
    public:
        DoublyLinkedList() {
            head = nullptr;
            tail = nullptr;
        }
        void insertAtBeginning(int val) {
            Node* newNode = new Node;
            newNode->data = val;
            newNode->next = head;
            newNode->prev = nullptr;
            if (head != nullptr)
                head->prev = newNode;
            head = newNode;
        }
};

The DoublyLinkedList class has two data members: head, which stores a pointer to the first node in the list, and tail, which stores a pointer to the last node in the list. The insertAtBeginning() method inserts a new node at the beginning of the list.

Traversing Linked Lists

Traversing a linked list means visiting each node in the list, starting from the head node. This can be done in several ways, including iterative and recursive approaches. The following code snippet shows how to traverse a linked list in a recursive manner:

void traverse(Node* head) {
    if (head == nullptr)
        return;
    std::cout << head->data << std::endl;
    traverse(head->next);
}

The traverse() method prints the data stored in each node of the list. It uses recursion to visit each node in the list.

Inserting and Deleting Elements From Linked Lists

Inserting and deleting elements from linked lists can be done in several ways. Inserting a new element can be done at the beginning, end, or any other position in the list. Likewise, deleting an element can be done from the beginning, end, or any other position in the list.

The following code snippet shows how to insert a new element at the beginning of a singly linked list:

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

The insertAtBeginning() method inserts a new node at the beginning of the list. It sets the new node’s next pointer to the current head node, and sets the head pointer to the new node.

The following code snippet shows how to delete an element from the end of a singly linked list:

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

The deleteFromEnd() method deletes the last node in the list. It first finds the last node in the list, and then sets the next pointer of the previous node to nullptr. Finally, it deletes the last node.

Skip Lists

A skip list is a type of linked list in which each node has multiple levels of links that point to different elements in the list. This type of linked list is useful for searching and sorting data, as it allows for faster access to elements in the list.

The following code snippet shows how to create a skip list in C++:

class SkipList {
    private:
        Node* head;
        Node* tail;
    public:
        SkipList() {
            head = nullptr;
            tail = nullptr;
        }
        void insert(int val, int level) {
            Node* newNode = new Node;
            newNode->data = val;
            newNode->next = nullptr;
            newNode->level = level;
            if (head == nullptr) {
                head = newNode;
                tail = newNode;
            }
            else {
                tail->next = newNode;
                tail = newNode;
            }
        }
};

The SkipList class has two data members: head, which stores a pointer to the first node in the list, and tail, which stores a pointer to the last node in the list. The insert() method inserts a new node into the list. It sets the new node’s level to the specified value, and then sets the next pointer of the previous node to the new node.

Conclusion

In this article, we have discussed linked lists in C++, and how to implement them using classes. We have also discussed singly linked lists, doubly linked lists, and skip lists. We have also seen how to traverse, insert and delete elements from linked lists.

Exercises

void deleteElement(int val, Node* head) {
    Node* current = head;
    Node* prev = nullptr;
    while (current != nullptr && current->data != val) {
        prev = current;
        current = current->next;
    }
    if (current == nullptr)
        return;
    if (prev != nullptr)
        prev->next = current->next;
    else
        head = current->next;
    delete current;
}

Node* searchElement(int val, Node* head) {
    Node* current = head;
    while (current != nullptr && current->data != val)
        current = current->next;
    return current;
}

void insertAtLevel(int val, int level, Node* head) {
    Node* current = head;
    Node* prev = nullptr;
    while (current != nullptr && current->level > level) {
        prev = current;
        current = current->next;
    }
    if (current == nullptr || current->level < level)
        return;
    Node* newNode = new Node;
    newNode->data = val;
    newNode->level = level;
    newNode->next = current;
    if (prev != nullptr)
        prev->next = newNode;
    else
        head = newNode;
}

void deleteElement(int val, Node* head) {
    Node* current = head;
    Node* prev = nullptr;
    while (current != nullptr && current->data != val) {
        prev = current;
        current = current->next;
    }
    if (current == nullptr)
        return;
    if (prev != nullptr)
        prev->next = current->next;
    else
        head = current->next;
    delete current;
}

Node* searchElement(int val, Node* head) {
    Node* current = head;
    while (current != nullptr && current->data != val)
        current = current->next;
    return current;
}