A singly linked list is a data structure that consists of nodes where each node points to the next node, forming a linear collection of elements.

Code 📺

Node Structure

Let’s define the structure of Node which can hold integer data and address to the next node.

C
// Structure (Design) of Node
struct Node
{
    int data;
    Node *next;
};
C++

Other than the two components, we will also define a constructor which accepts one argument of integer type. It assigns the passed value as data and NULL to the next node’s address block.

// Structure (Design) of Node
struct Node
{
    int data;
    Node *next;
    Node(int d)
    {
        this->data = d;
        next = NULL;
    }
};

Create New Linked List

To create a new linked list, you need to call this function which accepts one parameter of integer type. It returns the address of newly created linked list after creating the root node and assigning the passed integer value.

C
// To create a linked list
struct Node* createLinkedList(int d)
{
    struct Node *node = (struct Node*)malloc(sizeof(struct Node));
    node->data = d;
    node->next = NULL;
    return node;
}
C++
// To create a linked list
Node* createLinkedList(int d)
{
    return new Node(d);
}

Insert Node 😎

Insert New Node at First

  1. Check if root is NULL. If yes then it means linked list not created, therefore use return statement.
  2. Create new node, allocate memory and assign data to it. The next part will point to the address of root node (to make sure that the newly created node is now connected to the linked list).
  3. Next, we simply point the root node to the address of new node.
C
void insertAtFirst(struct Node **root, int d)
{
    if (*root == NULL)
        return;
    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = d;
    newNode->next = *root;
    *root = newNode;
}
C++
// Insert new node at first
void insertAtFirst(Node **root, int d)
{
    if (*root == NULL)
        return;
    Node *newNode = new Node(d);
    newNode->next = *root;
    *root = newNode;
}

Insert New Node at Last

  1. Check if root is NULL. If yes then it means linked list not created, therefore use return statement.
  2. Create a copy of root node and iterate through until the next is NULL.
  3. Create new node, allocate memory and assign data to it. The next part will point to NULL, since this new node is supposed to be added at the end of the linked list.
  4. Next, the temporary node’s next part will store or point to the address of newly created node to make sure the newly created node is connected to the linked list.
C
// Insert new node at last
void insertAtLast(struct Node **root, int d)
{
    if (*root == NULL)
        return;
    
    struct Node *t = *root;

    while(t->next != NULL)
        t = t->next;
    
    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = d;
    newNode->next = NULL;

    t->next = newNode;
}
C++
// Insert new node at last
void insertAtLast(Node **root, int d)
{
    if (*root == NULL)
        return;
    Node *tmp = *root;
    while (tmp->next != NULL)
        tmp = tmp->next;
    Node *newNode = new Node(d);
    tmp->next = newNode;
}

Insert Before Specific Node

  1. Check if root is NULL. If yes then it means linked list not created, therefore use return statement.
  2. Create a temporary node that points to root node and a new node by allocating memory.
  3. Iterate through the linked list nodes using temporary node created in previous step. Check if there exists a node whose data matches the key value, if yes then add new node before that matching node and use return statement to break the loop.
  4. If there is no such node that matches the key value then display the possible reasons for failed operation.
C
// Insert new node before a specific node
void insertBefore(struct Node **root, int key, int d)
{
    if (*root == NULL)
        return;
    struct Node *newNode = (struct Node*) malloc(sizeof(struct Node)), *tmp = *root;
    while (tmp->next != NULL)
    {
        if (tmp->next->data == key)
        {
            newNode->data = d;
            newNode->next = tmp->next;
            tmp->next = newNode;
            return;
        }
        tmp = tmp->next;
    }
    printf("\nOperation Failed - Insert before specific node.\nOne of the possible reasons could be:\n");
    printf("1. Minimum 2 nodes required.\n");
    printf("2. This operation cannot be performed to add new node at the beginning.\n");
    printf("3. Specified node (%d) does not exist.", key);
}
C++
// Insert new node before a specific node
void insertBefore(Node **root, int key, int d)
{
    if (*root == NULL)
        return;
    Node *newNode = new Node(d), *tmp = *root;
    while (tmp->next != NULL)
    {
        if (tmp->next->data == key)
        {
            newNode->next = tmp->next;
            tmp->next = newNode;
            return;
        }
        tmp = tmp->next;
    }
    cout << "\nOperation Failed - Insert before specific node.\nOne of the possible reasons could be:" << endl;
    cout << "1. Minimum 2 nodes required." << endl;
    cout << "2. This operation cannot be performed to add new node at the beginning." << endl;
    cout << "3. Specified node (" << key << ") does not exist." << endl;
}

Insert After Specific Node

  1. Check if root is NULL. If yes then it means linked list not created, therefore use return statement.
  2. Create a temporary node that points to root node and a new node by allocating memory.
  3. Iterate through the linked list nodes using temporary node created in previous step. Check if there exists a node whose data matches the key value, if yes then add new node after that matching node and use return statement to break the loop.
  4. If there is no such node that matches the key value then display the possible reasons for failed operation.
