Operation of Link List

Linked lists are a crucial data structure in computer science, where each element (node) contains a data value and a reference to the next node in the sequence.

Unlike arrays, linked lists provide dynamic memory allocation, allowing efficient insertions and deletions.

In this post, we will explore the core operations of linked lists, such as creation, insertion, deletion, traversal, searching, concatenation, and display, with detailed explanations and C code examples to help you master this fundamental concept in programming.

1. Creation: Defines a linked list structure.
2. Insertion: Adds nodes at specific positions (e.g., beginning).
3. Deletion: Removes nodes based on conditions (e.g., value).
4. Traversal: Iterates over nodes to perform actions.
5. Search: Finds a node based on a key.
6. Concatenation: Joins two linked lists together.
7. Display: Outputs the data of all nodes.

1. Creation of a Linked List

Creating a linked list means we are constructing a list of nodes that are connected to one another. Each node contains two parts:

• data: Stores the value of the node.
• next: Points to the next node in the list (or NULL if it's the last node).

Each node is created dynamically using memory allocation (malloc), which gives us flexibility since the size of the linked list can change dynamically during execution.

Step-by-step breakdown:

1. Define the Node structure with two parts: data and next.
2. Dynamically allocate memory for each node using malloc.
3. Set the next pointer to link the nodes.

Example:

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

// Allocating memory for the first node
struct Node* head = NULL;
head = (struct Node*)malloc(sizeof(struct Node));
head->data = 10; // Assigning value
head->next = NULL; // Last node points to NULL

We use dynamic memory allocation because we don’t know the number of nodes beforehand. This allows the linked list to grow or shrink dynamically based on the needs of the program.

2. Insertion in Linked List (at Beginning)

Insertion at the beginning means adding a new node as the first node of the list. When a new node is added:

• The next pointer of the new node is updated to point to the current head.
• The head pointer is updated to point to the new node.

Step-by-step breakdown:

1. Create a new node dynamically.
2. Set the new node's next pointer to the current head (which can be NULL if the list is empty).
3. Update the head to point to the new node.

Example:

struct Node* insertAtBeginning(struct Node* head, int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = head; // Point to the current first node
    return newNode; // New node becomes the head
}

Imagine a queue of people standing in line. If a new person arrives and they want to stand at the front of the line, they simply point to the previous first person in line, and the front of the queue is updated.

3. Deletion from Linked List (by Value)

Deleting a node involves:

• Searching for the node that contains the value.
• If the node is found, it’s removed from the list.
• The previous node’s next pointer is updated to skip the deleted node.

If the node to be deleted is the head, we simply move the head to the next node.

Step-by-step breakdown:

1. Traverse the list to find the node with the specified value.
2. If the node is found, adjust the next pointer of the previous node.
3. If it's the first node, update the head.
4. Free the memory of the deleted node.

Example:

struct Node* deleteByValue(struct Node* head, int value) {
    struct Node *temp = head, *prev = NULL;

    if (temp != NULL && temp->data == value) {
        head = temp->next; // Move head to the next node
        free(temp); // Free the memory of the node
        return head;
    }

    while (temp != NULL && temp->data != value) {
        prev = temp;
        temp = temp->next;
    }

    if (temp == NULL) return head; // If value is not found

    prev->next = temp->next; // Link the previous node to the next node
    free(temp); // Free the memory of the deleted node
    return head;
}

4. Traversing the Linked List

Traversing means moving through each node of the linked list and performing an operation on it, such as printing the data or performing calculations.

We start from the head, move to the next node using the next pointer, and continue this until we reach the end (when next is NULL).

Step-by-step breakdown:

1. Start from the head node.
2. Visit each node by following the next pointer.
3. Perform operations (such as printing) on each node.
4. Stop when next is NULL.

Example:

void traverse(struct Node* head) {
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next; // Move to the next node
    }
    printf("NULL\n"); // Indicating the end of the list
}

Think of a train with multiple carriages. To inspect each carriage, you start at the first one and move from one carriage to the next, until the last one.

5. Searching in Linked List

Searching means finding a node that contains a particular value. We traverse the list and check each node’s data.

Step-by-step breakdown:

1. Start at the head node.
2. Compare the data of the current node with the search key.
3. If the data matches, return success.
4. If the data doesn't match, move to the next node and repeat.
5. Stop when the node is found or when the end of the list is reached (NULL).

Example:

int search(struct Node* head, int key) {
    struct Node* temp = head;
    while (temp != NULL) {
        if (temp->data == key)
            return 1; // Return true if the value is found
        temp = temp->next;
    }
    return 0; // Return false if the value is not found
}

Imagine looking for a specific book in a row of bookshelves. You check each book one by one until you find the one you're looking for.

6. Concatenation of Two Linked Lists

Concatenation means joining two linked lists into one. To do this:

• Traverse the first list until the last node.
• Set the last node’s next pointer to point to the head of the second list.

Step-by-step breakdown:

1. Traverse the first list until you find the last node (where next is NULL).
2. Link the last node’s next pointer to the head of the second list.

Example:

struct Node* concatenate(struct Node* head1, struct Node* head2) {
    if (head1 == NULL) return head2; // If the first list is empty, return the second list
    struct Node* temp = head1;
    while (temp->next != NULL) { // Traverse the first list
        temp = temp->next;
    }
    temp->next = head2; // Connect the last node of the first list to the second list
    return head1; // Return the concatenated list
}

7. Displaying the Linked List

Displaying means printing all the elements of the linked list in a readable format.

We start from the head and print each node’s data, moving from one node to the next.

Step-by-step breakdown:

1. Start from the head node.
2. Print the data of each node.
3. Move to the next node and repeat.
4. Stop when next is NULL.

Example:

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

Mastering linked list operations is key to understanding more complex data structures. With the examples and explanations provided, you're now equipped to implement and optimize linked lists in your own projects.