Linked List Data Structure

What is a Linked List?

A linked list is a linear data structure where each element, called a node, contains a data part and a reference (or link) to the next node in the sequence. Unlike arrays, linked lists do not store elements in contiguous memory locations, making them more flexible for dynamic memory allocation.

Linked lists are ideal for situations where the size of the data structure is not known in advance or where frequent insertions and deletions are required.

Real-World Analogy

Imagine a treasure hunt where each clue leads you to the next clue. Each clue is like a node in the linked list, containing the information (data) and directions to the next clue (next node).

Example

Consider a linked list that stores the following integers: 1, 2, 3, 4, and 5. The list is structured as follows:

1 -> 2 -> 3 -> 4 -> 5 -> NULL

Each number points to the next one in the sequence, and the last node points to NULL, indicating the end of the list.

Code Snippets

C++

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

Node* head = new Node();
head->data = 1;
head->next = new Node();
head->next->data = 2;
// Continue for other nodes

Java

class Node {
    int data;
    Node next;
}

Node head = new Node();
head.data = 1;
head.next = new Node();
head.next.data = 2;
// Continue for other nodes

Python

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

head = Node(1)
head.next = Node(2)
# Continue for other nodes

C

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

struct Node* head = malloc(sizeof(struct Node));
head->data = 1;
head->next = malloc(sizeof(struct Node));
head->next->data = 2;
// Continue for other nodes