LinkedList refers to a linear data structure wherein elements are not saved at adjacent memory locations, but the nodes are connected. Being of the most significant data structures in C programming, let’s explore all about linked lists in C, including the various types of linked lists, their operations and how to create a linked list!
A linked list in C is a data structure comprising nodes, where all the nodes are connected using an address. Each node holds two fields, i.e., the address field and the data field. The data field holds the node’s actual value, and the address field holds the next node’s address.
The ability to easily insert and delete elements makes sure the LinkedList can store a huge amount of data. A flexible memory allocation, dynamic size and sequential access are precisely the reasons why it is the second most used data structure in C.
Arrays can store linear data of identical types. However, they have certain limitations. Firstly, the arrays’ size is fixed, so you should know the maximum limit for the number of elements.
Secondly, it is challenging to insert new elements or delete existing elements in an array. The reason is it is imperative to create room for new elements, and for that, the existing elements must be shifted. On the other hand, in the linked list in C, if you have the head node, you can traverse to any node using it and insert a new node at the desired place.
Here are the details of different types of linked list in C:
i. Simple Linked List: Simple Linked List allows you to traverse the linked list in one direction only. It is also known as a singly linked list in C.
ii. Doubly Linked List: In the doubly linked list in C, you can traverse or move the linked list in forward and back directions.
iii. Circular Linked List: In a circular linked list, the last node has the link to the head node of the linked list in its next pointer.
iv. Doubly Circular Linked List: Also known as a circular two-way linked list, it is a complex type of linked list. It holds the pointer to the previous and the next node in the sequence.
v. Header Linked List: It includes a header node at the start of the list.
In order to understand linked lists better, let’s explore their various implementations.
Linked Lists are used to employ widely used data structures like queues and stacks.
They help you to implement hash tables. Every bucket of the hash table can work as a linked list.
They are used for the representation of the adjacency list of graphs.
You can store values of primitive types or objects in the singly linked list program in C.
Linked lists support dynamic size allocation that helps them to efficiently insert and delete elements at any place. On the other hand, arrays support fixed-size allocation that needs costly memory reallocation and copying for deletions and insertions.
In linked lists, the insertion at the beginning represents a constant time operation and accepts O(1) time. On the other hand, in arrays, the insertion of an element at the beginning accepts O(n) time (where n is the number of elements in that array).
While liked lists bring a bunch of advantages, they also have several drawbacks. These include:
Linked Lists don’t allow random access. You need to access the elements sequentially from the first node. Hence, you can’t efficiently perform a binary search with linked lists.
They need additional memory space for a pointer with every element of the list.
It takes much time to change and traverse the pointers.
The elements are not contiguous, so there is no locality of reference.
Unlike array by index, linked lists don’t allow direct access to an element.
The singly linked lists don’t support reverse traversing.
Searching, sorting, and appending an element to a linked list needs O(n) time (where n is the number of elements). These processes are costly too.
Let’s go through the below example program to understand how to create a linked list in C.
#include <stdio.h>
#include <stdlib.h>
// Defines the structure for each node
struct Node {
int data;
struct Node* next;
};
int main() {
// The following section creates the nodes
struct Node* n1 = (struct Node*)malloc(sizeof(struct Node));
struct Node* n2 = (struct Node*)malloc(sizeof(struct Node));
struct Node* n3 = (struct Node*)malloc(sizeof(struct Node));
// This code section assigns values to the nodes
n1->data = 1;
n2->data = 2;
n3->data = 3;
// This code section links the nodes
n1->next = n2;
n2->next = n3;
n3->next = NULL;
// The following code prints the linked list
struct Node* current = n1;
while (current != NULL) {
printf ("%d ", current->data);
current = current->next;
}
// The following section frees up the memory occupied by each node
free(n1);
free(n2);
free(n3);
return 0;
} |
Output:
1 2 3 |
In the above program, we define the Node structure to show all the included nodes of the linked list. We create three nodes. The malloc function is used to allocate memory to each node. Subsequently, we assign values to the data field of each node. The nodes are then linked by assigning the corresponding next pointers. We then traverse the linked list from the first node and print the data values of every node. The last step uses the free function that frees up the memory assigned for each node.
The basic LinkedList functions and operations are display(), create(), insert_begin(), insert_end(), insert_pos(), delete_begin(), delete_end(), and delete_pos(). Let’s look at the details of a few of them.
create()
It is used to create a temp node to scan the value. Subsequently, you need to check whether the LinkedList is empty or not. If it is empty, the temp node will behave as the head node. If it’s not empty, you need to use another node to traverse the boundary of LinkedList and add the temp node there.
display()
This function uses a while loop to display the whole LinkedList. You must first check whether the head node points to NULL or not. If it points to NULL, it means that LinkedList is empty. If it’s not empty, you need to assign the head node to a temp node and then use that temp node to traverse across the LinkedList and print them.
insert_begin()
To use this function, you need to make a temp node to scan the value and then check whether LinkedList is empty or not. If it’s empty, the new node would be considered a head node. If it’s not empty, you must create the temp node pointing toward the existing head node. Subsequently, the head node points towards the newly prepared node.
insert_end()
After creating a temp node to scan the value check, you must check whether LinkedList is empty or not. If it’s empty, the new node will be inserted into LinkedList. If it’s not empty, you can create a new node, for example, nd. Using this new node, you will traverse until the end of LinkedList. Finally, the temp node is inserted at the end of LinkedList.
insert_pos()
Firstly, create a temp node and check whether the LinkedList is empty or not. If it’s empty, the control returns. But if it’s not empty, the user needs to input the node position. The control returns if the input is higher than the length of LinkedList.
A singly linked list in C refers to a collection of node-like structures. Each of them is divided into two portions. They are:
Node: For storing data (strings, integers, or other type of data)
Pointer: For storing the next node’s address (it connects one node to another)
To construct a singly linked list in C, you need to use the struct keyword that lets you create user-defined data types. It can store various types of data in the nodes available in the singly linked list.
Here’s an example of a singly linked list created using integer data and struct ‘Node’.
// An example of creating a singly linked list node in C
struct Node {
int data;
struct Node* next;
}; |
A linked list in C is a data structure comprising nodes. Each node stores a data element and a reference/pointer to the subsequent node in the list. The traversal of a linked list means going through each node of the list and undertaking certain operations on it. The following program demonstrates how to traverse a linked list in C:
#include <stdio.h>
#include <stdlib.h>
// Defines a structure for a node
struct Node
{
int inputdata;
struct Node* next;
};
// Declares a function to traverse a linked list
void traverseLinkedList(struct Node* upper)
{
struct Node* this = upper;
while (this != NULL)
{
printf("%d ", this->inputdata);
this = this->next;
}
}
int main()
{
// The following code creates a sample linked list with three nodes
struct Node* upper= NULL;
struct Node* second = NULL;
struct Node* third = NULL;
// Allocates memory for each node
upper= (struct Node*)malloc(sizeof(struct Node));
second = (struct Node*)malloc(sizeof(struct Node));
third = (struct Node*)malloc(sizeof(struct Node));
// Assigns data values and sets next pointers
upper->inputdata = 1;
upper->next = second;
second->inputdata = 2;
second->next = third;
third->inputdata = 3;
third->next = NULL;
// Traverses the linked list
traverseLinkedList(upper);
return 0;
} |
Output:
1 2 3 |
In the above program, we define a structure named Node. It depicts a node of the linked list. It stores an integer data element (inputdata) and a pointer to the subsequent node (next).
The traverseLinkedList function accepts the upper node of the linked list as its parameter. Also, it initializes a ‘this’ pointer to the upper node and implements a while loop to traverse the linked list. In the while loop, the function prints the data value of every node as well as increments the ‘this’ pointer to the next node.
The main function has a sample linked list consisting of three nodes: upper, second, and third. The malloc function assigns memory to each node. Also, the nodes are assigned the data values, and we have set the next pointers to link the nodes. Subsequently, we call the traverseLinkedList function by passing the head node to traverse. Finally, the program prints the data values of all the defined nodes in the linked list.
LinkedList is one of the widely used data structures because it can efficiently insert and delete elements. You can insert a new element at any position without creating room for it in advance. This concept is useful to efficiently implement data structures like queues and stacks.
Going through the above tutorial acquaints you with the usefulness of linked lists for implementing data structures, hash tables, graphs, etc., in C. In addition, you can check out upGrad’s Executive Post Graduate Programme in Software Development by IIIT-B to facilitate your career advancement. The program is compiled to impart various key aspects of software development ranging from computer science fundamentals to building interactive web UI.
The course delivers superior-quality content by industry leaders and faculty in the form of cases, projects, and videos. Completing this course help you to develop your career in the growing field of STEM!
1. What are the different approaches to constructing a linked list in C?
Listed below are the various approaches to building a linked list in C. (i) Naive Method for Creating LinkedList (ii) Generic Method for Creating LinkedList (iii) Single Line Approach for Creating LinkedList (iv) Standard Solution for Creating LinkedList (v) Return Head From Push Function (vi) Making Head Pointer Global
2. What is the difference between stack and linked list in C?
Stack and linked list are both linear data structures. The stack implements the LIFO(Last in, First out) principle. It suggests that insertion and deletion can occur only at one end. But in a linked list, insertion and deletion can occur from any position.
3. What are the steps to implement a linked list using an array in C?
You can follow the below steps to implement a linked list using an array in C. (i) Initialize the array with some data. (ii) Write the struct node. (iii) Iterate on the array. (iv) Create a new node with the data provided. (v) Insert the newly created node into the linked list. (vi) Print the linked list.
Leave a Reply
Your email address will not be published. Required fields are marked *