Extra 5% OFF Use Code: OL05
Free Shipping over ₹999

Linked Lists Types

by Mohd Azka
in Data Structure and Algorithm(DSA)
March 16, 2024

Linked List types

In C, there are different types of linked lists based on how they are structured and how nodes are linked together. The most common types include:

Singly linked list:

Each node in a singly linked list contains data and a pointer/reference to the next node in the sequence. It only allows traversal in one direction, usually from the head (start) of the list to the tail (end).

#include <stdio.h>
#include <stdlib.h>

// Define the Node struct
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// Create a new node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Print the linked list
void printList(Node* node) {
    while (node) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("null\n");
}

int main() {
    // Explicitly creating and connecting nodes
    Node* node1 = createNode(4);
    Node* node2 = createNode(5);
    Node* node3 = createNode(6);
    Node* node4 = createNode(2);

    node1->next = node2;
    node2->next = node3;
    node3->next = node4;

    printList(node1);

    // Free the memory
    free(node1);
    free(node2);
    free(node3);
    free(node4);

    return 0;
}

Output:

4 -> 5 -> 6 -> 2 -> null

Code Explanation

1. Define the Node Structure

typedef struct Node {
    int data;           // Stores the value of the node
    struct Node* next;  // Pointer to the next node
} Node;
  • Purpose: This defines what a node looks like.
  • Fields:
    • int data: Stores the value (e.g., 4, 5, etc.).
    • struct Node* next: A pointer to the next node in the list.
  • typedef: This creates an alias Node for struct Node, making it easier to use.

2. Create a New Node

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node)); // Allocate memory for the node
    if (!newNode) {
        printf("Memory allocation failed!\n");
        exit(1); // Exit the program if memory allocation fails
    }
    newNode->data = data; // Set the data of the node
    newNode->next = NULL; // Set the next pointer to NULL (no next node yet)
    return newNode; // Return the newly created node
}
  • Purpose: This function creates a new node with the given data.
  • Steps:
    1. Allocate memory for the node using malloc.
    2. Check if memory allocation was successful. If not, print an error and exit.
    3. Set the data field to the provided value.
    4. Set the next pointer to NULL (since this node is not yet connected to any other node).
    5. Return the new node.

3. Print the Linked List

void printList(Node* node) {
    while (node) { // Loop until the current node is NULL
        printf("%d -> ", node->data); // Print the data of the current node
        node = node->next; // Move to the next node
    }
    printf("null\n"); // Print "null" to indicate the end of the list
}
  • Purpose: This function prints all the nodes in the linked list.
  • Steps:
    1. Start from the given node (usually the first node in the list).
    2. Use a while loop to go through each node until you reach NULL.
    3. Print the data of the current node.
    4. Move to the next node by updating the pointer (node = node->next).
    5. After the loop ends, print null to show the end of the list.

4. Main Function

int main() {
    // Create nodes with data
    Node* node1 = createNode(4); // Node 1 with data = 4
    Node* node2 = createNode(5); // Node 2 with data = 5
    Node* node3 = createNode(6); // Node 3 with data = 6
    Node* node4 = createNode(2); // Node 4 with data = 2
 
    // Connect the nodes to form a linked list
    node1->next = node2; // Node 1 points to Node 2
    node2->next = node3; // Node 2 points to Node 3
    node3->next = node4; // Node 3 points to Node 4
 
    // Print the linked list
    printList(node1); // Start printing from Node 1
 
    // Free the memory allocated for the nodes
    free(node1);
    free(node2);
    free(node3);
    free(node4);
 
    return 0; // End of program
}
  • Purpose: The main function creates a linked list, connects the nodes, prints the list, and frees the memory.
  • Steps:
    1. Create Nodes:
      • Use the createNode function to create 4 nodes with data 4, 5, 6, and 2.
    2. Connect Nodes:
      • Use the next pointer to connect the nodes in this order:
        • node1 -> node2 -> node3 -> node4 -> null
    3. Print the Linked List:
      • Call the printList function starting from node1 to print the entire list.
    4. Free Memory:
      • Use free to release the memory allocated for each node. This prevents memory leaks.
    5. Return 0:
      • The program ends successfully.

Doubly Linked list

