COMPSCI 61B Lecture 5: DLLists, Arrays
Document Summary
Inserting at the back of an sllist is much slower than the front because for a long list, the addlist method has to walk through the entire list. We can attempt to speed things up by adding a last variable to speed up our code (like size). This structure will support rapid addlast and getlast but removelast will still be slow because we have no easy way to get to the second-to-last node, to update the last pointer, after removing the last node. Realize that if every node had a pointer to the element behind it, we would never have to scan our node from the front to find the predecessor. Add a backwards link from every node. This yields a doubly linked list or dllist rather than our earlier singly linked list or. Reverse pointers allow all operations to be fast.
