Section 28.5 Slicing and Splicing Lists
In Section 23.14, we saw how to split an array-based list into two parts. It involved creating a new array and then copying data over piece by piece. In a linked list, we can split a list into two parts by just changing a few links. For example, if we have a pointer to the node at which we want to split the list, we can just break the link from that node to the next one and return two new lists: one starting at the head of the original list and ending at that node, and one starting at the next node and ending at the tail of the original list.
Notice that splitting the list just involves changing a few pointers and updating the size. There would not be any more work to do if our list was 10,000 items long instead of just 4. Assuming we have the midpoint pointer, the split process is \(O(1)\text{.}\)
Of course, if we do not have the midpoint pointer, we will have to create one and move it step by step to the midpoint of the list. This would take \(O(n)\) time. However, especially if the items are large, the constant factor for moving a pointer \(O(n)\) times may be smaller than the constant factor for the \(O(n)\) part of slicing an array-based list, where \(n\) items have to be copied over to a new array.
Exploration 28.5.2. Splicing Linked Lists.
As with slicing, splicing just involves changing a few pointers and updating the size. Assuming we have tail pointers in the lists, we can do the entire operation in constant time (\(O(1)\)). There is no corresponding easy way to splice together two array-based lists. To merge those, we would need to copy all the items from the second to the first array (and possibly reallocate the array), which would require \(O(n)\) time.
Checkpoint 28.5.1.
You have attempted of activities on this page.
