Hey Coders! Today, we are going to dive deeper into the concept of linked lists. We'll explore various aspects of linked lists, including their definition and purpose, how to create and traverse a linked list, adding and deleting nodes at different positions, performing operations on the list elements and managing, manipulating data stored in the nodes.

List of content:

• Defintion.
• Need of Linked List.
• Creation and Traversal.
• Performing Operations.

Let's start.....

Definition:

A linked list is a way of organizing data where each element (called a node) contains two parts: the actual data and a reference (or pointer) to the next node in the sequence. This structure allows you to easily add or remove elements without shifting the other elements around, unlike in arrays. It's like a chain where each link knows where the next one is!

Need of Linked List:

Linked lists are needed when we require a flexible and dynamic way to store and manage data. Unlike arrays, linked lists allow:

• Dynamic Memory Allocation: We can easily adjust the size of the list during runtime without needing to predefine the size.
• Efficient Insertions/Deletions: Adding or removing elements is faster and doesn't involve shifting other elements as in arrays.
• Versatility: They're useful for implementing data structures like stacks, queues, graphs, and more.
• Memory Optimization: They use only as much memory as needed for the data and its links.

Creation and Traversal:

Creation :

In C :

1. Define the Node Structure:

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

2. Allocate Memory for Nodes: Use to dynamically allocate memory for each node.

3. Link Nodes: Assign the next pointer of each node to connect them.

struct Node* head = (struct Node*)malloc(sizeof(struct Node));
head->data = 1;
head->next = NULL;

In Java :

1. Define the Node Class:

class Node {
    int data;
    Node next;
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

2. Create and Connect Nodes: Use constructors and assign next to link nodes.

Node head = new Node(1);
head.next = new Node(2);

In C++ :

1. Define the Node Structure:

struct Node {
    int data;
    Node* next;
    Node(int data) : data(data), next(nullptr) {}
};

2. Create and Connect Nodes: Use constructors and dynamic memory allocation (new).

Node* head = new Node(1);
head->next = new Node(2);

Traversal :

In C :

Start at the Head: Begin at the head node of the linked list.

Traverse Using a Loop: Use a while loop to visit each node until NULL.

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

void traverse(struct Node* head) {
    struct Node* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

In Java :

Start at the Head: Access the head of the linked list.

Traverse Using a Loop: Use a while loop to iterate through each node.

class Node {
    int data;
    Node next;
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

void traverse(Node head) {
    Node current = head;
    while (current != null) {
        System.out.print(current.data + " -> ");
        current = current.next;
    }
    System.out.println("NULL");
}

In C++ :

Start at the Head: Begin traversal from the head node.

Traverse Using a Loop: Use a while loop to move through the list.

struct Node {
    int data;
    Node* next;
    Node(int data) : data(data), next(nullptr) {}
};

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

Performing Operations:

In C :

Insertion (At the beginning):

void insertAtBeginning(struct Node** head, int newData) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = newData;
    newNode->next = *head;
    *head = newNode;
}

Deletion (A specific value):

void deleteNode(struct Node** head, int key) {
    struct Node* temp = *head, *prev = NULL;
    if (temp != NULL && temp->data == key) {
        *head = temp->next;
        free(temp);
        return;
    }
    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }
    if (temp == NULL) return;
    prev->next = temp->next;
    free(temp);
}

Search:

int search(struct Node* head, int key) {
    struct Node* current = head;
    while (current != NULL) {
        if (current->data == key) return 1;
        current = current->next;
    }
    return 0;
}

In Java :

Insertion (At the end):

void insertAtEnd(Node head, int newData) {
    Node newNode = new Node(newData);
    if (head == null) {
        head = newNode;
        return;
    }
    Node temp = head;
    while (temp.next != null) {
        temp = temp.next;
    }
    temp.next = newNode;
}

Deletion (A specific value):

void deleteNode(Node head, int key) {
    Node temp = head, prev = null;
    if (temp != null && temp.data == key) {
        head = temp.next;
        return;
    }
    while (temp != null && temp.data != key) {
        prev = temp;
        temp = temp.next;
    }
    if (temp == null) return;
    prev.next = temp.next;
}

Search:

boolean search(Node head, int key) {
    Node current = head;
    while (current != null) {
        if (current.data == key) return true;
        current = current.next;
    }
    return false;
}

In C++ :

Insertion (At the beginning):

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

Deletion (A specific value):

void deleteNode(Node** head, int key) {
    Node* temp = *head, *prev = nullptr;
    if (temp != nullptr && temp->data == key) {
        *head = 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;
}

Search:

bool search(Node* head, int key) {
    Node* current = head;
    while (current != nullptr) {
        if (current->data == key) return true;
        current = current->next;
    }
    return false;
}

linked lists do not require pre-defined sizes and allow for efficient insertion and deletion of elements without rearranging other data. Commonly used in scenarios requiring dynamic data management, linked lists serve as the foundation for other advanced data structures like stacks, queues, and graphs. They come in various forms, including singly linked lists (where nodes only point to the next node), doubly linked lists (nodes connect in both directions), and circular linked lists (nodes form a loop, with the last node pointing back to the first). This adaptability and efficiency make linked lists crucial for various applications in programming.

Let's explore doubly linked lists and circular linked lists next—stay tuned for their structures, operations, and practical benefits.

For more topics click here.

Happy Coding!