Linked List is the data structure that stores data elements  in a sequence. Each data element is called a Node.Each node further contains data field/fields and a pointer(Refer :Pointers ) to next node(Fig 1).

The  left part  of node has a data item and the right part of node has the address of succeeding node.The  address of elements may be  sequential or may be notSTART  node has the address of first node . The last node of linked list has  NULL  in the right part. NULL value indicates the  end of list. Chain of nodes is formed using this method.

`If Â START = NULL ,it means that linked list does not contain any node and the list is empty.`

In Fig 2,START  stores the address of first node(40).Nodes are at address 40,45,50,65  respectively.10,20,30,40 are the data elements in the left part .45 in first node points to second node at 45 address,50 in second points third node which is at location 50,65 in fourth part points to last node which further does not points to anything.i.e. the last node of list.

Implementation of Linked List

Linked lists are implemented in C through structures(Refer :Structures).

Syntax

```struct node//Fig 3
{
int data_item;
};```
• node is the name of structure.
• data_item of int type refers to element of linked list.
• *link  is a pointer variable of structure .

Traversing a Singly Linked List

Program 1

```#include<stdio.h>
struct node
{
int item;
};

int main()
{
struct node *start,*list;
int i;
start = (struct node *)malloc(sizeof(struct node)); //Refer Program 2 for working of this statement.
list = start;
for(i=0;i<5;i++)
{
list->item = i;
list->link = (struct node *)malloc(sizeof(struct node));
}
while(start != NULL)
{
printf("%d\n",start->item);
}
return 0;
}```

Illustration of Program

• node is the name of structure.
• item of int type refers to element of linked list.
• *link is a pointer variable of structure used to point to next address.
• *start and *list refers to pointer variables of structure.
• The function malloc is used to allocate a certain amount of memory during the execution of a program. The malloc function will request a block of memory from the heap. If the request is granted, the operating system will reserve the requested amount of memory.
• malloc allocates sizeof(struct node) bytes, and returns a void pointer to it, which we cast to  struct node *.
• start points to the first node of linked list.

Working of Program 1

Program 2

```#include<stdio.h>
struct node
{
int item;
};

int main()
{
struct node *start,*list;

start = (sizeof(struct node));
printf("%d\n",start);
start =malloc(sizeof(struct node));
printf("%d\n",start);
start =  (struct node*) printf("%d",start);
printf("%d\n",start);
return 0;
};```

Practical applications of linked list

• A list of images that need to be burned to a CD in a medical imaging application
• A list of users of a website that need to be emailed some notification
• A list of objects in a 3D game that need to be rendered to the screen
Rate this post