Implementation of Linked List in C
In a linked list, a block of memory allocated for an element is referred to as a node. Each node contains two types of information,
1. Data
2. Pointer to the next node (address of the next node).
The pointer of the last node in the linked list is always equal to NULL.
The below figure is the logical representation of the linked list.
Note : (5, 10, 15 and 20 are assumed data) and (100, 200, 300 and 400 are addresses of memory locations)
Now, let us map this logical representation of linked list into C code.
Step 1 : Creating Linked List.
For the creation of a node, first you need to declare the data and the address part of a node . These two are declared using a user-defined data type `structure`.
struct node
{
int data;
struct node *next;
};As creating a node, the name of the structure `struct` is assumed as `node`.
Type of node is `struct node`.
Type of data is assumed as integer(`int`) type.
Type of pointer `next` is the type of node as it is going to point to the immediate next node in the list.
Before a node creation, one pointer is initialised to `NULL` which is called as a `head` pointer.
After the creation of a node, this `head` pointer is made to point to the first node in the list .
After declaration of a node members, now create a node by using dynamic memory allocation function `malloc`.
newnode = (struct node *)malloc(sizeof(struct node)); The structure member `data` is of type `int` so 4-bytes for data and another member is pointer `next` so 4-bytes (for 32-bit machine) for `next` hence total `8-bytes` (which is called as a node) is assigned by the `malloc`. And the address of the first location is stored into another pointer named `newnode` of type `struct node`.
Note : Assuming address of first location of 8-byte as 100.
The pointer `newnode` now points to the first node because it contains address of first 8-bytes as shown in the fig below.
Now, insert the data (for ex: 5) into the first node by accessing the structure member `data` using the pointer `newnode` and initialise the member `address` to `NULL` as it is the first node.
printf("Enter the data%d : ", i);
scanf("%d", &newnode->data);
newnode->next = 0; 
Now link the pointer `head` to the node1 by copying the address of `newnode` into `head` pointer.
if(head == 0)
{
head = temp = newnode;
}Hence, a first node is created in the list.
If you want to create more than one node in the list then, before the creation of first node write the number of nodes `n` required (for example : n = 4 ) and declare one temporary pointer `temp` of type `struct node`.
printf("Enter the number of nodes in the list : ");
scanf("%d", &n);Using for loop, for `i=1`, first node is created where pointers `newnode` and `head` are linking to the first node and make `temp` to link it to the first node by copying the value of `head` pointer into it.
for `i=2`, malloc assigns another `8-bytes` of locations whose starting address is stored into pointer `newnode`. Now enter data (for ex: 10) into that node2 by accessing structure member `data` using pointer `newnode` and initialize the address part of node2 to `NULL` . To create a link from node1 to node2 update the `address` part of node1 to which `temp` is pointing by the value of `newnode` and make `temp` to point to node2 by copying `newnode` to `temp`.
Positions of pointers after the creation of node2 :
pointer `head` is pointing to node1.
pointer `temp` is pointing to node2.
pointer `newnode` is pointing to node2.
Note : Assuming address of second node's first location as 200.
if(head == 0)
{
head = temp = newnode;
}
else
{
temp->next = newnode;
temp = newnode;
}
for `i=3`, malloc assigns another `8-bytes` of locations whose starting address is stored into pointer `newnode`. Now enter data (for ex: 15) into that node3 by accessing structure member `data` using pointer `newnode` and initiaize the address part of node3 to `NULL`. To create a link from node2 to node3 update the `address` part of node2 to which `temp` is pointing by the value of `newnode` and make `temp` to point to node3 by copying `newnode` to `temp`
Positions of pointers after the creation of node2 :
pointer `head` is pointing to node1.
pointer `temp` is pointing to node3.
pointer `newnode` is pointing to node3.
Note : Assuming address of third node's first location as 300.
for i=4, node4 will be created and the positions of pointers :
pointer `head` is pointing to node1.
pointer `temp` is pointing to node4.
pointer `newnode` is pointing to node4.
Note : Assuming address of fourth node's first location as 400.
This way a `Linked List` of `4` nodes is created.
Step 2 : Displaying Linked List.
To display the created linked list, first make `temp` to point node1 by copying `head` to `temp`.
temp=head; Print the data part of node1 to which `temp` is pointing and then update the `temp` value with address part of node1 which makes `temp` to point node2. Now print the data part of node2 and again update the `temp` value with address part of node2 which makes `temp` to point node-3. Likewise keep on printing the data and updating `temp` value until `temp` is not equal to `NULL`.
Note: Pointer `temp` becomes `NULL` when it points the last node in the list.
while(temp!=0)
{
printf("%d ",temp->data);
temp=temp->next;
count++ // counting number of nodes in the list //
}C-code that demonstrates the creation and display of linked list
#include <stdio.h>
#include<stdlib.h>
int main()
{
struct node
{
int data;
struct node *next;
};
struct node *head = 0, *newnode, *temp;
int count=0, n;
// create linked list //
printf("Enter the number of nodes in the list : ");
scanf("%d", &n);
for(int i = 1; i<=n; i++)
{
newnode = (struct node *)malloc(sizeof(struct node));
printf("Enter the data%d : ", i);
scanf("%d", &newnode->data);
newnode->next = 0;
if(head == 0)
{
head = temp = newnode;
}
else
{
temp->next = newnode;
temp = newnode;
}
}
printf("--------------------------------\n");
// display linked list /
temp=head;
printf("Linked list : ");
while(temp!=0)
{
printf("%d ",temp->data);
temp=temp->next;
count++; //counting number of nodes in the list//
}
printf("\nCount = %d",count);
}