Introduction
A data structure is the logical or mathematical model of a particular organization of data. Thus a data structure is defined by
(i) organizing data in a specific way
(ii) defining a set of operations performed on the data that make it behave in a certain way
Data structure is a way of organizing all data items that considers not only the data items are stored but also their relationship to each other. Data structures are of two types: linear data structures and non-linear data structures. In linear data structures the elements are processed in a linear sequence, that is one by one. But in non-linear data structures elements are processed randomly. Stacks, queues and lists are examples of linear data structures whereas trees and graphs are examples of non-linear data structures. In this chapter we will study about implementation of typical data structures like lists, stacks, queues and trees.
Lists
Lists are collection of items in which each element contains data items as well as information about other elements of the list. There are two types of lists – one way lists and two-way lists. In one-way lists traversing is made in one direction only whereas in two-way lists traversing is made in either direction or both directions.
Stacks
Stack is one of the most useful linear data structure – Stack in which elements are inserted and deleted at one end called as top of the stack.
Queues
After this we will study another non-linear data structure – Queues. The concept of a ‘queue’ data structure is similar to its ordinary meaning, that is a line of people waiting to purchase something, where the first person in the line is the first person to be served. In queue, the elements are inserted at one end called rear end of the queue and deleted at other end of the queue called front end of the queue.
Trees
Trees are one of the most useful non-linear data structures. In trees we will see the implementation of binary search tree – a special type of binary tree.
Implementation of Data Structures
Now let us see implementation of these data structures in C.
Example-1 Write a program that implements a singly linked list
/* A singly linked list is a collection of nodes in which traversing is done in one direction only. In this we take a node consisting of two fields – data field and link field. The data field consists of information and link field contains the address of next node. In case of last node, the link field contains a Null. */
/* Program – lohit.c */
#include
#include
#include
struct node
{
int data;
struct node *link;
};
typedef struct node Node;
main()
{
Node *first;
int choice, item, pos;
(Node *) getnode();
InitializeList(&first);
clrscr();
printf("\nCreating a Singly Linked List.\n");
CreateList(&first);
while (1)
{
printf("\n\n\tImplementation ofa Singly Linked List.\n");
printf("\n\t\t1. Insertion as a First Node.");
printf("\n\t\t2. Insertion as a Last Node.");
printf("\n\t\t3. Insertion of a Node at any specific location.");
printf("\n\t\t4. Deletion of First Node.");
printf("\n\t\t5. Deletion of Last Node.");
printf("\n\t\t6. Deletion of any Node.");
printf("\n\t\t7. Display");
printf("\n\t\t0. Exit");
printf("\n\n\tEnter (1/2/3/4/5/6/0) - ");
scanf("%d",&choice);
switch (choice)
{
case 1:
printf("\nEnter the item of information = ");
scanf("%d",&item);
InsertFirst(&first,item);
break;
case 2:
printf("\nEnter the item of information = ");
scanf("%d",&item);
InsertLast(&first,item);
break;
case 3:
printf("\nEnter the item of information = ");
scanf("%d",&item);
printf("\nEnter the node number where you want to insert the item = ");
scanf("%d",&pos);
InsertAtAny(&first,item,pos);
break;
case 4:
DeleteFirst(&first);
break;
case 5:
DeleteLast(&first);
break;
case 6:
printf("\nEnter the node number you want to delete = ");
scanf("%d",&pos);
DeleteAny(&first,pos);
break;
case 7:
Traversing(first);
break;
case 0:
exit(0);
}
}
}
InitializeList(Node **first)
{
(*first)=NULL;
}
CreateList(Node **first)
{
Node *temp, *current;
int item;
printf("\nEnter the item of information (-9999 to terminate) = ");
scanf("%d",&item);
while (item != -9999)
{
temp = getnode();
temp->data = item;
temp->link = NULL;
if ((*first) == NULL)
(*first) = temp;
else
current->link = temp;
current = temp;
printf("Enter the item of information (-9999 to terminate) = ");
scanf("%d",&item);
}
}
Traversing(Node *first)
{
if (first == NULL)
{
printf("\nList is empty. Press any key to Continue....");
getch();
return;
}
printf("\nContents of a linked list are as….\n");
printf("\nStart -->");
while (first != NULL)
{
printf("%d-->",first->data);
first=first->link;
}
printf("End");
getch();
}
InsertFirst(Node **first, int item)
{
Node *temp;
temp=getnode();
if (temp==NULL)
{
printf("\nUnable to create a new node. Press any key to Continuee....");
getch();
return;
}
temp->data=item;
temp->link=(*first);
(*first)=temp;
}
InsertLast(Node **first, int item)
{
Node *temp, *current;
temp=getnode();
if (temp==NULL)
{
printf("\nUnable to create a new node. Press any key to Continuee....");
getch();
return;
}
temp->data=item;
temp->link=NULL;
if (*first==NULL)
(*first)=temp;
else
{
current=(*first);
while (current->link!=NULL)
current=current->link;
current->link=temp;
}
}
InsertAtAny(Node **first, int item, int pos)
{
Node *current, *previous, *temp;
int i=1;
temp=getnode();
if (temp==NULL)
{
printf("\nUnable to create a new node. Press any key to Continuee....");
getch();
return;
}
if ((*first==NULL)||(pos==1))
{
temp->data=item;
temp->link=NULL;
(*first)=temp;
return;
}
current=(*first)->link;
previous=(*first);
while (current!=NULL)
{
if ((i+1) == pos)
break;
else
{
previous=current;
current = current->link;
i++;
}
}
temp->data = item;
temp->link = current;
previous->link = temp;
}
DeleteFirst(Node **first)
{
Node *temp;
int item;
if (*first == NULL)
{
printf("\nList is empty. Press any key to Continue....");
getch();
return;
}
temp=(*first);
item = temp->data;
(*first) = (*first)->link;
freenode(temp);
printf("\nDeleted item = %d",item);
getch();
}
DeleteLast(Node **first)
{
Node *current, *previous;
int item;
if (*first == NULL)
{
printf("\nList is empty. Press any key to Continue....");
getch();
return;
}
current = (*first);
if ((*first)->link == NULL)
(*first) = (*first)->link;
else
{
while (current->link != NULL)
{
previous=current;
current=current->link;
}
previous->link=current->link;
}
item = current->data;
freenode(current);
printf("\nDeleted item = %d",item);
getch();
}
DeleteAny(Node **first, int pos)
{
Node *current, *previous;
int item, i=2;
if (*first == NULL)
{
printf("\nList is empty. Press any key to Continue....");
getch();
return;
}
if (pos == 1)
{
current = (*first);
item=current->data;
(*first) = (*first)->link;
freenode(current);
printf("\nDeleted item = %d",item);
return;
}
current = (*first)->link;
previous=(*first);
while (current)
{
if ( i == pos)
{
previous->link = current->link;
item = current->data;
freenode(current);
printf("\nDeleted item = %d",item);
getch();
return;
}
else
{
previous = current;
current = current->link;
}
i++;
}
}
getnode()
{
Node *t;
t = (Node *)malloc(sizeof(Node));
return t;
}
freenode(Node *t)
{
free(t);
}
Here is the output of this program….
Creating a Singly Linked List.
Enter the item of information (-9999 to terminate) = 11
Enter the item of information (-9999 to terminate) = 42
Enter the item of information (-9999 to terminate) = 35
Enter the item of information (-9999 to terminate) = 87
Enter the item of information (-9999 to terminate) = 45
Enter the item of information (-9999 to terminate) = -9999
Implementation ofa Singly Linked List.
1. Insertion as a First Node.
2. Insertion as a Last Node.
3. Insertion of a Node at any specific location.
4. Deletion of First Node.
5. Deletion of Last Node.
6. Deletion of any Node.
7. Display
0. Exit
Enter (1/2/3/4/5/6/0) - 3
Enter the item of information = 55
Enter the node number where you want to insert the item = 4
Implementation of a Singly Linked List.
1. Insertion as a First Node.
2. Insertion as a Last Node.
3. Insertion of a Node at any specific location.
4. Deletion of First Node.
5. Deletion of Last Node.
6. Deletion of any Node.
7. Display
0. Exit
Enter (1/2/3/4/5/6/0) - 7
Contents of a linked list are as….
Start -->11-->42-->35-->55-->87-->45-->End
Implementation of a Singly Linked List.
1. Insertion as a First Node.
2. Insertion as a Last Node.
3. Insertion of a Node at any specific location.
4. Deletion of First Node.
5. Deletion of Last Node.
6. Deletion of any Node.
7. Display
0. Exit
Enter (1/2/3/4/5/6/0) - 4
Deleted item = 11
Implementation of a Singly Linked List.
1. Insertion as a First Node.
2. Insertion as a Last Node.
3. Insertion of a Node at any specific location.
4. Deletion of First Node.
5. Deletion of Last Node.
6. Deletion of any Node.
7. Display
0. Exit
Enter (1/2/3/4/5/6/0) - 6
Enter the node number you want to delete = 5
Deleted item = 45
Implementation of a Singly Linked List.
1. Insertion as a First Node.
2. Insertion as a Last Node.
3. Insertion of a Node at any specific location.
4. Deletion of First Node.
5. Deletion of Last Node.
6. Deletion of any Node.
7. Display
0. Exit
Enter (1/2/3/4/5/6/0) - 7
Contents of a linked list are as….
Start -->42-->35-->55-->87-->End
Implementation ofa Singly Linked List.
1. Insertion as a First Node.
2. Insertion as a Last Node.
3. Insertion of a Node at any specific location.
4. Deletion of First Node.
5. Deletion of Last Node.
6. Deletion of any Node.
7. Display
0. Exit
Enter (1/2/3/4/5/6/0) – 2
Enter the item of information = 88
Implementation of a Singly Linked List.
1. Insertion as a First Node.
2. Insertion as a Last Node.
3. Insertion of a Node at any specific location.
4. Deletion of First Node.
5. Deletion of Last Node.
6. Deletion of any Node.
7. Display
0. Exit
Enter (1/2/3/4/5/6/0) - 7
Contents of a linked list are as….
Start -->42-->35-->55-->87-->88-->End
Implementation ofa Singly Linked List.
1. Insertion as a First Node.
2. Insertion as a Last Node.
3. Insertion of a Node at any specific location.
4. Deletion of First Node.
5. Deletion of Last Node.
6. Deletion of any Node.
7. Display
0. Exit
Enter (1/2/3/4/5/6/0) - 0