Linked Lists

Introduction

A linked list is a linear data structure, where elements are stored in nodes, and each node points to the next node in the list. It is a dynamic data structure, meaning its size can change during the execution of a program. Linked lists are useful when efficient insertion and deletion of elements are required.

Types of Linked Lists

There are several types of linked lists:

• Singly Linked List: Each node has a pointer to the next node in the list.
• Doubly Linked List: Each node has pointers to both the next node and the previous node in the list.
• Circular Linked List: The last node in the list points back to the first node, forming a loop.

Basic Operations

The most common operations on a linked list are:

• Insertion: Adding a new node to the list.
• Deletion: Removing a node from the list.
• Traversal: Accessing each element in the list sequentially.
• Search: Finding an element in the list.

C++ Example

Here's an example of a simple singly linked list implementation in C++:

#include <iostream>

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

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

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

int main() {
    Node* head = nullptr;

    insert(head, 1);
    insert(head, 2);
    insert(head, 3);

    printList(head);

    return 0;
}

In this example, the Node class represents a single node in the list. The insert() function adds a new node with the given data to the front of the list. The printList() function prints the elements of the list.

See Also

• Arrays
• Heaps
• Hash Tables