What is Linked List?

A linked list is a fundamental data structure in computer science used for storing and organizing a collection of elements called nodes. Unlike arrays, which use contiguous memory, linked lists utilize non-contiguous memory and each node contains two parts: the data and a reference (pointer) to the next node in the sequence.

There are different types of linked lists, but the most common ones are singly linked lists and doubly linked lists:

Singly Linked List

• In a singly linked list, each node contains data and a pointer/reference to the next node. The last node points to NULL, indicating the end of the list.
• The first node is called the head, and it is used to traverse the list.

Doubly Linked List

• In a doubly linked list, each node has two pointers/references: one to the next node and one to the previous node.
• The first node’s previous pointer and the last node’s next pointer are set to NULL.

Advantages of Linked Lists

• Dynamic Size: Linked lists can dynamically grow or shrink, unlike arrays.
• Insertion and Deletion: Insertion and deletion operations are efficient, especially in singly linked lists, as no shifting of elements is required.
• Memory Efficiency: Linked lists can efficiently utilize memory, allocating memory for nodes as needed.

Disadvantages of Linked Lists

• Random Access: Unlike arrays, linked lists do not allow for random access to elements. Traversing from the beginning is necessary to reach specific elements.
• Extra Memory: Linked lists require extra memory for storing the pointers/references, which can increase memory overhead compared to arrays.
• Cache Inefficiency: Linked lists may cause more cache misses due to non-contiguous memory locations.

Common Operations on Linked Lists

1. Insertion: Inserting a new node at the beginning, end, or any position in the linked list.
2. Deletion: Deleting a node from the list, either from the beginning, end, or any position.
3. Traversal: Iterating through the linked list to access or modify its elements.
4. Searching: Finding a specific element in the linked list based on the value.
5. Concatenation: Combining two linked lists together.

Singly Linked List Implementation in C++

#include <iostream>

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

    Node(int data) {
        this->data = data;
        this->next = nullptr;
    }
};

class LinkedList {
private:
    Node* head;

public:
    LinkedList() {
        head = nullptr;
    }

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

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

int main() {
    LinkedList list;
    list.insert(5);
    list.insert(10);
    list.insert(15);

    list.display(); // Output: 15 10 5

    return 0;
}

In this example, we implemented a simple singly linked list in C++. We defined two classes, Node representing a single node, and LinkedList representing the list itself. The LinkedList class contains functions to insert elements at the beginning and display the list. The list 15 -> 10 -> 5 is displayed as 15 10 5.

Linked lists are crucial data structures used in various applications, and understanding their concepts and implementations is essential for any programmer.