Implementation of Linked List in C

#c #linkedlist #array

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 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 initialized 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 initialize 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;
  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.