Lecture Notes for Computer Algorithms I

14 October 2003 - Array-Based Linked Lists

1. Can we do better?

2. Move-to-the front lists.

3. Indirection, the programmer's friend.

   1. Move to the front lists require O(n) data movement.

      1. Which is doubly expensive.

   2. Can we do better?

      1. What's the problem?

      2. data[i + 1] is cheap to use but expensive to maintain.

         1. It requires a lot of shifting around.

      3. Can we maintain the next-element relation without so much shifting around?

4. Array-based linked lists.

   1. Remember what arrays are: they map indices to values.

      1. And indicies are integers, which are cheap to move.

   2. If mapping is good once, maybe it'll be good twice.

      1. Given element i, find the next element at location next[i].

         1. next[i] is almost as cheap as i + 1.

         2. Maintaining next costs something, but not as much as moving data elements around.

         3. And it's more complex to implement.

   3. Move-to-the-front lists work best when the data are skewed.

      1. The skew may change over time.

      2. An example of a self-adjusting data structure.

   4. An alternative is to move forward one on each access.

      1. Performance can degenerate due to Alphonse and Gastoning.

5. Implementation.

   1. Data structures.

      1. An array for elements.

      2. An array for next indices.

      3. A count of the number of elements in the roster.

      4. The index of the roster's first element (it's head).

      5. The index of the free list.

   2. Procedures

      1. Initialization.

         1. Hang everything on the free list

      2. add(e)

         1. Allocate an element from the free list.

         2. Link the new element at the head of the list.

      3. find(e)

         1. Walk the elements one by one, checking the data against e.

      4. delete(e)

         1. Find e.

         2. Splice it out of the list.

            1. This is most easily done with a trailing index.

               1. And tailing indices are most easly done with a dummy head.

         3. Hang the element on the free list.

This page last modified on 13 October 2003.