January 22, 2003

Reading material

Pages 206-211 (Section 5.3)

Additional material

Implementation of a list with a circular array in pseudocode: PostScript and PDF

public static void sort(List list)
{
    int b = 0;
    int w = 0;
    int r = 0;
    Iterator i = list.elements();
    while (i.hasNext())
    {
        Object e = i.next();
        if (e == BLUE)
        {
            b++;
        }
        if (e == WHITE)
        {
            w++;
        }
        if (e == RED)
        {
            r++;
        }
    }
    if (!list.isEmpty())
    {
        Position p = list.first();
        while (b != 0)
        {
            list.replaceElement(p, BLUE);
            b--;
            p = list.after(p);
        }
        while (w != 0)
        {
            list.replaceElement(p, WHITE);
            w--;
            p = list.after(p);
        }
        while (r != 0)
        {
            list.replaceElement(p, RED);
            r--;
            p = list.after(p);
        }
    }
}

Question

Consider the array based implementation of a list. In this implementation, each position contains an element and an index. For which operations would the worst case running time change if we would not store the index in a position?