COMPSCI 61B Lecture Notes - Lecture 5: Doubly Linked List, Linked List, Member Variable
29 Jan 2017
School
Department
Course
Professor
Document Summary
Generalizing: adding a sentinel node to allow representation of the empty list. Looking back: . last and . prev allow fast removelast. Sentinel upgrade: avoiding special cases with sentback or circular list. Inserting at the back of an sllist is much slower than the front. Adding a cache for . last is not enough, since it results in fast operations for add and get, but remove is very slow. Add backwards links from every node in addition to adding the cache for . last. This yields a doubly linked list or dllist, as opposed to a singly linked list or. Reverse pointers allow all operations (add, get, remove) to be fast. Non-obvious fact: annoying special case, when last sometimes points at the sentinel and sometimes points at a real" node. One common sentinel used for back and front. While fast, adding . last and . prev introduces lots of special cases. Add an additional sentback sentinel at the end of the list.
