A single linked list or one way list is a linear collection of data elements, called nodes. Each node has two parts. First part is INFO part which stores the information and another part is POINTER which points to the next elements. The drawback of the single linked list is that it cannot access the predecessor of the node from the current node. This can overcome in doubly linked list.
Inserting nodes To insert nodes into inked list , insert an element into the following three things should be done
A. Allocating node
B. Assigning the data
C.
Adjusting the pointers
o insert the new node into the
linked list has the following three instances
1. A new node
may be inserted at the beginning of the linked list.
2. Insert node
at the end of the linked list
3. insert node
at specified position of the linked list.
Inserting at the Beginning of a
List:
Algorithm:
Insert at beginning
INSFIRST (START, ,ITEM)
This
algorithm inserts ITEM as the first node in the list
Step
1: [OVERFLOW ?] If ptr =NULL, then
Write:
OVERFLOW
Return
Step
2: ptr =(NODE*)malloc(sizeof(NODE)
Step
3: Set ptr-> data=ITEM [Copies new data into new node]
Step
4: Set ptr-.next = START
[New
node now points to original first node]
Step
5: Set START:=NEW [Changes START so it points to new node]
Step
6: Return
Pseudo-code
for insertion
void insertatbegining()
{
NODE *ptr;
int item;
ptr = (NODE *) malloc(sizeof(NODE));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter value\n");
scanf("%d",&item);
ptr->data = item;
ptr->next = start;
start = ptr;
printf("\nNode inserted");
}
}
Insert
node at end of the list
Algorithm:
INS_LAST(START,ITEM)
This
algorithm inserts ITEM as the end of node in the list
Step
1: [OVERFLOW ?] If ptr =NULL, then
Write:
OVERFLOW
Return
Step
2: ptr =(NODE*)malloc(sizeof(NODE)
Step
3: Set ptr-> data=ITEM [Copies new data into new node]
Step
4: Set ptr-.next = Null
[New
node now points to original first node]
Step
5: if START:=Null then set START= ptr
Step
6: Set temp = Start
Step7:
Repeat step 8 until temp -> next != Null
step
8: set temp=temp->next
Step
9: set temp -> next= ptr
Step
10: Return
Sample
code /Pseudo code
void insertatend()
{
NODE *ptr,*temp;
int item;
ptr = (NODE*)malloc(sizeof(NODE));
printf("\nEnter value?\n");
scanf("%d",&item);
ptr->data = item;
if(start == NULL)
{
ptr -> next = NULL;
start = ptr;
printf("\nNode inserted");
}
else
{
temp = start;
while (temp -> next != NULL)
{
temp = temp -> next;
}
temp->next = ptr;
ptr->next = NULL;
printf("\nNode inserted");
}
}
Deleting
a node
This operation is
used to delete node from the linked list. a node may be deleted from the
at the beginning of the linked list, or at the end of the linked list, or at
the specified position of the linked list.
in order to delete node from linked list , it is
necessary to search for the location of deletion. The following steps involved in deleting the node from the linked
list.
1. If the linked
list is empty then display the message as "Deletion is not possible".
2. If the node to be deleted is the first node
(pointed by the head or start pointer)then set the pointer of head /start to
point the second node in the list
3. If the node
to be deleted is last node, then go on locating the last but one node and set
link field to point to null pointer.
4. If the
situation is other than the above three , then the delete the node from the
specified position within the linked list.
|
SN |
Operation |
Description |
|
1 |
It involves deletion of a node from the beginning
of the list. This is the simplest operation among all. It just need a few
adjustments in the node pointers. |
|
|
2 |
It involves deleting the last node of the list.
The list can either be empty or full. Different logic is implemented for the
different scenarios. |
|
|
3 |
It involves deleting the node after the specified
node in the list. we need to skip the desired number of nodes to reach the
node after which the node will be deleted. This requires traversing through
the list. |
Delete
node at beginning
Delete-at-beginning (START)
This
algorithm deletes element from the first position in the linked list
Step
1: [OVERFLOW ?] If start =Null, then
Write:
OVERFLOW - Linked List is Empty
Return
Step
2: Set ptr = Start
Step
3: Set start= start-.next
Step
4: Print the element deleted as ptr->data
Step
5:free(ptr)
Pseudo-code
for Deletion at starting
void
delete_at_begining()
{
NODE *ptr;
int item;
ptr = (NODE *) malloc(sizeof(NODE));
if(ptr == NULL)
{
printf("\nOVERFLOW
List is Empty");
}
else
{
ptr = start;
start = ptr->next;
free(ptr);
printf("\nNode deleted from the begining ...\n");
}
}
Delete
node at End
Algorithm
Delete-at-end (START)
This
algorithm deletes element from the last position in the linked list
Step
1: [OVERFLOW ?] If start =Null, then
Write:
OVERFLOW - Linked List is Empty
Return
Step
2: Set ptr = Start
Step
3: while ptr->next != Null
Step
4: Set ptr=ptr->next
Step
5:Set ptr->next=Null
Step
6:free(ptr)
Pseudo-code
for Deletion at ending
void
delete_at_begining()
{
NODE *ptr;
int item;
ptr = (NODE *) malloc(sizeof(NODE));
if(ptr == NULL)
{
printf("\nOVERFLOW
List is Empty");
}
else
{
ptr =start;
while(ptr->next != NULL)
{
ptr1 = ptr;
ptr = ptr ->next;
}
ptr1->next = NULL;
free(ptr); }
}
Delete
Node at specified position
Algorithm
Delete-at-end (START)
This
algorithm deletes element from the last position in the linked list
Step
1: [OVERFLOW ?] If start =Null, then
Write:
OVERFLOW - Linked List is Empty
Return
Step
2: Set ptr = Start
Step
3: Find the location to delete node
Step
4: Repeat Step 5& 6 until specified loc
Step
5: Set ptr1=ptr
Step 6:Set ptr= ptr->next
Step
7: Set ptr1->next= ptr->next
Step
8:free(ptr)
Pseudo-code
void random_delete()
{
struct node *ptr,*ptr1;
int loc,i;
printf("\n Enter the location of the node after which you want to perform deletion \n");
scanf("%d",&loc);
ptr=head;
for(i=0;i<loc;i++)
{
ptr1 = ptr;
ptr = ptr->next;
if(ptr == NULL)
{
printf("\nCan't delete");
return;
}
}
ptr1 ->next = ptr ->next;
free(ptr);
printf("\nDeleted node %d ",loc+1);
}
No comments:
Post a Comment