Categories: Computers & Internet

Linked Lists – Deletion, Traversing the list

Deleting a node from a linked list is straightforward but there are a few cases
we need to account for:
1. the list is empty; or
2. the node to remove is the only node in the linked list; or
3. we are removing the head node; or
4. we are removing the tail node; or
5. the node to remove is somewhere in between the head and tail; or
6. the item to remove doesn’t exist in the linked list

The algorithm whose cases we have described will remove a node from any-where within a list irrespective of whether the node is the head etc. If you know
that items will only ever be removed from the head or tail of the list then you can create much more concise algorithms. In the case of always removing from
the front of the linked list deletion becomes an O(1) operation.

1) algorithm Remove(head, value)
2) Pre: head is the head node in the list
3) value is the value to remove from the list
4) Post: value is removed from the list, true; otherwise false
5) if head = ; 6) // case 1
7) return false
8) end if
9) n à head
10) if n.Value = value
11) if head = tail
12) // case 2
13) head à ; 14) tail à ; 15) else
16) // case 3
17) head à head.Next
18) end if
19) return true
20) end if
21) while n.Next 6= ; and n.Next.Value 6= value
22) n à n.Next
23) end while
24) if n.Next 6= ; 25) if n.Next = tail
26) // case 4
27) tail à n
28) end if
29) // this is only case 5 if the conditional on line 25 was false
30) n.Next à n.Next.Next
31) return true
32) end if
33) // case 6
34) return false
35) end Remove

 

Related Post

Traversing the list

Traversing a singly linked list is the same as that of traversing a doubly linked
list (de¯ned in x2.2). You start at the head of the list and continue until you
come across a node that is ;. The two cases are as follows:
1. node = ;, we have exhausted all nodes in the linked list; or
2. we must update the node reference to be node.Next.
The algorithm described is a very simple one that makes use of a simple
while loop to check the ¯rst case.

1) algorithm Traverse(head)
2) Pre: head is the head node in the list
3) Post: the items in the list have been traversed
4) n à head
5) while n 6= 0
6) yield n.Value
7) n à n.Next
8) end while
9) end Traverse




  • Khushal Sharma

    Recent Posts

    Heart Attack Causes and its Solution

    What is the Main Cause of a Heart Attack? What is its Solution? A heart attack is the blockage of… Read More

    1 year ago

    Understanding the Debt Ceiling: Its Impact, Importance, and Implications

    In the vast economic arena, one term that often takes center stage, inciting extensive debates and discussions, is the "debt… Read More

    2 years ago

    De-Dollarization: The New World Order of Currency and Its Global Impact

    De-Dollarization: The Changing Face of Global Finance The financial landscape is in a state of flux, with an intriguing economic… Read More

    2 years ago

    Unstoppable Bayern Munich: The Story Behind Their 11th Consecutive Bundesliga Title

    The curtains closed on a dramatic Bundesliga season with Bayern Munich standing tall once again, clinching their 11th straight title.… Read More

    2 years ago

    Celine Dion Cancels Concert Tour Due to Deteriorating Stiff-Person Syndrome

    The Unfolding Story of Celine Dion's Health In recent news that has left fans across the globe stunned, iconic singer… Read More

    2 years ago

    Navigating the Crossroads: LeBron James, Anthony Davis, and the LA Lakers’ Uncertain Future

    As the echoes of the recent NBA season start to fade, the attention of enthusiasts is firmly glued to one… Read More

    2 years ago