TAILIEUCHUNG - Lecture Algorithms and data structures (CSC112) - Chapter 15

Chapter 15 - Deleting an Element from a Linked List. The main contents of the chapter consist of the following: 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

• Kỹ thuật lập trình
• Data structures
• Lecture Algorithms and data structures
• Thiết kế thuật toán
• Cấu trúc dữ liệu
• Algorithm analysis
• Graph algorithms
• Design techniques
• Ebook Data structures and algorithms made easy
• Data structures and algorithms made easy
• Data structures and algorithmic puzzles
• Data structures for storing strings
• Algorithms design techniques
• algorithms
• data structure lectures
• structured document data
• teaching data structures
• algorithms in data structures
• Lecture Data Structures
• Bài giảng Cấu trúc dữ liệu
• Programming assignments
• Data structures organize data
• Resource constraints
• Lecture Data structures and algorithms
• Data structures and algorithms
• Cấu trúc dữ liệu và giải thuật
• Abstract data type
• Lecture ECE 250
• Memory allocation
• Computer science
• Design of data structures
• Algorithms in Java
• AVL trees
• Binary search trees
• Red black trees
• Splay trees
• Dynamic programming