In a doubly linked list, each node contains data and two pointers/references: one to the next node and one to the previous node. This allows traversal in both directions: forward and backward.

#include <stdio.h>
#include <stdlib.h>

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

int main() {
    Node* node1 = (Node*) malloc(sizeof(Node));
    node1->data = 5;
    node1->next = NULL;
    node1->prev = NULL;

    Node* node2 = (Node*) malloc(sizeof(Node));
    node2->data = 7;
    node2->next = NULL;
    node2->prev = node1;
    node1->next = node2;

    Node* node3 = (Node*) malloc(sizeof(Node));
    node3->data = 3;
    node3->next = NULL;
    node3->prev = node2;
    node2->next = node3;

    Node* node4 = (Node*) malloc(sizeof(Node));
    node4->data = 2;
    node4->next = NULL;
    node4->prev = node3;
    node3->next = node4;

    Node* currentNode = node1;
    printf("Forward: ");
    while (currentNode) {
        printf("%d -> ", currentNode->data);
        currentNode = currentNode->next;
    }
    printf("NULL\n");

    currentNode = node4;
    printf("Backward: ");
    while (currentNode) {
        printf("%d -> ", currentNode->data);
        currentNode = currentNode->prev;
    }
    printf("NULL\n");

    free(node1);
    free(node2);
    free(node3);
    free(node4);

    return 0;
}

Output:

Forward: 5 -> 7 -> 3 -> 2 -> NULL
Backward: 2 -> 3 -> 7 -> 5 -> NULL

Code Explanation

1. Define the Node Structure

typedef struct Node {
    int data;           // Stores the value of the node
    struct Node* next;  // Pointer to the next node
    struct Node* prev;  // Pointer to the previous node
} Node;
  • Purpose: This defines what a node in a doubly linked list looks like.
  • Fields:
    • int data: Stores the value (e.g., 5, 7, etc.).
    • struct Node* next: Points to the next node in the list.
    • struct Node* prev: Points to the previous node in the list.
  • typedef: Creates an alias Node for struct Node, making it easier to use.

2. Main Function

int main() {
    // Create nodes
    Node* node1 = (Node*) malloc(sizeof(Node));
    node1->data = 5;
    node1->next = NULL;
    node1->prev = NULL;
 
    Node* node2 = (Node*) malloc(sizeof(Node));
    node2->data = 7;
    node2->next = NULL;
    node2->prev = node1;
    node1->next = node2;
 
    Node* node3 = (Node*) malloc(sizeof(Node));
    node3->data = 3;
    node3->next = NULL;
    node3->prev = node2;
    node2->next = node3;
 
    Node* node4 = (Node*) malloc(sizeof(Node));
    node4->data = 2;
    node4->next = NULL;
    node4->prev = node3;
    node3->next = node4;
  • Purpose: This part of the code creates and connects nodes to form a doubly linked list.
  • Steps:
    1. Create Nodes:
      • Use malloc to allocate memory for each node.
      • Set the data field for each node.
      • Initialize next and prev pointers to NULL.
    2. Connect Nodes:
      • Set the next pointer of each node to point to the next node.
      • Set the prev pointer of each node to point to the previous node.
      • For example:
        • node1->next = node2 and node2->prev = node1.
        • node2->next = node3 and node3->prev = node2.
        • node3->next = node4 and node4->prev = node3

3. Traverse and Print the List

    // Traverse forward
    Node* currentNode = node1;
    printf("Forward: ");
    while (currentNode) {
        printf("%d -> ", currentNode->data);
        currentNode = currentNode->next;
    }
    printf("NULL\n");
 
    // Traverse backward
    currentNode = node4;
    printf("Backward: ");
    while (currentNode) {
        printf("%d -> ", currentNode->data);
        currentNode = currentNode->prev;
    }
    printf("NULL\n");
  • Purpose: This part of the code traverses the doubly linked list in both forward and backward directions and prints the values.
  • Steps:
    1. Forward Traversal:
      • Start from the first node (node1).
      • Use a while loop to go through each node by following the next pointer.
      • Print the data of each node.
      • Stop when NULL is reached (end of the list).
    2. Backward Traversal:
      • Start from the last node (node4).
      • Use a while loop to go through each node by following the prev pointer.
      • Print the data of each node.
      • Stop when NULL is reached (start of the list).

4. Free Memory

    // Free the memory
    free(node1);
    free(node2);
    free(node3);
    free(node4);
 
    return 0;
}
  • Purpose: This part of the code releases the memory allocated for the nodes to avoid memory leaks.
  • Steps:
    1. Use free to release the memory for each node.
    2. Return 0 to indicate successful program execution.

