Chapter 14 - Linked List Traversal Inserting. The main contents of the chapter consist of the following: Dealing with node-based allocation with arrays; internally, it is still a linked list, only the nodes are contiguous in memory; it is no longer necessary to call the operating system for each new node; doubling the memory used is straight-forward; to halve the memory used, we just follow the linked list. | Review Linked List Insertion Description Deletion Description Basic Node Implementation Conclusion Linked List Traversal 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 (to preserve order) Linked List Traversal Traversal means “visiting” or examining each node. Simple linked list Start at the beginning Go one node at a time until the end Recursive procedure (or function) Given a head pointer Looks at just one node What procedure will look at the rest? The Node Code Node definesa record data isoftype Num next isoftype Ptr toa Node endrecord The Big Picture 42 heap stack head 98 12 6 LB The Little Picture 12 The Classic Code Procedure Traverse (current isoftype in Ptr toa Node) // Precon: Pass in pointer to a list // Purpose: Print each data item // Postcon: No changes to list if(current NIL) then print(current^.data) Traverse(current^.next) endif endprocedure // Traverse The Big Picture 42 heap stack head 98 12 6 Insertion Into Linked Lists Node Definition node definesa record data isoftype Num next isoftype ptr toa node endrecord The Scenario You have a linked list Perhaps empty, perhaps not Perhaps ordered, perhaps not You want to add an element into the linked list 48 17 142 head // Adding an Element to a Linked List Involves two steps: Finding the correct location Doing the work to add the node Finding the Correct Location Three possible positions: The front The end Somewhere in the middle head Inserting to the Front There is no work to find the correct location Empty or not, head will point to the right location 48 17 142 head 93 Inserting to the End Find the end of the list (when at NIL) Recursion or iteration 48 17 142 head // 93 // Don’t Worry! Inserting to the Middle Used when order is important Go to the node that should follow the one to add Recursion or iteration 17 | Review Linked List Insertion Description Deletion Description Basic Node Implementation Conclusion Linked List Traversal 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 (to preserve order) Linked List Traversal Traversal means “visiting” or examining each node. Simple linked list Start at the beginning Go one node at a time until the end Recursive procedure (or function) Given a head pointer Looks at just one node What procedure will look at the rest? The Node Code Node definesa record data isoftype Num next isoftype Ptr toa Node endrecord The Big Picture 42 heap stack head 98 12 6 LB The Little Picture 12 The Classic Code Procedure Traverse (current isoftype in Ptr toa Node) // Precon: Pass in pointer to a list // Purpose: Print each data item // Postcon: No changes to list if(current NIL) then print(current^.data) .