C
// Insert new node after a specific node
void insertAfter(struct Node **root, int key, int d)
{
    if (*root == NULL)
        return;
    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node)), *tmp = *root;
    while (tmp->next != NULL)
    {
        if (tmp->data == key)
        {
            newNode->data = d;
            newNode->next = tmp->next;
            tmp->next = newNode;
            return;
        }
        tmp = tmp->next;
    }
    printf("\nOperation Failed - Insert after specific node.\nOne of the possible reasons could be:\n");
    printf("1. Minimum 2 nodes required.\n");
    printf("2. This operation cannot be performed to add new node at the end.\n");
    printf("3. Specified node (%d) does not exist.", key);
}
C++
// Insert new node after a specific node
void insertAfter(Node **root, int key, int d)
{
    if (*root == NULL)
        return;
    Node *newNode = new Node(d), *tmp = *root;
    while (tmp->next != NULL)
    {
        if (tmp->data == key)
        {
            newNode->next = tmp->next;
            tmp->next = newNode;
            return;
        }
        tmp = tmp->next;
    }
    cout << "\nOperation Failed - Insert after specific node.\nOne of the possible reasons could be:\n" << endl;
    cout << "1. Minimum 2 nodes required." << endl;
    cout << "2. This operation cannot be performed to add new node at the end." << endl;
    cout << "3. Specified node (" << key << ") does not exist." << endl;
}

Delete Node 😮

Delete First Node

  1. Check if root is NULL. If yes then it means linked list not created, therefore use return statement.
  2. Create a temporary node that points to root node.
  3. Point the root node to the next node or in simple words assign the next of null to the root node.
  4. Free up the memory occupied by the temporary node.
C
void deleteFirst(struct Node **root) 
{
    if(*root == NULL)
        return;
    
    struct Node *t = *root;
    *root = (*root)->next;

    free(t);
}
C++
// Delete first node
void deleteFirst(Node **root)
{
    if (*root == NULL)
        return;
    Node *tmp = *root;
    *root = (*root)->next;
    delete tmp;
}

Delete Last Node

  1. Check if root is NULL. If yes then it means linked list not created, therefore use return statement.
  2. Create a temporary node that points to root node. Iterate through the nodes till second last node. In simple words, if there are N nodes then the temporary node must point to the second last (N-1) node.
  3. Free up the memory occupied by the last node.
  4. Assign NULL to the next of second last node.
C
void deleteLast(struct Node **root) 
{
    if(*root == NULL)
        return;
    
    struct Node *t = *root;
    while(t->next->next != NULL)
        t = t->next;

    free(t->next->next);
    t->next = NULL;
}
C++
// Delete last node
void deleteLast(Node **root)
{
    if (*root == NULL)
        return;
    Node *tmp = *root;
    while (tmp->next->next != NULL)
        tmp = tmp->next;
    delete tmp->next->next;
    tmp->next = NULL;
}

Delete Specific Node

  1. Check if root is NULL. If yes then it means linked list not created, therefore use return statement.
  2. Create two temporary nodes: tmp and tmp2, respectively. Iterate through the linked list and also check if key node exists or not.
  3. If yes then point tmp2 to the next of tmp and point next of tmp to tmp->next->next.
  4. Free up the memory occupied by tmp2 node and use return statement.
  5. If no then display the appropriate reasons for failed operation.
C
// Delete specific (middle) node
void deleteMiddle(struct Node **root, int key)
{
    if (*root == NULL)
        return;
    struct Node *tmp = *root, *tmp2;
    while (tmp->next->next != NULL)
    {
        if (tmp->next->data == key)
        {
            tmp2 = tmp->next;
            tmp->next = tmp->next->next;
            free(tmp2);
            return;
        }
        tmp = tmp->next;
    }
    printf("\n\nOperation Failed - Delete specific node from middle.\nOne of the possible reasons could be::\n");
    printf("1. Minimum 3 nodes required.\n");
    printf("2. Specified key node (%d) does not exist.\n", key);
}
C++
// Delete specific (middle) node
void deleteMiddle(Node **root, int key)
{
    if (*root == NULL)
        return;
    Node *tmp = *root, *tmp2;
    while (tmp->next->next != NULL)
    {
        if (tmp->next->data == key)
        {
            tmp2 = tmp->next;
            tmp->next = tmp->next->next;
            free(tmp2);
            return;
        }
        tmp = tmp->next;
    }
    cout << "\n\nOperation Failed - Delete specific middle node.\nOne of the possible reasons could be:" << endl;
    cout << "1. Minimum 3 nodes required." << endl;
    cout << "2. Specified middle node (" << key << ") does not exist." << endl;
}

Traversal 🤠

Display Linked List Nodes

C
void traverse(struct Node *root)
{
    struct Node *t = root;

    while(t != NULL) {
        printf("%d -> ", t->data);
        t = t->next;
    }
    printf("NULL");
}
C++
// Display all nodes of linked list.
void traverse(Node *root)
{
    if (root == NULL)
        return;

    Node *tmp = root;
    while (tmp != NULL)
    {
        cout << tmp->data << " -> ";
        tmp = tmp->next;
    }
    cout << "NULL" << endl;
}

Display in Reverse Order using Recursion

C
void reverse(struct Node *root)
{
    if(root == NULL)
    {
        printf("NULL");
        return;
    }

    reverse(root->next);
    printf(" -> %d", root->data);
}
C++
// Display Linked List in Reverse Order using Recursion
void reverse(Node *root)
{
    if(root == NULL)
    {
        cout << "NULL";
        return;
    }

    reverse(root->next);
    cout << " -> " << root->data;
}

Categorized in:

C ProgramC++ ProgramDSA

Tagged in:

, , , , , ,