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,
- Data
- 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)
(https://www.coderlogs.com/post/6257cf1a752339739aa908d4/-Memory-Usage-in-Linked-List-)
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 asnode
.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 initialized to
NULL
which is called as ahead
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 typeint
so 4-bytes for data and another member is pointernext
so 4-bytes (for 32-bit machine) fornext
hence total8-bytes
(which is called as a node) is assigned by themalloc
. And the address of the first location is stored into another pointer namednewnode
of typestruct 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 pointernewnode
and initialize the memberaddress
toNULL
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 ofnewnode
intohead
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 pointertemp
of typestruct node
.
printf("Enter the number of nodes in the list : ");
scanf("%d", &n);
- Using for loop, for
i=1
, first node is created where pointersnewnode
andhead
are linking to the first node and maketemp
to link it to the first node by copying the value ofhead
pointer into it.
- for
i=2
, malloc assigns another8-bytes
of locations whose starting address is stored into pointernewnode
. Now enter data (for ex: 10) into that node2 by accessing structure memberdata
using pointernewnode
and initialize the address part of node2 toNULL
. To create a link from node1 to node2 update theaddress
part of node1 to whichtemp
is pointing by the value ofnewnode
and maketemp
to point to node2 by copyingnewnode
totemp
.
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 another8-bytes
of locations whose starting address is stored into pointernewnode
. Now enter data (for ex: 15) into that node3 by accessing structure memberdata
using pointernewnode
and initiaize the address part of node3 toNULL
. To create a link from node2 to node3 update theaddress
part of node2 to whichtemp
is pointing by the value ofnewnode
and maketemp
to point to node3 by copyingnewnode
totemp
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 copyinghead
totemp
.
temp=head;
- Print the data part of node1 to which
temp
is pointing and then update thetemp
value with address part of node1 which makestemp
to point node2. Now print the data part of node2 and again update thetemp
value with address part of node2 which makestemp
to point node-3. Likewise keep on printing the data and updatingtemp
value untiltemp
is not equal toNULL
.
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;
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");
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);
}
I own a website www.coderlogs.com where in I write similar blogs so do visit this website for more such blog posts.
Top comments (1)
Thanks for your articles. It's great!. I don't understand that why do you use temp pointer in this case ?