Linked List (Deletion)

Data Structures
Lecture 7: Deletion from Linked List
By
Ravi Kant Sahu
Asst. Professor
Lovely Professional University, Punjab

Outlines
• Deletion from a Linked List
• Deletion Algorithm
– Deleting the Node following a given Node
– Deleting a Node with a given ITEM of Information
• Review Questions
Ravi Kant Sahu, Asst. Professor @ Lovely Professional University, Punjab (India)
Deletion from a Linked List
 A node N is to be deleted from the Linked List.

• Node N is between node A and node B.
 Deletion occurs as soon as the next pointer field of node A is

changed so that it points to node B.
 Types of Deletion:
• Deleting the node following a given node
• Deleting the Node with a given ITEM of Information.
Deletion from Linked List
START
ITEM Ø
Node A Node N Node B
Maintaining the AVAIL List
• After the deletion of a node from the list, memory space of
node N will be added to the beginning of AVAIL List.
• If LOC is the Location of deleted node N:
LINK [LOC] = AVAIL

AVAIL = LOC
Work Space
Deleting the Node Following a given Node
DEL (INFO, LINK, START, AVAIL, LOC, LOCP)
1. If LOCP = NULL, then:

Set START = LINK [START]. [Delete First node.]
Else:
Set LINK [LOCP] = LINK [LOC]. [Delete node N.]
[End of If Structure.]
2. [Return Deleted node to the AVAIL list]

Set LINK [LOC] = AVAIL and AVAIL= LOC.
3. EXIT.
Deleting the Node with a given ITEM of
Information
DELETE (INFO, LINK, START, AVAIL, ITEM)
1. Call FIND_B (INFO, LINK, START, ITEM, LOC, LOCP)
[Find the Location of node N and its preceding node]
2. If LOC = NULL, then: Write: ITEM not in LIST and EXIT.
3. [Delete node].
If LOCP = NULL, then:
Set START = LINK [START]. [Delete First node]
Else:
Set LINK [LOCP] = LINK [LOC].
4. [Return Deleted node to the AVAIL list]

Set LINK [LOC] = AVAIL and AVAIL= LOC.
5. EXIT.
FIND_B (INFO, LINK, START, ITEM, LOC, LOCP)
1. [List Empty?] If START = NULL, then:

Set LOC = NULL, LOCP = NULL and Return.
2. [ITEM in First node?] If INFO [START] = ITEM, then:

Set LOC = START, and LOCP = NULL, and Return.
3. Set SAVE = START and PTR = LINK [START]. [Initializes pointers]

4. Repeat step 5 and 6 while PTR ≠ NULL.
5. If INFO [PTR] = ITEM, then:
Set LOC = PTR and LOCP = SAVE, and Return.
6. Set SAVE = PTR and PTR = LINK [PTR]. [Update pointers]

[End of Step 4 Loop.]
7. Set LOC = NULL. [Search Unsuccessful.]
8. Return.
Exercise
• Write an algorithm to delete the last node of a linked list.
[Hint: Find out the address of last node and second last node]
Work Space
Header Linked List
Header Linked List
 A header linked list which always contains a special
node, called the header node, at the beginning of the
list.
START
Ø
HEADER NODE
Header Linked List
Name Salary LINK

2 0
START 1
5 59,000 6
2
E 10000 9
3
10 C 4000 7
AVAIL 4
8
5
B 20000 4
6
D 13000 3
7
1
8
F 12000 2
9
5
10
Advantages of Header Linked List
• Header linked list contains a special node at the top.
• This header node need not represent the same type of data that
succeeding nodes do.
• It can have data like, number of nodes, any other data...
• Header node can access the data of all the nodes in the linked
list.
Types of Header Linked List
 A Grounded header list is a header list where the last node
contains the null pointer.
 A Circular header list is a header list where the last node

points back to the header node.
Note:
• Unless otherwise stated or implied, header list will always be circular
list.
• Accordingly, in such a case, the header node also acts as a sentinel
indicating the end of the list.
START
Ø
HEADER NODE
Grounded Header List
START
HEADER NODE
Circular Header List
• If Link [START] = NULL,
then, Grounded Header List is Empty.
• If Link [START] = START,

then, Circular Header List is Empty.
Traversing a Circuar Header List
 Algorithm (Traversing a Circular Header list)
1. Set PTR = LINK [START]. [Initialize pointer PTR]

2. Repeat step 3 and 4 while PTR ≠ START.
3. Apply PROCESS to INFO[PTR].
4. Set PTR = LINK [PTR]. [PTR points to next node]
[End of Step 2 Loop.]
5. EXIT
Use of Header Linked List
• Header Linked lists are frequently used for maintaining
Polynomials in memory.
Review Questions
• What is the condition for the list being empty?
• Which pointer fields are changed when:

– a node is deleted after a given node
– a node is deleted which is at the end of list
– a node is deleted at the beginning of the list.

Linked List (Deletion)

Uploaded by

Copyright:

Available Formats

Linked List (Deletion)

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Linked List (Deletion)

Uploaded by

Copyright:

Available Formats

Data Structures

Lecture 7: Deletion from Linked List

Lovely Professional University, Punjab

 A node N is to be deleted from the Linked List.

 Deletion occurs as soon as the next pointer field of node A is

Node A Node N Node B

• If LOC is the Location of deleted node N:

LINK [LOC] = AVAIL

1. If LOCP = NULL, then:

2. [Return Deleted node to the AVAIL list]

4. [Return Deleted node to the AVAIL list]

1. [List Empty?] If START = NULL, then:

2. [ITEM in First node?] If INFO [START] = ITEM, then:

3. Set SAVE = START and PTR = LINK [START]. [Initializes pointers]

6. Set SAVE = PTR and PTR = LINK [PTR]. [Update pointers]

Name Salary LINK

• It can have data like, number of nodes, any other data...

 A Circular header list is a header list where the last node

Grounded Header List

Circular Header List

• If Link [START] = START,

1. Set PTR = LINK [START]. [Initialize pointer PTR]

• Which pointer fields are changed when:

You might also like