Lecture Notes for SE 598, Data Structures and Algorithms

12 July 2000, Implementing Lists

1. operations and behavior

   1. create - create a list

   2. delete - delete a list

   3. grow - add new elements to a list

   4. shrink - delete elements from a list

   5. size - return the number of elements in a list

   6. note the absence of read and write - done indirectly through iterators and references

2. design

   1. use a linked list

      1. each list element contains a value and a pointer to the next list element

         1. template <typename T>
            struct list_element {
              list_element<T> * next;
              T value;
              }
            

      2. have a head with two pointers, one to the beginning and the other to the end of the list

         1. template <typename T>
            struct list {
              list_element<T> * begin, end;
              }
            

      3. creating is fast and simple, deleting is slow and simple

      4. grow and shrink

         1. push_front() and pop_front() are fast and reasonably simple

            1. le = new list_element;	// this code is incomplete. (why?)
               le->next = lhead.begin;
               lhead.begin = le;
               

            2. le = lhead.begin;		// this code is incomplete. (why?)
               lhead.begin = le->next;
               delete le;
               

         2. push_back() and pop_back() are reasonably simple and ...

            1. the problem is getting to the list element before the one being deleted - there's no direct pointer to the previous element

            2. traversing the list to find the previous list element makes push_back() and pop_back() slow

            3. need direct pointers to both the previous and next list elements - a doubly linked list

               1. template <typename T>
                  struct list_element {
                    list_element<T> * previous, next;
                    T value;
                    }
                  

            4. now push_back() and pop_back() are fast if a bit less simple to do.

               1. le = new list_element		// this code is incomplete. (why?)
                  le->previous = lhead.end
                  le->next = nil
                  lhead.end->next = le
                  lhead.end = le
                  

               2. le = lhead.end		// this code is incomplete. (why?)
                  le->previous->next = nil
                  lhead.end = le->previous
                  delete le
                  

         3. insert() and erase() are also fast and simple with doubly-linked lists

         4. splice() is also fast and simple to do with doubly-linked lists

      5. size is fast and simple with an auxiliary variable

   2. use an array

      1. almost like using a linked list

      2. each list is a set of three arrays (or vectors)

         1. template <typedef T, int size>
            struct list {
              vector<int> previous(size), next(size);
              vector<T>   values(size);
              int         begin, end;
              int         free;
              }
            

      3. for the i-th list element

         1. list.values[i] is its value

         2. list.previous[i] is the index of the previous list element

         3. list.next[i] is the index of the next list element

      4. list.begin and list.end are the indices of the first and last elements on the list.

      5. array-list operations are almost identical to the linked-list versions

      6. the free list is a second linked-list keeping track of the unused list elements - efficient allocation and de-allocation

      7. arrays eliminate the overhead of allocating and de-allocating list elements

         1. but, creation may be more expensive

         2. linked lists can make use of free lists to cut overhead too

This page last modified on 25 July 2000.