Linked List in C Language With Examples

Linked lists are linear data structures used to store and organise data in memory. It is an important concept of data structures and helps to utilise memory efficiently by dynamically allocating nodes when needed. C language linked list is a collection of nodes, where each node contains a data element and a reference (called pointer) to the next node in the sequence.

This Story also Contains

1. The Anatomy of a Linked List Node in C
2. Exploring Two Popular Types of Linked Lists in C
3. Implementing a Singly Linked List in C: A Step-by-Step Guide
4. Conclusion

Unlike arrays, which are less flexible and take more time for insertion and deletion operations; linked list programs in C are fast and offer flexibility in size and memory utilisation. If you are interested in gaining further knowledge about this field, we suggest you check Online C Certification Courses.

The basic building block of a linked list in C is a node, and a node contains two fields: a data field to store the actual information and a reference or pointer field to link it to the next node in the sequence. The last node in the list usually points to a null value, indicating the end of the list.

The Anatomy of a Linked List Node in C

It is important to understand the basic structure of a linked list node before diving deep into its implementation. The linked list in C node consists of two primary components: Data Field and Pointer (Reference).

Data Field

The data field of a linked list node holds the actual information that the node is intended to store. This can be any data type, depending on the requirements of the specific linked list.

For example, if the linked list is meant to store integers, the data field would be of type int. Similarly, the data field would be of type char for a linked list of strings.

Pointer (Reference)

The pointer field in the node structure is important for maintaining the linkage between nodes in the linked list. This pointer, often named 'next' or 'link', points to the memory location of the next node in the sequence. It is the pointer that allows the creation of a chain of nodes where each node knows the location of the next one.

Syntax to Demonstrate Data Field and Pointer in C Linked List

struct Node {

// Data field where value needs to be stored

int data;

// next is the pointer to the next node

struct Node* next;

};

Note: This linkage of linked lists is what gives the C program its dynamic nature, as nodes can be easily added or removed by updating these pointers.

Also read:

• Understanding the Algorithms in C Language, Types, and Examples
• Understanding Shortest Job First Scheduling in C Programming
• A Step-By-Step Guide on How to Implement Selection Sort in C

Exploring Two Popular Types of Linked Lists in C

There are many types of linked lists that includes singly, doubly, circular, doubly circular, and header linked lists. But, here, we will discuss in detail only two popular linked lists- singly linked list and doubly linked list.

Singly Linked List

The singly linked list is the most simple form of a linked list. Each node of a linked list contains data and a pointer to the next node that forms a unidirectional sequence. The last node point of a linked list is NULL which marks the end of the list. The following example shows the singly linked list code in C:

// Syntax of a singly linked list node

struct Node {

int data;

struct Node* next;

};

Doubly Linked List

A doubly linked list in C is a type of linked list where each node not only points to the next node but also points to the previous node. This bidirectional connection allows for easier traversal both forward and backward through the list. This feature is particularly useful for operations like reverse traversal or efficient insertion and deletion at both ends of the list.

// Example of a doubly linked list node

struct Node {

int data;

struct Node* next;

struct Node* prev; // Pointer to the previous node

};

Also read:

• How to Run C Program: A Comprehensive Guide
• What Are Storage Classes in C? Its Types, Advantages and Disadvantages

Implementing a Singly Linked List in C: A Step-by-Step Guide

Implementing a singly linked list in C is a foundational skill for any computer programmer who aims to master dynamic data structures. A singly linked list is a versatile and memory-efficient data structure. It is important to understand its implementation, as it provides insights into fundamental programming concepts such as pointers and memory management.

Below, we have covered fundamental operations such as creating a node, inserting a node at the beginning, and traversing the singly linked list in C.

Creating a Node

To create a new node, we need to first define a function that allocates memory for the node and initialises its data and next pointer.

Code:

struct Node* createNode(int value) {

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

newNode->data = value;

newNode->next = NULL;

return newNode;

}

Inserting a Node at the Beginning

To insert a node at the beginning of the list, first, we create a new node and update the next pointer to point to the current head of the list.

Code:

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

struct Node* newNode = createNode(value);

newNode->next = head;

return newNode;

}

Traversing the Linked List

Traversing a linked list means moving through each node in the list, one by one, starting from the first node (head) and continuing until the last node (NULL). Linked list in C, where nodes are connected through pointers; traversing allows programmers to explore and interact with the elements sequentially.

Unlike arrays, linked lists do not provide direct access to elements based on indices. A systematic traversal from the beginning to the end or vice versa is important to access the data elements in the linked list in C.

Traversing is fundamental for performing operations like printing all elements in the list, searching for a specific value, counting nodes, or performing any operation that requires accessing every node sequentially.

Code:

// The head is the starting point of the linked list.
void traverseList(struct Node* head) {

// Declare a pointer 'current' and initialise it with the head of the linked list.
struct Node* current = head;

while (current != NULL)
// Move the 'current' pointer to the next node in the linked list.

// This step is important for iterating through the entire list.
{

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

current = current->next;

}

printf("NULL\n");

}

// Print "NULL" to indicate the end of the linked list after the while loop.

Output

If we define a structure named `Node` in this C program and add a `main()` function with some values, the output will be:

Related: Popular Programming Courses From Top Providers

• Udemy C Courses & Certifications
• Coursera C Courses & Certifications
• Swayam C Courses & Certifications
• Vskills C Courses & Certifications
• Edx C Courses & Certifications
• NIIT C Courses & Certifications

Conclusion

A linked list offers a dynamic and efficient way to manage data. Whether it is a singly linked list for one-directional traversal or a doubly linked list for bidirectional traversal, the principle remains the same as the above-provided C linked list example.