Lecture Notes for SE 598, Data Structures and Algorithms

12 July 2000, List Algorithms

1. list structure

   1. sequential - linear; value after another

   2. open access - values may enter and leave at any point in the list

   3. lists are not order preserving

   4. stl lists are a bit of a pain though

      1. bidirectional iterators, no i + 1 or i - 1, only ++ and --

      2. iterator invalidation - what happens to i after l.erase(i)?

2. list algorithms

   1. list merging

      1. start with two lists, each having a property (sorted, for example)

      2. combine the two lists into one and preserve the property (the merged list is sorted, for example)

      3. list::iterator l1_begin = list1.begin();
         list::iterator l2_begin = list2.begin();
         
         while ((l1_begin != list1.end()) && (l2_begin != list2.end())) {
           list::iterator l1_next = list1.end(); l1_next++;
           list::iterator l2_next = list2.end(); l2_next++;
           if (*l1_begin <= *l2_begin) {
             list3.splice(list3.end(), list1, l1_begin);
             l1_begin = l1_next;
             }
           else {
             list3.splice(list3.end(), list2, l2_begin);
             l2_begin = l2_next;
             }
           }
         
         while (l1_begin != list1.end()) {
           list::iterator next = list1.end(); next++;
           list3.splice(list3.end(), list1, l1_begin);
           l1_begin = next;
           }
         while (l2_begin != list2.end()) {
           list::iterator next = list2.end(); next++;
           list3.splice(list3.end(), list2, l2_begin);
           l2_begin = next;
           }
         
         

      4. this is the merge() generic algorithm.

      5. merging is the basis for divide-and-conquer, a powerful, efficient, and useful way to derive algorithms

   2. insertion sort

      1. a sequence of values have some property (are sorted, for example)

      2. to add a new value to the sequence, find where it belongs according to the property and insert it.

      3. lists are ready-made for this kind of manipulation.

      4. for (list::iterator end = ilist.begin(); end != ilist.end(); end++) {
           list::iterator next = end;
           next++;
           for (list::iterator here = ilist.begin(); here != end; here++)
             if (*next <= *here) {
               ilist.splice(here, ilist, next);
               break;
               }
           }
         

      5. this is the basis for the insertion sort, a simple, semi-efficient way to sort

      6. not really necessary because of the l.sort() member function

   3. lists of lists are a useful data structure

      1. searching through lots of strings for a name - sorting helps a bit

      2. store the first letter of each string, and a list of all strings starting with that letter

         1. now initial search is fast

         2. saving space by sharing the first letter too

      3. now apply the same idea to the list of strings sharing the same first letter

      4. this is known as the prefix tree because it extracts and shares common prefixes among the strings

This page last modified on 25 July 2000.