Home »
Data Structure
Singly Linked List implementation in C
In this program, we are implementing a single linked list in Data Structure using C program.
This is a data structure program using C, here we are implementing a singly linked list using C language program.
In this program,
- head and tail are two pointers, where head points to first node of linked list and tail points the las node of the linked list.
- A Node contains two parts
- item - item contains data item (it may be a number, string or any object like structure).
- next - next contains address of the next node.
- Last Node of the linked list contains NULL in the next part.
Singly Linked list program in C
#include <stdio.h>
#include <stdlib.h>
//Self referential structure to create node.
typedef struct tmp
{
int item;
struct tmp * next;
}Node;
//structure for create linked list.
typedef struct
{
Node * head;
Node * tail;
}List;
//Initialize List
void initList(List * lp)
{
lp->head = NULL;
lp->tail = NULL;
}
//Create node and return reference of it.
Node * createNode(int item)
{
Node * nNode;
nNode = (Node *) malloc(sizeof(Node));
nNode->item = item;
nNode->next = NULL;
return nNode;
}
//Add new item at the end of list.
void addAtTail(List * lp,int item)
{
Node * node;
node = createNode(item);
//if list is empty.
if(lp->head == NULL)
{
lp->head = node;
lp->tail = node;
}
else
{
lp->tail->next = node;
lp->tail = lp->tail->next;
}
}
//Delete item from the end of list.
int delFromTail(List * lp)
{
Node * temp;
int i = 0;
int item = 0;
if(lp->tail == NULL)
{
printf("\nList is Empty ...");
return -1;
}
else
{
temp = lp->head;
while(temp->next != lp->tail)
{ temp = temp->next;}
item = lp->tail->item;
lp->tail = temp;
lp->tail->next = NULL;
}
return item;
}
//Add new item at begning of the list.
void addAtHead(List * lp,int item)
{
Node * node;
node = createNode(item);
//if list is empty.
if(lp->head == NULL)
{
lp->head = node;
lp->tail = node;
}
else
{
node->next = lp->head ;
lp->head = node ;
}
}
//Delete item from Start of list.
int delFromHead(List * lp)
{
int item = 0;
if(lp->head == NULL)
{
printf("\nList is Empty ...");
return -1;
}
else
{
item = lp->head->item;
lp->head = lp->head->next;
}
return item;
}
//To print list from start to end of the list.
void printList(List *lp)
{
Node * node;
if(lp->head == NULL)
{
printf("\nEmpty List");
return;
}
node = lp->head;
printf("\nList: \n\n\t");
while(node != NULL)
{
printf("| %05d |",node->item);
node = node->next;
if(node !=NULL)
printf("--->");
}
printf("\n\n");
}
//Main function to execute program.
int main()
{
List *lp;
int item = 0;
lp = (List *) malloc(sizeof(List));
initList(lp);
addAtTail(lp,10);
addAtTail(lp,20);
addAtHead(lp,30);
addAtHead(lp,40);
printList(lp);
item = delFromTail(lp);
if(item >= 0)
printf("\nDeleted item is : %d",item);
printList(lp);
item = delFromHead(lp);
if(item >= 0)
printf("\nDeleted item is : %d",item);
printList(lp);
return 0;
}
Output
List:
| 00040 |--->| 00030 |--->| 00010 |--->| 00020 |
Deleted item is : 20
List:
| 00040 |--->| 00030 |--->| 00010 |
Deleted item is : 40
List:
| 00030 |--->| 00010 |