COMPSCI 61B Lecture Notes - Lecture 5: Member Variable, Linked List
27 Jan 2018
School
Department
Course
Professor
Document Summary
2 lectures ago, we created an intlist which is a powerful recursive data structure. Problem is, intlist is awkward to work with, We"ve created the sllist, which hides some of the nakedness. A: maybe just cache the last node. In order to delete the final item, we need to know where the second to last item is, Answer: no because we need last to point to that afterwards. Solution: what we can do is link the data structure so that it has a previous and a next. Sllist singly linked list has a limitation: Special case: last pointer sometimes points at the sentinal, sometimes at a real node. For each methods, run into annoying if statement that checks sentinal. Instead having two sentinels, have a sentinel that represents both front and back. Add additional sentback sentinel at the end of the list. Make the linked list circular, with a single sentinel in the middle.
