Single Linked List Implementation in C

In this comprehensive guide, we’ll dive into the world of singly linked lists, exploring how they function, their memory structure, and how to implement one in C. If you’re getting into data structures or gearing up for coding interviews, this is definitely a concept you need to grasp.

What Is a Singly Linked List?

A singly linked list is a linear data structure where each element, known as a node, has two main components:

-        Data — the value that the node holds.

-        Next Pointer — a reference to the next node in the sequence.

Unlike arrays, the elements in a linked list aren’t stored in consecutive memory locations. Instead, each node dynamically points to the next one, creating a chain-like structure.

Visual Representation:

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

Why Choose a Singly Linked List?

There are several compelling reasons why singly linked lists can be a better choice than arrays in certain situations:

-        Dynamic Memory Allocation: Memory for nodes is allocated as needed during runtime.

-        Efficient Insertions and Deletions: This structure shines when you need to frequently add or remove elements, especially in the middle of the list.

-        No Memory Waste: Unlike arrays, you don’t have to specify the size ahead of time, which helps avoid wasting memory.

Basic Terminology

Before we jump into how to implement a singly linked list, let’s clarify some important terms:

-        Node: This is an individual element within the linked list.

-        Head: The first node in the list.

-        Next: A pointer in each node that directs you to the following node.

-        NULL: This indicates the end of the linked list.

-        Traversal: The process of visiting each node starting from the head until you reach NULL.

Structure of a Node in C

struct Node {

int data;

struct Node* next;

};

Operations on Singly Linked List

Let’s dive into the essential operations you can perform on a singly linked list using C. Here’s what we’ll cover:

1.  Adding a new node at the start

2.  Adding a new node at the end

3.  Removing a node

4.  Traversing or displaying the list

5.  Finding a specific element

These operations are fundamental for working with singly linked lists, so let’s get started!

C Program: Create and Traverse a Linked List

#include <stdio.h>

#include <stdlib.h>

// Define structure

struct Node {

int data;

struct Node* next;

};

// Function to create a new node

struct Node* createNode(int value) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

    newNode->data = value;

    newNode->next = NULL;

return newNode;

}

// Function to display the list

void displayList(struct Node* head) {

struct Node* temp = head;

    printf("Linked List: ");

while (temp != NULL) {

        printf("%d -> ", temp->data);

     temp = temp->next;

}

    printf("NULL\n");

}

// Driver Code

int main() {

struct Node* head = NULL;

struct Node* first = createNode(10);

struct Node* second = createNode(20);

struct Node* third = createNode(30);

// Linking nodes

head = first;

    first->next = second;

    second->next = third;

    displayList(head);

return 0;

}

Output:

Linked List: 10 -> 20 -> 30 -> NULL

Adding a new node at the start

void insertAtBeginning(struct Node** head, int value) {

struct Node* newNode = createNode(value);

    newNode->next = *head;

*head = newNode;

}

Adding a new node at the end

void insertAtEnd(struct Node** head, int value) {

struct Node* newNode = createNode(value);

if (*head == NULL) {

     *head = newNode;

     return;

}

struct Node* temp = *head;

while (temp->next != NULL) {

     temp = temp->next;

}

    temp->next = newNode;

}

Removing a node

void deleteNode(struct Node** head, int key) {

struct Node *temp = *head, *prev = NULL;

if (temp != NULL && temp->data == key) {

     *head = temp->next;

        free(temp);

     return;

}

while (temp != NULL && temp->data != key) {

     prev = temp;

     temp = temp->next;

}

if (temp == NULL) return;

    prev->next = temp->next;

free(temp);

}

Finding a specific element

int search(struct Node* head, int key) {

struct Node* current = head;

while (current != NULL) {

     if (current->data == key)

            return 1;

     current = current->next;

}

return 0;

}

Complete Example Program

#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));

    newNode->data = value;

    newNode->next = NULL;

return newNode;

}