Circular linked list

Circular linked lists are like singly or doubly linked lists, but the last node in the list points back to the first node (for singly linked lists) or the last node points to the first node and the first node points to the last node (for doubly linked lists). This creates a circular structure.

#include <stdio.h>
#include <stdlib.h>

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

int main() {
    Node* node1 = (Node*) malloc(sizeof(Node));
    Node* node2 = (Node*) malloc(sizeof(Node));
    Node* node3 = (Node*) malloc(sizeof(Node));
    Node* node4 = (Node*) malloc(sizeof(Node));

    node1->data = 7;
    node2->data = 5;
    node3->data = 3;
    node4->data = 2;

    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node1;  // Circular link

    Node* currentNode = node1;
    Node* startNode = node1;
    printf("%d -> ", currentNode->data);
    currentNode = currentNode->next;

    while (currentNode != startNode) {
        printf("%d -> ", currentNode->data);
        currentNode = currentNode->next;
    }

    printf("...\n");  // Indicating the list loops back

    free(node1);
    free(node2);
    free(node3);
    free(node4);

    return 0;
}

Output:

7 -> 5 -> 3 -> 2 -> ...

Code Explanation

1. Include Header Files

#include <stdio.h>
#include <stdlib.h>
  • stdio.h: Provides input/output functions like printf.
  • stdlib.h: Provides memory allocation functions like malloc and free.

2. Define the Node Structure

typedef struct Node {
    int data;
    struct Node* next;
} Node;
  • A Node structure is defined with two members:
    • data: Stores the integer value of the node.
    • next: A pointer to the next node in the list.
  • typedef is used to create an alias Node for struct Node.

3. Main Function

int main() {
    // Memory allocation for nodes
    Node* node1 = (Node*) malloc(sizeof(Node));
    Node* node2 = (Node*) malloc(sizeof(Node));
    Node* node3 = (Node*) malloc(sizeof(Node));
    Node* node4 = (Node*) malloc(sizeof(Node));
  • Dynamic Memory Allocation:
    • malloc is used to allocate memory for each node.
    • sizeof(Node) calculates the size of the Node structure.

4. Assign Data to Nodes

    node1->data = 7;
    node2->data = 5;
    node3->data = 3;
    node4->data = 2;
  • Each node is assigned an integer value:
    • node1 stores 7.
    • node2 stores 5.
    • node3 stores 3.
    • node4 stores 2.

5. Create Circular Links

    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node1;  // Circular link
  • The next pointers are set to create a circular linked list:
    • node1 points to node2.
    • node2 points to node3.
    • node3 points to node4.
    • node4 points back to node1, making the list circular.

6. Traverse the Circular Linked List

    Node* currentNode = node1;
    Node* startNode = node1;
    printf("%d -> ", currentNode->data);
    currentNode = currentNode->next;
 
    while (currentNode != startNode) {
        printf("%d -> ", currentNode->data);
        currentNode = currentNode->next;
    }
 
    printf("...\n");  // Indicating the list loops back
  • Initialization:
    • currentNode is set to node1 (the starting node).
    • startNode is also set to node1 to mark the beginning of the list.
  • Traversal:
    • The while loop continues until currentNode returns to startNode.
    • Each node’s data is printed, and currentNode moves to the next node.
  • Output:
    • The program prints: 7 -> 5 -> 3 -> 2 -> ... (indicating the list loops back to the start).

7. Free Allocated Memory

    free(node1);
    free(node2);
    free(node3);
    free(node4);
  • free is used to deallocate the memory allocated for each node.
  • This prevents memory leaks.

8. Return from Main

    return 0;
}
  • The program ends by returning 0, indicating successful execution.

    Leave a Reply

    Your email address will not be published.

    Need Help?
    OceanLabz © 2025 All rights reserved.
    Successfully added to your cart.