What is Linked List in C
Linked list
Similar to an array, a linked list is a linear data structure that stores a chain of nodes with two fields of memory in each node. Where first memory is used for data, and second memory is used to store the addresses of subsequent components.
Therefore, each struct node in a linked list has two memory fields: a data field and an address field.
The address field contains the address of the next element. The address section is also known as Pointer to the Next Node.
After array, we use linked list as our second priority for the data structure.
The linked list's size is not defined, and data items may be inserted along the list.
Linked list Vs. Array:
The fundamental distinction between an array and a linked list is the amount of contiguous memory that an array takes up as opposed to the dispersed memory of a linked list.
Random access is made feasible by the array's contiguous memory. Any element can be directly accessed using its index. The below table explains more about the differences between Linked List and Array:
| S.no. | Linked List | Array |
| 1 | A linked list is a linear data structure which consist of a series of nodes. We can store data and also address of next node in every node. | An array is also a linear type of data structure which consists of similar data types elements in contiguous memory location. |
| 2 | Memory is dispersed in Linked List. In physical memory, the nodes are organized in random order. | An array takes up contiguous memory. This indicates that the data is kept in physical memory's subsequent memory locations. |
| 3 | Access to the sequence is supported by linked lists. It implies that we must read nodes progressively starting at the beginning of the list to access any random node. The reason for this is that physical memory nodes are scattered at random. Nodes, unlike arrays, do not have a known address. | Random access is possible with arrays. The array's elements can be accessed directly by their indexes. Since the data is kept in a single, continuous memory space, we can quickly access any element of an array using its index. |
| 4 | Each node in a linked list has two memory fields: one for data and one for the address of the next node. This means that Linked List takes up more memory than an array. | The array merely stores the data at each index. Nothing additional is kept in storage. |
| 5 | It's easy to insert or delete. Nodes aren't moved around or rearranged as a result of it. | Rearranging all of the array's members may be necessary to insert or remove data from it. |
| 6 | Memory is efficiently used by Linked List. Only when data is added does it take up memory. | Even without any data being inserted, an array uses memory. |
| 7 | The memory for the linked list is allocated at runtime. | An array may have memory allocated for it both during compilation and during runtime. |
| 8 | Linked List is dynamic. Its size is freely expandable and contractible. | The array that has allocated memory at compile time is a static array that has been declared, and its size is fixed. |
| 9 | On a linked list, we cannot conduct a binary search. | On the array, we can conduct a binary search. |
Types of linked lists:
- Singly Linked List
- Doubly Linked List
Singly Linked List:
The most prevalent kind of linked list among all other linked lists is the singly linked list. We can only navigate in one direction in a singly linked list. It is an assortment of sets of elements in an orderly fashion. In single linked list, each node in a linked list has two memory fields: one for data and one for the address of the next node.
A singly linked list can be created in essentially two different methods, which are:
- We can add any future new entries to the linked list's end.
- The alternative is to insert items into particular locations in the list in ascending order of sorted items.
Each item in a linked list must have both the data and an address of the next item in the list. The items contained in a linked list typically consist of structures.
Syntax:
struct node
{
Int data;
struct node * after;
};In the above syntax, struct nodes are used to hold data of the integer type and struct nodes *, which hold the address of the next node.
In singly linked lists, there is a single node connected just next to another node, so in the above code, we have used a struct to describe a node. The node will contain its integer value and the pointer of the same node type to the next.
Example: Let's create a singly linked list of node size 4 where the node order would be 4->1->2->3.
C code:
#include<stdio.h>
#include<stdlib.h>
struct node{
int data;
struct node* after_node;
};
int main(){
struct node* one=NULL;
struct node* two=NULL;
struct node* three=NULL;
struct node* four=NULL;
one=(struct node*)malloc(sizeof(struct node));
two=(struct node*)malloc(sizeof(struct node));
three=(struct node*)malloc(sizeof(struct node));
four=(struct node*)malloc(sizeof(struct node));
one->data=4;
one->after_node=two;
two->data=1;
two->after_node=three;
three->data=2;
three->after_node=four;
four->data=3;
four->after_node=NULL;
struct node* temp = one;
while(temp!=NULL){
printf("%d ",temp->data);
temp=temp->after_node;
}
}
Program Output:
Explanation:
In the above c code, we created four variables of type struct and initialized them as NULL. Now in the first node, we put the value, and we initialize its next node as a pointer that points to the next node. Now in the second node, we put the value again, and the next pointer would point to the third node. Now the third node will contain a value, and it will point to the fourth node as its next pointer since the fourth pointer is the last pointer so that we will put the value into it, and its next pointer will point to NULL.
Time complexity:
Search: O(N)
insertion: O(1)
deletion: O(1)
Doubly Linked list:
A data portion and two pointers—one for the previous node and the other for the next node—are contained in each node in a doubly-linked list.
In a doubly linked list, there are two possible directions of movement: forward and backward.
Traversal is possible in both directions using a doubly linked list. The next node's and the previous node's addresses are available. The choice to turn right or left will be available at any node.
Data, a pointer to the subsequent node, and a pointer to the preceding node make up a node.
With NULL as the previous node refers that the head node is empty. See the below image:
Example: We will be having an example of a doubly linked list:
NULL <-> 4 <-> 6 <-> 9 <-> 5 <-> 3 <-> NULL
C code:
#include<stdio.h>
#include<stdlib.h>
struct node{
int data;
struct node* next;
struct node* prev;
};
void addFront( struct node** headRef,int data){
struct node* newNode = (struct node*)malloc(sizeof(struct node));
newNode->data = data;
newNode->next=(*headRef);
newNode->prev=NULL;
if((*headRef)!=NULL)
(*headRef)->prev=newNode;
(*headRef) = newNode;
}
void addAfter(struct node* currNode,int data){
if(currNode==NULL){
printf("can't be null node");
return;
}
struct node* newNode = (struct node*)malloc(sizeof(struct node));
newNode->data = data;
newNode->next=currNode->next;
currNode->next=newNode;
newNode->prev=currNode;
if(newNode->next!=NULL){
newNode->next->prev=newNode;
}
}
void addEnd(struct node** headRef,int data){
struct node* newNode = (struct node*)malloc(sizeof(struct node));
newNode->data = data;
newNode->next=NULL;
struct node* temp=(*headRef);
if((*headRef)==NULL){
newNode->prev=NULL;
(*headRef)=newNode;
return;
}
while(temp->next!=NULL){
temp=temp->next;
}
temp->next=newNode;
newNode->prev=temp;
}
int main(){
struct node* head=NULL;
addFront(&head,9);
addFront(&head,6);
addFront(&head,4);
addEnd(&head,3);
addAfter(head->next->next,5);
struct node* temp = head;
struct node* last=NULL;
printf(" left to right traversal is :");
while(temp!=NULL){
last=temp;
printf("%d ",temp->data);
temp=temp->next;
}
printf(" \nright to left traversal is :");
while(last!=NULL){
printf("%d ",last->data);
last=last->prev;
}
}Program output:
Explanation:
In the above code, we have a node variable of type struct where three members are present. One is the node's data, and the other two are pointers to the node before it and the node after it.
We implemented three functions that add the new node at different positions.
One function will add the new node at the start of the list. We will be given the pointer to the head and the integer data. We will create the node with data value and add it to the previous head node, making this new node the head node.
The second function will add the node after any given node. We will receive an integer value and a reference to the target node. We will create the node with its values, and then we will traverse it to the target node. The target node's next node will be the new node, and vice versa. We will add the new node as the target node's next node. Also, we will set the previous nodes also.
The final node will be added to the linked list in the third function. The list will be repeated several times, and when it is finished, the previous node of the new node will serve as the last node, with the next node of the last node added as a new node.