♠ Posted by Unknown in C'Language,Data Structure at 11:14
Linked List Operations
A linked list is
defined as a collection of nodes. Each node has two parts.
1. Information
2. Pointer to next
node
Information part
may consists of one or more than one fields. In other words a linked list
consists of series of structures, which are not necessarily contiguous. Each
structure contains one or more than one contiguous information fields and a
pointer to a structure containing its successor. The last node of the list
contains NULL (‘\0’) in the pointer field. The pointer contains the address of
the location where next information is stored.
There are following
algorithms for the linked list.
1. Linked list creation algorithm
Step 1: [Initially list empty]
Start = NULL
Node = Create a Node
Step 3: [Assign value to information
part of a node]
Info[Node] =
Data
Step 4: [Assign null to the address
part for signaling end of the list]
Next[Node] = Start
Step 5: [Assign address of first
node to start variable]
Start = Node
Step 6: [Return the created node]
Return [Start]
2. Algorithm to traverse nodes in a linked list
Step 1: [Initialize
pointer variable current_node]
Current_node = First
Step 2: [Perform
the traversing operational]
Repeat while
Current_node [Not] NULL
Process Info
[Current_node]
Step 3: [Move
pointer to next node]
Current_node = Next
[Current_node]
Step 4: Exit
3. Algorithm to insert a node at the beginning of a list
Step 1: [check for
free space]
If New1 = NULL output
“OVERFLOW” and Exit
Step 2: [Allocate
free space]
New1 = Create new node
Step 3: [Read value
of information part of a new node]
Info [New1] = Value
Step 4: [Link
address part of the currently created node with the address of start]
Next [ New1] = Start
Step 5: [Now assign
address of newly created node to the start]
Start = New1
Step 6: Exit
4. Algorithm to insert a node at the end of list
Step 1: [Check for
free space]
If New1 = NULL output
“OVERFLOW” and Exit
Step 2: [Allocate
free space]
New1 = Create new node
Step 3: [Read value
of information part of a new node]
Info [New1] = value
Step 4: [Move the
pointer to the end of the list]
Repeat while node [Not]
NULL
Node = next [Node]
Previous = next
[Previous]
Step 5: [Link currently created node
with the last node of the list]
Next [New1] = node
Next [previous] = New1
Step 6: Exit
5. Algorithm to insert a node in a linked list at a desired place.
Step 1: [check for
availability space]
If New1 = NULL output
“OVERFLOW” and Exit
Step 2:
[Initialization]
Node_number = 0
Node = Start.Next
[Points to first node of the list]
Previous = Address of
Start [Assign address of start to previous]
Step 3: [Read
information of new node number]
Insert_node = Value
Step 4: [perform
insertion operation]
Repeat through Step 6
while Node <> NULL
Step 5: [Check
place where new should be insert]
If Info [Nde] <
Insert_node
Next [New1] = Node
Previous->Next
= new1
Info [new1] =
Insert_node
Return
Else [Move the pointer
forward]
Node = Next [Node]
Previous = Next
[Previous]
Step 6: Node_number
= Node_number + 1
Step 7: Exit
6. Algorithm to delete a node in a linked list at a desired place.
Step 1:[ Initialization
]
Node = Start.next
[Points to the first node in the linked list]
Previous = Address of
Start
Step 2: [Initialize
node counter]
Node_number = 1
Step 3: [Read
information associated with a node]
Delete_node = Value
Step 4: [Check list
is empty or not]
If Node = NULL
Output “OverFlow” and
Exit
Step 5: [Perform
deletion operation]
Repeat through 6 while
Node <> NULL
If Info [Node] =
Delete_node
(1) Next [Previous] =
Next [Node] [Make link of previous node to the
next node]
(2) Delete (Node) [Delete
current node]
(3) Exit
Step 6: Node_number = Node_number +
1
Step 7: Exit
Example :
#include<stdio.h>
#include<alloc.h>
struct list
{
int data;
struct list *next;
};
main()
{
struct list *node;
int ans;
node=NULL;
clrscr();
do
{
printf("\n\n1.
Enter new element :\n");
printf("2.Display
list :\n");
printf("3.exit:\n");
printf("4.Enter
new node at bagin:\n");
printf("5.Enter
new node at requird position:\n");
printf("6.Delete
the node:\n");
printf("Enter
your Choice:");
scanf("%d",&ans);
switch(ans)
{
case 1:create(&node);
break;
case 2:display(node);
break;
case 3:addatpos(&node);
break;
case 4:addatbag(&node);
break;
case
6:delnode(&node);
break;
default:
printf("you
have enter wrong choice..\n");
}
}while(ans!=30);
getch();
return;
}
create(struct list **q)
{
struct list *temp;
int a;
temp= *q;
if(*q==NULL)
{
*q=(struct list*)malloc(sizeof(struct list));
temp=*q;
}
else
{
while(temp->next!=NULL)
temp=temp->next;
temp->next=(struct list*)malloc(sizeof(struct list));
temp=temp->next;
}
printf("Enter the value:");
scanf("%d",&a);
temp->data=a;
temp->next=NULL;
return;
}
display(struct list*q)
{
while(q!=NULL)
{ printf("%d",q->data);
q=q->next;
}
return;
}
addatbag(struct list **q)
{
struct list* temp;
int a;
temp=malloc(sizeof(struct list));
printf("Enter the value:");
scanf("%d",&a);
temp->data=a;
temp->next=*q;
*q=temp;
return;
}
addatpos(struct list *q)
{
int
pos,a,flag=0;
struct list *temp;
printf("Enter the position:");
scanf("%d",&pos);
while(q!=NULL)
{
if(q->data==pos)
{
flag=1;
break;
}
q=q->next;
}
if(flag==0)
{
printf("Position is not proper;");
return;
}
printf("Enter the choice:");
scanf("%d",&a);
temp=malloc(sizeof(struct list));
temp->data=a;
temp->next=q->next;
q->next=temp;
return;
}
delnode(struct list **q)
{
struct list *temp,*old;
int
pos;
temp=*q;
printf("enter the position for
delete:");
scanf("%d",&pos);
while(temp!=NULL)
{
if(temp->data==pos)
{
if(temp==*q)
{
*q=temp->next;
free(temp);
return;
}
else
{
old->next=temp->next;
free(temp);
return;
}
}
else
{
old=temp;
temp=temp->next;
}
}
return;
}
1 comments:
edsds
Post a Comment