ALGORITHM

• DELETION AT BEGINNING
  1. if HEAD = NULL, write “UNDERFLOW”, and move to 6th step and exit.
  2. if not then follow the next steps
  3. SET PTR = HEAD
  4. SET HEAD = HEAD → NEXT
  5. FREE PTR i.e. Delete the node
  6. Exit
• DELETION AT THE END
  1. if HEAD = NULL, write “UNDERFLOW” and move to 10th step and exit
  2. if not then follow the steps below
  3. SET PTR = HEAD
  4. Repeat steps 5 and 6 while PTR → NEXT ≠ NULL
  5. SET PRE_PTR = PTR
  6. SET PTR = PTR → NEXT
  7. [END OF LOOP]
  8. SET PRE_PTR → NEXT = NULL
  9. FREE PTR
  10. Exit
• DELETION IN BETWEEN
  1. if HEAD = NULL, write “UNDERFLOW” and move to 10th step and exit
  2. if not then follow the steps below
  3. suppose INDEX is given
  4. SET PTR = HEAD
  5. SET PTR = PTR → NEXT, while you reach the index - 1 position in the linked list
  6. Declare a new node pointer i.e. new_ptr and SET NEW_PTR = PTR → NEXT
  7. SET P → NEXT = NEW_PTR → NEXT
  8. FREE NEW_PTR
  9. EXIT

SOURCE CODE

Linked List Declaration and initialization

#include<stdio.h>
#include<stdlib.h>

struct node{
	int data;
	struct node * next;
};

Traversal/print in Linked List

void linkedlistTraversal(struct node *ptr){
	while (ptr != NULL){
		//prints the element of the linked lists
		printf("Element: %d \\n", ptr -> data);
		ptr = ptr -> next;
	}
}

Linked list Deletion functions

1. Delete at the starting

struct node * deleteFirst( struct node * head){
    struct node * ptr = head;
    head = head -> next;
    free (ptr);
    return head;
}

1. Delete in between

struct node * deleteAtIndex ( struct node * head, int index){
    struct node * p = head;
    struct node * q = head -> next;
    for (int i = 0; i < index -1; i++ ){
        p = p -> next;
        q = q -> next;
    }
    p -> next = q -> next;
    free (q);
    return head;
}

1. Delete by Value

struct node * deleteTheValue(struct node * head, int value){
    struct node * p = head;
    struct node * q = head -> next;
    while ( q->data != value && q->next != NULL)
    {
        p = p -> next;
        q = q -> next;
    }
    if (q->data == value){
        p->next = q->next;
        free(q);
    }
    return head;
}

1. Delete in the end

struct node * deleteEnd( struct node * head){
    struct node * p = head;
    struct node * q = head -> next;
    while (q -> next != NULL){
        p = p -> next;
        q = q -> next;
    }
    p -> next = NULL;
    free (q);
    return head;
}

Driver Code

int main(){
	// node * xyx (xyz is a Pointer variable)
	struct node * head;
	struct node * second;
	struct node * third;
	struct node * fourth;

	//allocate memory for nodes in HEAP

	head = (struct node *)malloc(sizeof(struct node));
	second = (struct node *)malloc(sizeof(struct node));
	third = (struct node *)malloc(sizeof(struct node));
    fourth = (struct node *)malloc(sizeof(struct node));
	//link nodes '->' arrow operator

	head -> data = 1;
	head -> next = second;
	second -> data = 2;
	second -> next = third;
	third -> data = 3;
	third -> next = fourth;
    fourth -> data = 4;
	fourth -> next = NULL;
    printf("Linked list before deletion: \\n");
	linkedlistTraversal(head);

//uncomment the function call you wanna perform

    //head = deleteFirst(head);
    //head = deleteAtIndex(head, 2); //2 is the index number
    //head = deleteEnd(head);
    //head = deleteTheValue(head, 4);

    printf("Linked list after deletion: \\n");
    linkedlistTraversal(head);

    return 0;
}