Deletion from a Linked list in Data Structures

Let LIST be a linked list with a node N between nodes A and B. Suppose node N is to be deleted from the linked list.

Delete the node following a given node

Let LIST be a linked list in memory. Suppose we are given the location LOC of a node N in LIST. Furthermore, suppose we are given the location LOCP of the node preceding N or, when N is the first node, we are given LOCP = NULL. The following algorithm deletes N from the list.

Algorithm: (Deletion from the linked list.)

DEL(INFO, LINK, START, AVAIL, LOC, LOCP).
This algorithm deletes the node N with location LOC. LOCP is the location of the node which precedes N or, when N is the first node, LOCP = NULL.

Step I: [UNDERFLOW?]
If START = NULL, then: Write: UNDERFLOW and Exit.

Step II: If LOCP = NULL, then:
Set START := LINK[START]. [Delete first node.]
Else:
Set LINK[LOCP] := LINK[LOC]. [Delete node N.]
[End of If structure.]

Step III: [Add node to the free storage list.]
(i) Set LINK[LOC] := AVAIL,
(ii) AVAIL := LOC.

Step IV: Exit.

Deleting the node with a given ITEM of information

(i) Algorithm: (Search the location for deletion.)

SEARCH(INFO, LINK, START, ITEM, LOC, LOCP).

This procedure finds the location LOC of the first node N which contains ITEM and the location LOCP of the node preceding N. If ITEM does not appear in the list, then, the procedure sets LOC = NULL; and if ITEM appears in the first node, then, it sets LOCP = NULL.

Step I: [List empty?]
If START = NULL, then:
Set LOC := NULL and LOCP := NULL, and Return.
[End of If structure.]

Step II: [ITEM in first node?]
If ITEM = INFO[START], then:
Set LOC := START and LOCP := NULL, and Return.
[End of If structure.]

Step III: [Initialize SAVE and PTR.]
Set SAVE := START and PTR := LINK[START].

Step IV: Repeat step 5 while PTR != NULL:

Step V: If ITEM = INFO[PTR], then:
Set LOC := PTR, and LOCP := SAVE and Return.
Else:
Set SAVE := PTR, and PTR := LINK[PTR].
[End of If structure.]
[End of step 4 loop.]

Step VI: [Search unsuccessful?]
Set LOC := NULL.

Step VII: Return.

(ii) Algorithm: (Deletion from linked list.)

DELETE(INFO, LINK, START, AVAIL, ITEM).

This algorithm deletes from a linked list the first node N which contains the given ITEM of information.

Step I: [Find the location of N and its preceding node.]
Call SEARCH(INFO, LINK, START, ITEM, LOC, LOCP).

Step II: If LOC = NULL, then: Write: ITEM not in list, and Exit.

Step III: [Delete node.]
If LOCP = NULL, then:
Set START := LINK[START]. [Delete first node.]
Else:
Set LINK[LOCP] := LINK[LOC].
[End of If structure.]

Step IV: [Add node to the free storage list.]
Set LINK[LOC] := AVAIL and AVAIL := LOC.

Step V: Exit.