Page 118 - DCAP407_DATA_STRUCTURE

Unit 6: Linked List Operations

4. The function insert_beginning() prompts input from user and inserts the
entered number in the first position of the list.
5. The function display() displays the list every time a new element is added
to the list.
6. The program terminates when the user enters 3.

6.4 Deleting a Node from a Linked List

Figure 6.3 depicts the deletion of a node from the linked list. The linked list consists of five nodes such
as, START, Node1, Node2, Node3, and Node4 respectively. If Node3 has to be deleted from the list,
then assign the address of Node4 to Node2. This is represented as:
Node2->next=&Node4

Figure 6.3: Deleting a Node from a Linked List

6.4.1 Deleting a Node Following a Given Node

Let us consider START as the initial position in a list, data as the element to be deleted, and temp and q
as the temporary pointers to hold the address of the node.
Algorithm for deleting a node is as follows:
1. Input the data to be deleted

2. If START is equal to the data entered by the user, then
(a) temp=START
(b) START=START->link
(c) free the deleted temp node
(d) exit
3. Assign START to q

4. While (q->link->link) is not equal to NULL, check if(q->link->data) is equal to data. If true then
execute the statements in step 5.
5. temp=q->link
q->link=temp->link
free the deleted temp node

LOVELY PROFESSIONAL UNIVERSITY 111