COMPSCI 61B Lecture 6: ALists, Resizing vs SLists
Document Summary
Unlike the dllist, the alist will use arrays to store data instead of a linked list. Have to scan to the desired position. Slow for any i not near the sentinel node. Accessing the i element of an array takes constant time. Retrieval from any position of an array is very fast as it is independent of array size. The position of the next item to be inserted is always size. Size is always the number of items in the alist. The last item in the last is always in position size - 1. Any change in our list must be reflected in a change in one or more memory boxes in our implementation. Only size -> setting deleted item to zero is not necessary to preserve invariants, and thus not necessary for correctness. When the array gets too full (size == items. legnth), just make a new array.
