Self-Referential Structures and Linked Lists in C

A self-referential structure in C is a structure that contains a pointer to another structure of the same type. This concept is the foundation of many dynamic data structures like linked lists, trees, and graphs. In this tutorial, we will focus on how self-referential structures are used to build a linked list.

At SamagraCS Educational Technology, we make learning about self-referential structures and linked lists easy and intuitive, breaking down complex ideas into manageable steps.

What is a Self-Referential Structure?

A self-referential structure is a structure that contains a pointer to another structure of the same type. This allows the creation of data structures where each element can point to another element of the same type, forming chains of data like linked lists.

Real-Life Analogy:

Think of a linked list like a train where each carriage (node) is connected to the next one. Each carriage (structure) holds some data (passengers) and a pointer to the next carriage (the next structure). The last carriage in the train points to nothing, indicating the end of the list.

Defining a Self-Referential Structure (Linked List Node)

In a linked list, each element (or node) consists of:

Data: The value or information stored in the node.
Pointer: A pointer that points to the next node in the list.

Syntax:

struct Node {
    int data;  // Data part
    struct Node *next;  // Pointer to the next node (self-referential pointer)
};

Here:

data: This is where the node stores its value.
next: This is a pointer that points to the next node in the linked list. It’s a self-referential pointer because it points to another structure of type Node.

What is a Linked List?

A linked list is a dynamic data structure that consists of a sequence of nodes. Each node stores data and a pointer to the next node. Linked lists are commonly used because they provide efficient insertion and deletion operations compared to arrays.

There are three main types of linked lists:

Singly Linked List: Each node points to the next node.
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.

In this tutorial, we will focus on the singly linked list.

Basic Operations on a Linked List

Inserting a node: Adding a new node to the list.
Deleting a node: Removing a node from the list.
Traversing the list: Going through each node and printing its data.

Implementing a Linked List in C

Let’s walk through the implementation of a basic singly linked list in C.

Example: Creating and Traversing a Linked List

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

// Defining the structure for a linked list 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));
    newNode->data = data;
    newNode->next = NULL;  // New node points to NULL initially
    return newNode;
}

// Function to print the linked list
void printList(struct Node* head) {
    struct Node* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");  // End of the list
}

int main() {
    // Creating the first node (head)
    struct Node* head = createNode(10);

    // Creating additional nodes
    struct Node* second = createNode(20);
    struct Node* third = createNode(30);

    // Linking the nodes together
    head->next = second;
    second->next = third;

    // Printing the linked list
    printList(head);

    return 0;
}

Output:

10 -> 20 -> 30 -> NULL

Explanation of the Code:

Structure Definition:

We define the structure Node, which contains an integer data and a pointer next that points to the next node in the linked list.

createNode() Function:

This function dynamically allocates memory for a new node, assigns the data to the node, and sets the next pointer to NULL (indicating the end of the list).

Linking Nodes:

The nodes are linked together using the next pointer. For example, head->next = second; links the first node (head) to the second node.

Traversing the List:

The printList() function starts from the head node and traverses the list, printing the data of each node until it reaches the end (NULL).

Inserting a Node at the Beginning of the List

Let’s modify the program to insert a new node at the beginning of the list.

Code Example:

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

// Defining the structure for a linked list 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));
    newNode->data = data;
    newNode->next = NULL;  // New node points to NULL initially
    return newNode;
}

// Function to insert a node at the beginning of the list
struct Node* insertAtBeginning(struct Node* head, int data) {
    struct Node* newNode = createNode(data);
    newNode->next = head;  // New node points to the old head
    return newNode;  // New node becomes the new head
}

// Function to print the linked list
void printList(struct Node* head) {
    struct Node* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");  // End of the list
}

int main() {
    // Creating the first node (head)
    struct Node* head = createNode(10);

    // Inserting nodes at the beginning
    head = insertAtBeginning(head, 20);
    head = insertAtBeginning(head, 30);

    // Printing the updated linked list
    printList(head);

    return 0;
}

Output:

30 -> 20 -> 10 -> NULL

Explanation of Insertion Code:

Inserting at the Beginning:

The insertAtBeginning() function creates a new node and makes it point to the current head of the list. The new node then becomes the new head of the list.

Updating the Head:

We update the head to point to the new node after each insertion. This ensures that the new node is added at the beginning of the list.

Real-Life Example: Student Records Using Linked List

Let’s create a linked list to store a collection of student records, where each student has a name and roll number.

Code Example:

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

// Defining the structure for a student node
struct Student {
    char name[50];
    int rollNo;
    struct Student* next;
};

// Function to create a new student node
struct Student* createStudent(const char* name, int rollNo) {
    struct Student* newStudent = (struct Student*)malloc(sizeof(struct Student));
    strcpy(newStudent->name, name);
    newStudent->rollNo = rollNo;
    newStudent->next = NULL;  // New node points to NULL initially
    return newStudent;
}

// Function to print the student list
void printStudentList(struct Student* head) {
    struct Student* current = head;
    while (current != NULL) {
        printf("Name: %s, Roll No: %d\n", current->name, current->rollNo);
        current = current->next;
    }
}

int main() {
    // Creating the first student node (head)
    struct Student* head = createStudent("Pawan Jaiswal", 1);

    // Creating additional student nodes
    struct Student* second = createStudent("Pooja Jaiswal", 2);
    struct Student* third = createStudent("John Doe", 3);

    // Linking the student nodes together
    head->next = second;
    second->next = third;

    // Printing the student list
    printStudentList(head);

    return 0;
}

Output:

Name: Pawan Jaiswal, Roll No: 1
Name: Pooja Jaiswal, Roll No: 2
Name: John Doe, Roll No: 3

A self-referential structure is an essential concept in C programming

that enables the creation of dynamic data structures like linked lists. By using self-referential pointers, you can link nodes together to form chains of data and efficiently manage collections of records.

At SamagraCS Educational Technology, we believe in providing easy-to-understand tutorials with practical applications. Try implementing more linked list operations such as deletion and searching to get a deeper understanding of how self-referential structures work.

For any questions or assistance, feel free to reach out to Pawan & Pooja, or the team at SamagraCS Educational Technology. Keep learning and happy coding!