Linked List in C - Sanfoundry

What is a Linked List?

A linked list is a linear data structure where elements (called nodes) are stored in memory and connected using pointers.

Each node contains:

Data – the actual value.
Pointer – a reference to the next node in the list.

[Data|Next] -> [Data|Next] -> [Data|Next] -> NULL

Why Use Linked Lists?

Dynamic size — grows and shrinks at runtime
Efficient insertion/deletion (no need to shift elements)
Useful when the number of elements is unknown or changes frequently

Types of Linked Lists in C

Singly Linked List – Points only to the next node.
Doubly Linked List – Each node points to both next and previous.
Circular Linked List – Last node points back to the first.

Structure of a Node in C

#include <stdio.h>
#include <stdlib.h>
 
struct Node {
    int data;
    struct Node* next;
};

How to Create a Node in C

To work with linked lists in C, we define a function to create new nodes:

// Function to create a new node with given value
struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        exit(1);
    }
    newNode->data = value;   // Assign data
    newNode->next = NULL;    // Initialize next pointer to NULL
    return newNode;
}

Insert Node at the Beginning of the Linked List

// Insert a new node at the beginning of the list
void insertAtBeginning(struct Node** head_ref, int value) {
    struct Node* newNode = createNode(value);
    newNode->next = *head_ref;  // Point new node to current head
    *head_ref = newNode;        // Update head to new node
}

Insert Node at the End of the Linked List

// Insert a new node at the end of the list
void insertAtEnd(struct Node** head_ref, int value) {
    struct Node* newNode = createNode(value);
    if (*head_ref == NULL) {
        *head_ref = newNode;   // If list is empty, new node is head
        return;
    }
    struct Node* temp = *head_ref;
    while (temp->next != NULL) {
        temp = temp->next;     // Traverse to the last node
    }
    temp->next = newNode;      // Link last node to new node
}

Traversing and Printing the Linked List

// Traverse the linked list and print all elements
void printList(struct Node* head) {
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");   // Indicate end of list
}

Deleting a Node by Value (Key)

// Delete the first node with the specified key (value)
void deleteNode(struct Node** head_ref, int key) {
    struct Node* temp = *head_ref;
    struct Node* prev = NULL;
 
    // If head node itself holds the key
    if (temp != NULL && temp->data == key) {
        *head_ref = temp->next;   // Change head
        free(temp);               // Free old head
        return;
    }
 
    // Search for the key in the list
    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }
 
    // If key was not found in the list
    if (temp == NULL) return;
 
    // Unlink node from linked list
    prev->next = temp->next;
    free(temp);  // Free memory
}

Sample Main Function

int main() {
    struct Node* head = NULL;   // Start with an empty list
 
    insertAtEnd(&head, 10);
    insertAtBeginning(&head, 5);
    insertAtEnd(&head, 20);
 
    printf("Linked list: ");
    printList(head);            // Expected output: 5 -> 10 -> 20 -> NULL
 
    deleteNode(&head, 10);
 
    printf("After deleting 10: ");
    printList(head);            // Expected output: 5 -> 20 -> NULL
 
    return 0;
}

Complete Example of Linked List

#include <stdio.h>
#include <stdlib.h>
 
struct Node {
    int data;
    struct Node* next;
};
 
struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
    if (!newNode) {
        printf("Memory allocation failed\n");
        exit(1);
    }
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}
 
void insertAtEnd(struct Node** head_ref, int value) {
    struct Node* newNode = createNode(value);
    if (*head_ref == NULL) {
        *head_ref = newNode;
        return;
    }
    struct Node* temp = *head_ref;
    while (temp->next != NULL) temp = temp->next;
    temp->next = newNode;
}
 
void printList(struct Node* head) {
    while (head != NULL) {
        printf("%d -> ", head->data);
        head = head->next;
    }
    printf("NULL\n");
}
 
int main() {
    struct Node* head = NULL;
 
    insertAtEnd(&head, 1);
    insertAtEnd(&head, 2);
    insertAtEnd(&head, 3);
 
    printList(head);
 
    return 0;
}

Output:

Free 30-Day Java Certification Bootcamp is Live. Join Now!

1 -> 2 -> 3 -> NULL

Explanation:

The program defines a Node structure to represent each element in a singly linked list.
The createNode() function dynamically allocates memory and initializes a node with a given value.
The insertAtEnd() function appends a new node at the end of the list, updating pointers accordingly.
If the list is empty, the new node becomes the head.
The printList() function traverses the list and prints all node values in order, ending with NULL.

Advantages of Linked Lists

Dynamic Size: Can grow or shrink in size during execution.
Efficient Insertions/Deletions: Insertions and deletions are more efficient compared to arrays.
Memory Utilization: Does not require memory reallocation or reorganization.

Disadvantages of Linked Lists

Memory Usage: Requires extra memory for pointers.
Sequential Access: Cannot access elements randomly; must traverse from the head.
Complexity: More complex to implement compared to arrays.

Sanfoundry Global Education & Learning Series – 1000 C Tutorials.

If you wish to look at all C Tutorials, go to C Tutorials.

« Prev - Where is Memory Allocated During Dynamic Memory Allocation in C Programming

» Next - Dynamic vs Static Memory Allocation in C with Linked Lists

Related Posts: