Open in app

Sign in

Write

Sign in

C-LINKED LIST (Singly Linked List)

Dev Frank
8 min readJun 21, 2024

--

A linked list is a data structure used to store a collection of elements. Unlike arrays, linked lists do not store elements in contiguous memory locations. Instead, each element, called a node, contains the data and a reference (or pointer) to the next node in the sequence. This structure allows for efficient insertions and deletions since you only need to update the pointers.

We can assume linked list as a series of connected boxes, where each box holds some information and a pointer (a reference) to the next box.

Types of Linked Lists

  • Singly Linked List: Each node points to the next node. The last node points to NULL.
  • Doubly Linked List: Each node points to both the next and the previous node.
  • Circular Linked List: The last node points back to the first node, forming a circle.

By default, when we refer to a linked list in C, we typically mean a singly linked list. This is because the singly linked list is the simplest and most fundamental form of a linked list.

To define and work with a linked list in C, you need to understand the syntax and structure of the various components involved, such as the node definition, list operations, and function definitions.

Syntax

// Define the node structure
struct Node {
    int data;          // Data part
    struct Node* next; // Pointer to the next node
};

Node Definition

  1. Node: A node is the basic building block of a linked list. Each node contains data and a pointer to the next node.
  • Data: This is the value or information the node holds.
  • Pointer: This is like an address that tells you where the next node in the list is.

2. Head: This a pointer or reference to the first node in the list. It serves as the starting point for any operations that involve traversing or manipulating the list. Without the head, it would be impossible to access the rest of the nodes in the list.

// Define the node structure
struct Node {
    int data;          // Data part
    struct Node* next; // Pointer to the next node
};

Basic Operations on a Singly Linked List

1. Creation of a Node:

  • You need a function to create and initialize a new node.
  • Allocating memory for a new node.
  • Setting the node’s data and initializing the next pointer to NULL.
#include <stdio.h>
#include <stdlib.h>

// Function to create a new node
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (!newNode) {
        printf("Memory allocation error\n");
        return NULL;
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

2. Inserting Nodes :

Nodes can be inserted at the beginning, at the end, or at a specific position.

— insertAtBeginning function creates a new node, sets its next pointer to the current head, and updates the head to the new node.

void insertAtBeginning(struct Node** headRef, int data) {
    struct Node* newNode = createNode(data);
    newNode->next = *headRef;
    *headRef = newNode;
}

— insertAtEnd function creates a new node, sets its next pointer to the current head, and updates the head to the new node.

void insertAtEnd(struct Node** headRef, int data) {
    struct Node* newNode = createNode(data);
    if (*headRef == NULL) {
        *headRef = newNode;
    } else {
        struct Node* temp = *headRef;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
}

3. Deletion :

Deletion can occur at various positions in the list: at the beginning, at the end, or at a specific position.

Delete from the Beginning

To delete the first node, you simply move the head pointer to the next node.

void deleteFromBeginning(struct Node** headRef) {
    if (*headRef == NULL) {
        printf("List is empty\n");
        return;
    }
    struct Node* temp = *headRef;
    *headRef = (*headRef)->next;
    free(temp);
}

Delete from the End

To delete the last node, you need to traverse the list to find the second last node and update its next pointer to NULL.

void deleteFromEnd(struct Node** headRef) {
    if (*headRef == NULL) {
        printf("List is empty\n");
        return;
    }
    if ((*headRef)->next == NULL) {
        free(*headRef);
        *headRef = NULL;
        return;
    }
    struct Node* temp = *headRef;
    while (temp->next->next != NULL) {
        temp = temp->next;
    }
    free(temp->next);
    temp->next = NULL;
}

Delete from a Specific Position

To delete a node at a specific position, you need to find the node just before that position and update its next pointer

void deleteFromPosition(struct Node** headRef, int position) {
    if (*headRef == NULL) {
        printf("List is empty\n");
        return;
    }
    struct Node* temp = *headRef;

    if (position == 0) {
        *headRef = temp->next;
        free(temp);
        return;
    }

    for (int i = 0; temp != NULL && i < position - 1; i++) {
        temp = temp->next;
    }

    if (temp == NULL || temp->next == NULL) {
        printf("Position does not exist\n");
        return;
    }

    struct Node* next = temp->next->next;
    free(temp->next);
    temp->next = next;
}

Here is a full example that demonstrates the linked list operations including deletion:

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

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

struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (!newNode) {
        printf("Memory allocation error\n");
        return NULL;
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

void insertAtBeginning(struct Node** headRef, int data) {
    struct Node* newNode = createNode(data);
    newNode->next = *headRef;
    *headRef = newNode;
}

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

void deleteFromBeginning(struct Node** headRef) {
    if (*headRef == NULL) {
        printf("List is empty\n");
        return;
    }
    struct Node* temp = *headRef;
    *headRef = (*headRef)->next;
    free(temp);
}

void deleteFromEnd(struct Node** headRef) {
    if (*headRef == NULL) {
        printf("List is empty\n");
        return;
    }
    if ((*headRef)->next == NULL) {
        free(*headRef);
        *headRef = NULL;
        return;
    }
    struct Node* temp = *headRef;
    while (temp->next->next != NULL) {
        temp = temp->next;
    }
    free(temp->next);
    temp->next = NULL;
}

void deleteFromPosition(struct Node** headRef, int position) {
    if (*headRef == NULL) {
        printf("List is empty\n");
        return;
    }
    struct Node* temp = *headRef;

    if (position == 0) {
        *headRef = temp->next;
        free(temp);
        return;
    }

    for (int i = 0; temp != NULL && i < position - 1; i++) {
        temp = temp->next;
    }

    if (temp == NULL || temp->next == NULL) {
        printf("Position does not exist\n");
        return;
    }

    struct Node* next = temp->next->next;
    free(temp->next);
    temp->next = next;
}

int main() {
    struct Node* head = NULL;

    // Insert nodes
    insertAtBeginning(&head, 10);
    insertAtBeginning(&head, 20);
    insertAtBeginning(&head, 30);

    // Print list
    printf("Initial list: ");
    printList(head);

    // Delete from beginning
    deleteFromBeginning(&head);
    printf("After deleting from beginning: ");
    printList(head);

    // Delete from end
    deleteFromEnd(&head);
    printf("After deleting from end: ");
    printList(head);

    // Delete from a specific position
    insertAtBeginning(&head, 40);
    insertAtBeginning(&head, 50);
    deleteFromPosition(&head, 1);
    printf("After deleting from position 1: ");
    printList(head);

    return 0;
}

Explanation of Deletion Functions

  1. Delete from Beginning:
  • Checks if the list is empty. If it is, it prints a message.
  • If not, it updates the head to point to the next node and frees the memory of the original first node.

2. Delete from End:

  • Checks if the list is empty. If it is, it prints a message.
  • If the list has only one node, it frees it and sets the head to NULL.
  • Otherwise, it traverses the list to find the second last node, updates its next pointer to NULL, and frees the last node.

3. Delete from a Specific Position:

  • Checks if the list is empty. If it is, it prints a message.
  • If the position is 0, it updates the head to point to the second node and frees the first node.
  • Otherwise, it traverses the list to find the node just before the position, updates its next pointer to skip the node to be deleted, and frees the node.

4. Traversing the List :

Starting from the head, you follow the pointers from one node to the next until you reach the end. This means it will go through each node in the list, starting from the head and following the pointers until you reach the end of the list.

Here’s how you can traverse a singly linked list and print its elements:

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

// Define the structure of a node
struct Node {
    int data;
    struct Node* next;
};

// Function to create a new node
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (!newNode) {
        printf("Memory allocation error\n");
        return NULL;
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Function to insert a node at the beginning
void insertAtBeginning(struct Node** headRef, int data) {
    struct Node* newNode = createNode(data);
    newNode->next = *headRef;
    *headRef = newNode;
}

// Function to traverse the list and print the elements
void traverseList(struct Node* head) {
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

int main() {
    struct Node* head = NULL;

    // Insert nodes at the beginning
    insertAtBeginning(&head, 10);
    insertAtBeginning(&head, 20);
    insertAtBeginning(&head, 30);

    // Traverse and print the list
    printf("Traversing the list: ");
    traverseList(head);

    return 0;
}

Explanation

Node Structure:

struct Node {
    int data;
    struct Node* next;
};
  • Defines a node with an integer data and a pointer to the next node.

Create Node Function:

struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (!newNode) {
        printf("Memory allocation error\n");
        return NULL;
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}
  • Allocates memory for a new node, initializes its data and next pointer.

Insert Node at Beginning:

void insertAtBeginning(struct Node** headRef, int data) {
    struct Node* newNode = createNode(data);
    newNode->next = *headRef;
    *headRef = newNode;
}
  • Creates a new node and inserts it at the beginning of the list by updating the head pointer.

Traverse List Function:

void traverseList(struct Node* head) {
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}
  • Starts at the head node.
  • Iterates through the list using a temporary pointer (temp).
  • Prints the data of each node followed by an arrow (->).
  • Stops when temp becomes NULL, indicating the end of the list.

Main Function:

Basically the main function demonstrates creating an empty linked list, inserting nodes at the beginning, and printing the list.

int main() {
    struct Node* head = NULL;

    // Insert nodes at the beginning
    insertAtBeginning(&head, 10);
    insertAtBeginning(&head, 20);
    insertAtBeginning(&head, 30);

    // Traverse and print the list
    printf("Traversing the list: ");
    traverseList(head);

    return 0;
}
  • Initializes the head to NULL (empty list).
  • Inserts three nodes at the beginning.
  • Calls the traverseList function to print the list.

📖Read More on Linked list …

That’s a wrap on our introduction to linked lists! We’ve explored how these flexible data structures work, learned how to create and manipulate them, and even saw how to add and remove nodes. Linked lists are a fundamental concept in programming, and understanding them opens the door to more advanced data structures and algorithms.

Stay tuned for our next story, where we’ll dive into doubly linked lists. Unlike singly linked lists, these allow you to traverse in both directions, making them even more versatile and powerful. See you next time!

Computer Science
Data Structures
Linked List
C Programming
Software Engineering

--

--

Dev Frank

Written by Dev Frank

41 Followers

Thrilled to share insights with the world. Diving deep into the world of software engineering. Tech enthusiast | Web developer | Software engineering Student.

Help

Status

About

Careers

Press

Blog

Privacy

Terms

Text to speech

Teams