Data: The actual information or payload.

Link (Pointer): A reference to the next node in the sequence.

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

Here, the “link list” keyword is utilized to define a structure called Node, representing the basic building block of our linked list.

Singly Linked List: Nodes are connected in a unidirectional chain.

Doubly Linked List: Nodes have pointers to both the next nodes and previous nodes.

Circular Linked List: The last node points back to the first node in the circular linked list, forming a loop.

Adding a Node at the beginning of a Linked List in C++

Adding a node at the beginning of a linked list involves creating a new node, updating pointers, and ensuring the new node becomes the new head of the list.

void insertAtBeginning(int data) {
    // Create a new node
    Node* newNode = new Node{data, nullptr};

    // Update the new node's next pointer to the current head
    newNode->next = head;

    // Update the head to point to the new node
    head = newNode;
}

Deleting a Node by Value

In this function, we traverse the linked list to find the node with the specified value. Once found, we update the pointers to skip the node and then free the memory.

void deleteNodeByValue(int value) {
    Node* current = head;
    Node* previous = nullptr;

    // Traverse the list to find the node with the given value
    while (current != nullptr && current->data != value) {
        previous = current;
        current = current->next;
    }

    // If the node is found
    if (current != nullptr) {
        // Update pointers to skip the node to be deleted
        if (previous != nullptr) {
            previous->next = current->next;
        } else {
            // If the node to be deleted is the head, update the head
            head = current->next;
        }

        // Free the memory occupied by the node
        delete current;
    }
}

Deleting a Node at a Specific Position

Here, we traverse the list to the specified position and update pointers to skip the node at that position. Then, we free the memory occupied by the node.

void deleteNodeAtPosition(int position) {
    if (position < 0) {
        // Invalid position
        return;
    }

    Node* current = head;
    Node* previous = nullptr;

    // Traverse the list to the specified position
    for (int i = 0; i < position && current != nullptr; ++i) {
        previous = current;
        current = current->next;
    }

    // If the node at the specified position is found
    if (current != nullptr) {
        // Update pointers to skip the node to be deleted
        if (previous != nullptr) {
            previous->next = current->next;
        } else {
            // If the node to be deleted is the head, update the head
            head = current->next;
        }

        // Free the memory occupied by the node
        delete current;
    }
}

Insertion at the beginning of linked list

We create a new node dynamically using the new keyword, initializing it with the provided data and setting its next pointer to nullptr.

Node* newNode = new Node{data, nullptr};

Update Next Pointer of the New Node:

newNode->next = head;

The next pointer of the new node is set to point to the current head of the linked list. This step ensures that the new node is now connected to the rest of the list.

Update Head Pointer:

head = newNode;

Finally, we update the head pointer to point to the new node. This makes the new node the new starting point of the linked list.

Inserting a Node After a Given Node in a Linked List in C++

Inserting a node after a given node in a linked list involves creating a new node, adjusting pointers to connect the new node to the list, and ensuring proper linkages.

Code Example

void insertAfterNode(Node* prevNode, int data) {
    if (prevNode == nullptr) {
        // Invalid previous node
        return;
    }

    // Create a new node
    Node* newNode = new Node{data, nullptr};

    // Update pointers to insert the new node after the given node
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}

Explanation

Check for Valid Previous Node:

if (prevNode == nullptr) {

    // Invalid previous node

    return;

}

Before proceeding with the insertion, we check if the given previous node is valid. If it’s nullptr, the function returns, preventing potential issues.

Create a New Node:

Node* newNode = new Node{data, nullptr};

We create a new node dynamically using the new keyword, initializing it with the provided data and setting its next pointer to nullptr.

Update Pointers to Insert the New Node:

newNode->next = prevNode->next;

prevNode->next = newNode;

The next pointer of the new node is set to the next pointer of the previous node, effectively inserting the new node between the previous node and its original successor.

The next pointer of the previous node is then updated to point to the new node, ensuring the proper linkage in the list.

Inserting a Node at the End of a Linked List in C++

Appending a node to the end of a linked list involves creating a new node, finding the last node in the list, and updating pointers to include the new node.

Insert At the End of Linked List

Here, We will discuss the insertion of a node at the end of a linked list. For this process first of all we will traverse our temp node to the end node and then create a new node setting its data part. then we assign the next of temp to the new node and the next of new node will be Null. It will be cleared with an example.

Code Example

void insertAtEnd(int data) {
    // Create a new node
    Node* newNode = new Node{data, nullptr};

    // If the list is empty, make the new node the head
    if (head == nullptr) {
        head = newNode;
        return;
    }

    // Traverse the list to find the last node
    Node* current = head;
    while (current->next != nullptr) {
        current = current->next;
    }

    // Update pointers to insert the new node at the end
    current->next = newNode;
}

Explanation

Create a New Node:

Node* newNode = new Node{data, nullptr};

A new node is dynamically created with the provided data and a nullptr next pointer.

Check if the List is Empty:

if (head == nullptr) {

    head = newNode;

    return;

}

If the list is empty (i.e., head is nullptr), the new node becomes the head of the list.

Traverse the List to Find the Last Node:

Node* current = head;

while (current->next != nullptr) {

    current = current->next;

}

The list is traversed until the last node is reached. The last node is identified by having a nullptr next pointer.

Update Pointers to Insert the New Node at the End:

current->next = newNode;

The next pointer of the last node is updated to point to the new node, making the new node the new tail of the list