tailieunhanh - Lecture Algorithms and data structures: Chapter 15 - Deleting an Element from a Linked List

In this topic, we will cover: Definition of a tree data structure and its components. Concepts of: Root, internal, and leaf nodes; parents, children, and siblings; paths, path length, height, and depth; ancestors and descendants; ordered and unordered trees; subtrees. | Review Inserting into a linked list involves two steps: Find the correct location Do the work to insert the new value We can insert into any position Front End Somewhere in the middle Deleting an Element from a Linked List Deletion involves: Getting to the correct position Moving a pointer so nothing points to the element to be deleted Can delete from any location Front First occurrence All occurrences The Node Definition Node definesa record data isoftype num next isoftype ptr toa Node endrecord The Scenario Begin with an existing linked list Could be empty or not Could be ordered or not 4 17 head 42 6 The Scenario Begin with an existing linked list Could be empty or not Could be ordered or not 4 17 head 42 6 The Scenario Begin with an existing linked list Could be empty or not Could be ordered or not 4 17 head 42 The Scenario Begin with an existing linked list Could be empty or not Could be ordered or not 4 17 head 42 Finding the Match We’ll examine three situations: Delete the first element Delete the first occurrence of an element Delete all occurrences of a particular element Deleting the First Element This can be done without any traversal/searching Requires an in/out pointer procedure DeleteFront (current iot in/out ptr toa Node) // deletes the first node in the list if (current nil) then current Deleting from a Linked List Deletion from a linked list involves two steps: Find a match to the element to be deleted (traverse until nil or found) Perform the action to delete Performing the deletion is trivial: current 4 17 head 42 6 . . Delete(head, 4) . . . . Delete(head, 4) . . procedure Delete(cur iot in/out ptr toa Node, target isoftype in num) // Delete single occurrence of a node. if(cur NIL) then if(cur^.data = target) then cur Deleting an Element from a Linked List Deletion involves: Getting to the correct position Moving a pointer so nothing points to the element to be deleted Can delete from any location Front First occurrence All occurrences The Node Definition Node definesa record data isoftype num next isoftype ptr toa Node endrecord The Scenario Begin with an existing linked list Could be empty or not Could be ordered or not 4 17 head 42 6 The Scenario Begin with an existing linked list Could be empty or not Could be ordered or not 4 17 head 42 6 The Scenario Begin with an existing linked list Could be empty or not Could be ordered or not 4 17 head 42 The Scenario Begin with an existing linked list Could be empty or not Could be ordered or not 4 17 head 42 Finding the Match We’ll examine