void insertAtEnd(struct Node** head, int value) {

struct Node* newNode = createNode(value);

if (*head == NULL) {

     *head = newNode;

     return;

}

struct Node* temp = *head;

while (temp->next != NULL)

     temp = temp->next;

    temp->next = newNode;

}

void displayList(struct Node* head) {

while (head != NULL) {

        printf("%d -> ", head->data);

     head = head->next;

}

    printf("NULL\n");

}

void deleteNode(struct Node** head, int key) {

struct Node *temp = *head, *prev = NULL;

if (temp != NULL && temp->data == key) {

     *head = temp->next;

        free(temp);

     return;

}

while (temp != NULL && temp->data != key) {

     prev = temp;

     temp = temp->next;

}

if (temp == NULL) return;

    prev->next = temp->next;

free(temp);

}

int search(struct Node* head, int key) {

while (head != NULL) {

     if (head->data == key)

            return 1;

     head = head->next;

}

return 0;

}

int main() {

struct Node* head = NULL;

    insertAtEnd(&head, 10);

    insertAtEnd(&head, 20);

    insertAtEnd(&head, 30);

    displayList(head);

    deleteNode(&head, 20);

    displayList(head);

if (search(head, 30))

        printf("Element found!\n");

else

        printf("Element not found!\n");

return 0;

}

Output:

10 -> 20 -> 30 -> NULL

10 -> 30 -> NULL

Element found!

Advantages of Singly Linked List

-        Dynamic Size: It can grow or shrink as needed while the program runs.

-        Efficient Memory Use: Unlike arrays, it doesn’t waste memory.

-        Easy Insertions/Deletions: Particularly simple when adding or removing items in the middle or at the start.

Disadvantages of Singly Linked List

-        No Backward Traversal: You can’t move backward since each node only has one pointer.

-        Extra Memory: Each node needs some memory for its pointer.

-        Sequential Access: To access a node, you have to start from the head, which takes O(n) time.

Applications of Singly Linked List

-        Implementing Stacks and Queues

-        Symbol Tables in Compilers

-        Dynamic Memory Allocation

-        Adjacency List Representation in Graphs

Related Topics to Explore

-        Doubly Linked List

-        Circular Linked List

-        Stack using Linked List

-        Queue using Linked List

-        Polynomial Representation using Linked Lists

Learn C Programming and Data Structures Professionally

If you’re eager to master C programming and delve deeper into data structures like linked lists, stacks, and trees, check out the Data Structures Course in Noida offered by Uncodemy.

This course is ideal for both beginners and intermediate learners who want to build a solid programming foundation and ace technical interviews.

Conclusion

Singly linked lists are a crucial topic in computer science, especially when working with dynamic data. Knowing how to create, manipulate, and traverse them is essential for anyone looking to pursue a career in software development or preparing for coding interviews.

In this article, we covered the fundamentals of singly linked lists in C, how to perform various operations, and how to implement them effectively. We also discussed their advantages, disadvantages, and real-world applications.

Interested in learning more concepts with hands-on training? Join the Data Structures Course in Noida at Uncodemy and boost your programming skills with guidance from expert mentors and live projects.

Frequently Asked Questions (FAQs)

Q1. What is a singly linked list?

A singly linked list is a type of linear data structure where each node connects to the next one in the sequence, and the last node points to NULL.

Q2. How is a singly linked list different from a doubly linked list?

In a singly linked list, each node has just one pointer that leads to the next node. On the other hand, a doubly linked list has two pointers for each node—one pointing to the next node and another pointing to the previous one.

Q3. What is the time complexity of insertion in a linked list?

- Insertion at the beginning: O(1)

- Insertion at the end: O(n) (unless you keep a tail pointer)

Q4. Why use linked lists over arrays?

Linked lists provide dynamic memory allocation and allow for efficient insertions and deletions. In contrast, arrays have a fixed size and can be less efficient when you need to make frequent changes.

Q5. Can we reverse a singly linked list?

Absolutely! A singly linked list can be reversed using either iterative or recursive methods by adjusting the next pointers of each node.