Stepwise algorithm for inserting element at the end of a Linkedlist

INPUT: HEADER IS A POINTER TO THE HEADER NODE OF THE LINKEDLIST AND X IS THE ELEMENT TO BE INSERTED
OUTPUT: LINKEDLIST WITH THE ADDED ELEMENT
DATA STRUCTURE: SINGLY LINKEDLIST

STEP 1: NEW=GETNODE(NODE)
STEP 2: IF(NEW=NULL)THEN
STEP 3: PRINT("MEMORY INSUFFICIENT")
STEP 4: EXIT 
STEP 5: ELSE
STEP 6: PTR=HEADER->LINK
STEP 7: WHILE(PTR->LINK!-NULL)DO
STEP 8: PTR=PTR->LINK
STEP 9: ENDWHILE
STEP 10: NEW->DATA=X
STEP 11: NEW->LINK=NULL
STEP 12: PTR->LINK=NEW
STEP 13: ENDIF
STEP 14: STOP

The given pseudocode represents the process of appending a new node to the end of a singly linked list. Let’s break down each step:

The given pseudocode represents the process of appending a new node to the end of a singly linked list. Let’s break down each step:

Explanation of Steps

1. STEP 1: NEW = GETNODE(NODE)
   • Allocate memory for a new node. The GETNODE() function creates and returns a new node. If memory allocation fails, NEW will be NULL.
2. STEP 2: IF (NEW = NULL) THEN
   • Check if the memory allocation was unsuccessful. If NEW is NULL, it means the system couldn’t allocate memory for the new node.
3. STEP 3: PRINT(“MEMORY INSUFFICIENT”)
   • Display an error message indicating that memory is insufficient to create a new node.
4. STEP 4: EXIT
   • Exit the program since further operations cannot proceed without sufficient memory.
5. STEP 5: ELSE
   • If NEW is not NULL, proceed to append the node to the linked list.
6. STEP 6: PTR = HEADER->LINK
   • Initialize a pointer PTR to traverse the linked list. Start at the first node (HEADER->LINK).
7. STEP 7: WHILE (PTR->LINK != NULL) DO
   • Traverse the linked list by following the LINK field of each node until the last node is reached. The last node is identified when PTR->LINK is NULL.
8. STEP 8: PTR = PTR->LINK
   • Move PTR to the next node in the list.
9. STEP 9: ENDWHILE
   • End the loop once PTR points to the last node of the list.
10. STEP 10: NEW->DATA = X
    • Assign the data value X to the DATA field of the new node NEW.
11. STEP 11: NEW->LINK = NULL
    • Set the LINK field of the new node NEW to NULL since it will be the last node in the list.
12. STEP 12: PTR->LINK = NEW
    • Update the LINK field of the last node (pointed to by PTR) to point to the new node NEW, effectively appending it to the list.
13. STEP 13: ENDIF
    • End the conditional block.
14. STEP 14: STOP
    • End the algorithm.

Key Points

• This algorithm assumes that the linked list is non-empty and has a HEADER node pointing to the first element of the list.
• If the list is empty (HEADER->LINK = NULL), the algorithm would require modification to handle this special case.
• The new node is always appended at the end of the list.

Efficiency

• Time Complexity: O(n), where n is the number of nodes in the linked list, because the algorithm traverses the entire list to find the last node.
• Space Complexity: O(1), as it uses a constant amount of additional memory.

C code for inserting an element at the end of a Linkedlist

#include <stdio.h>
#include <stdlib.h>
int getnode(int);
void display();
void newnode();int x;struct node{int data;struct node *link;};struct node *prev,*head,*news,*p,*ptr;
struct node *header;
int main(){
int n;
printf("ENTER THE LIMIT");
scanf("%d",&n);
getnode(n);
return 0;}
void display(struct node *head){
struct node *ptr;
ptr=header->link;
while(ptr!=NULL){
printf("%d ",ptr->data);
ptr=ptr->link;} }
void newnode(){
 news=NULL;
news=malloc(sizeof(struct node));
 news->data=x;
 if(news==NULL) {
 printf("memory Insufficient");}
 else{
 ptr=head;
 while(ptr!=NULL){
 ptr=ptr->link;}
 news->link=NULL;
 p->link=news; }}
int getnode(int n){
header=malloc(sizeof(struct node));
head=NULL;
for(int i=0;i<n;i++){
p=malloc(sizeof(struct node));
scanf("%d",&p->data);
p->link=NULL;
if(head==NULL)
head=p;
else
prev->link=p;
prev=p;
}header->link=head;
display(header);
printf("Enter the number to be inserted at the end");
scanf("%d",&x);
newnode();
display(header);
return 0;}

The given program is intended to manage a singly linked list and perform two primary tasks:

1. Create and display a linked list based on user input for a specified number of nodes.
2. Insert a new node at the end of the list and display the updated list.

Output

user@computer$ : ENTER THE LIMIT2
1
2
1 2 Enter the number to be inserted at the end3
1 2 3