IMPLEMENTATION OF SINGLE LINKED LIST
A Linked list is a chain of structs or records called Nodes. Each node has at least two members, one of which points to the next Node in the list and the other holds the data. These are defined as Single Linked Lists because they can only point to the next Node in the list but not to the previous.
struct Node
{
int Data;
struct Node *Next;
}*Head;
|
We use above structure for a Node in our example. Variable Data holds the data in the Node while pointer of type struct Node Next holds the address to the next Node in the list. Head is a pointer of type struct Node which acts as the Head to the list.
Initially we set 'Head' as NULL which means list is empty.
Initially we set 'Head' as NULL which means list is empty.
//Set HEAD as NULL
Head=NULL;
|
Let us see Insertion Functions.. addBeg, addEnd, addAt.
// Adding a Node at the Beginning of the List
void addBeg(int num)
{
struct Node *temp;
temp=(struct Node *)malloc(sizeof(struct Node));
temp->Data = num;
if (Head == NULL)
{
//List is Empty
Head=temp;
Head->Next=NULL;
}
else
{
temp->Next=Head;
Head=temp;
}
}
|  |
We create 'temp' node and save the Data part.
If Head is NULL it means list is empty. So we set temp node as the Head of the list and set the Next as NULL. Else we set the Next in temp node as Head and reassign Head with temp.
If Head is NULL it means list is empty. So we set temp node as the Head of the list and set the Next as NULL. Else we set the Next in temp node as Head and reassign Head with temp.
//Adding a Node at the end of the list
void addEnd(int num)
{
struct Node *temp1, *temp2;
temp1=(struct Node *)malloc(sizeof(struct Node));
temp1->Data=num;
// Copying the Head location into another node.
temp2=Head;
if(Head == NULL)
{
// If List is empty we create First Node.
Head=temp1;
Head->Next=NULL;
}
else
{
// Traverse down to end of the list.
while(temp2->Next != NULL)
temp2=temp2->Next;
// Append at the end of the list.
temp1->Next=NULL;
temp2->Next=temp1;
}
}
|
// Adding a new Node at specified position
void addAt(int num, int loc)
{
int i;
struct Node *temp, *prev_ptr, *cur_ptr;
cur_ptr=Head;
if(loc > (length()+1) || loc <= 0)
{
printf("\nInsertion at given location is not possible\n ");
}
else
{
// If the location is starting of the list
if (loc == 1)
{
addBeg(num);
}
else
{
for(i=1;i<loc;i++)
{
prev_ptr=cur_ptr;
cur_ptr=cur_ptr->Next;
}
temp=(struct Node *)malloc(sizeof(struct Node));
temp->Data=num;
prev_ptr->Next=temp;
temp->Next=cur_ptr;
}
}
}
// Counting number of elements in the List
int length()
{
struct Node *cur_ptr;
int count=0;
cur_ptr=Head;
while(cur_ptr != NULL)
{
cur_ptr=cur_ptr->Next;
count++;
}
return(count);
}
|
Now we will see how to delete a node from the list depending upon the data in the Node.
// Deleting a node from List depending upon the data in the node.
int delNodeData(int num)
{
struct Node *prev_ptr, *cur_ptr;
cur_ptr=Head;
while(cur_ptr != NULL)
{
if(cur_ptr->Data == num)
{
if(cur_ptr==Head)
{
Head=cur_ptr->Next;
free(cur_ptr);
return 0;
}
else
{
prev_ptr->Next=cur_ptr->Next;
free(cur_ptr);
return 0;
}
}
else
{
prev_ptr=cur_ptr;
cur_ptr=cur_ptr->Next;
}
}
printf("\nElement %d is not found in the List", num);
return 1;
}
|
If the value to be deleted is not the head of the list.
Similarly if we want to delete a node based on its location in the list.
// Deleting a node from List depending upon the location in the list.
int delNodeLoc(int loc)
{
struct Node *prev_ptr, *cur_ptr;
int i;
cur_ptr=Head;
if(loc > (length()) || loc <= 0)
{
printf("\nDeletion of Node at given location is not possible\n ");
}
else
{
// If the location is starting of the list
if (loc == 1)
{
Head=cur_ptr->Next;
free(cur_ptr);
return 0;
}
else
{
for(i=1;i<loc;i++)
{
prev_ptr=cur_ptr;
cur_ptr=cur_ptr->Next;
}
prev_ptr->Next=cur_ptr->Next;
free(cur_ptr);
}
}
return 1;
}
|
// Deleting a node from List depending upon the location in the list.
int delNodeLoc(int loc)
{
struct Node *prev_ptr, *cur_ptr;
int i;
cur_ptr=Head;
if(loc > (length()) || loc <= 0)
{
printf("\nDeletion of Node at given location is not possible\n ");
}
else
{
// If the location is starting of the list
if (loc == 1)
{
Head=cur_ptr->Next;
free(cur_ptr);
return 0;
}
else
{
for(i=1;i<loc;i++)
{
prev_ptr=cur_ptr;
cur_ptr=cur_ptr->Next;
}
prev_ptr->Next=cur_ptr->Next;
free(cur_ptr);
}
}
return 1;
}
|
Displaying a list.
1. // Displaying list contents
2.
3. void display()
4. {
5. struct Node *cur_ptr;
6.
7. cur_ptr=Head;
8.
9. if(cur_ptr==NULL)
10. {
11. printf("\nList is Empty");
12. }
13. else
14. {
15. printf("Elements in the List: ");
16. //traverse the entire linked list
17. while(cur_ptr!=NULL)
18. {
19. printf(" -> %d ",cur_ptr->Data);
20. cur_ptr=cur_ptr->Next;
21. }
22. printf("\n");
23. }
24. }
|
Reversing a list.
|
0 comments:
Post a Comment