File CursorList.h

↰ Parent directory (ADS/sequence)

A SEQUENCE [see File ADT.h] realized with cursors, beyond the book: the cells of the lists are the places of a vector, a CursorSpace, and a link is the index of the next cell, 0 being nil (the place 0 is never used).

Definition (ADS/sequence/CursorList.h)

Detailed Description

Several lists can share one space, each being the cursor of its first cell, and the free cells form a further list in the same vector, the free list: insert() takes its first cell, remove() gives the cell back, and a space whose free list is empty doubles its vector, the cursors staying valid. This is how a language with no pointers, or a program that wants its lists in one block of memory, realizes linked lists.

As in SinglyList [see File SinglyList.h], the position :math:` pos_i ` is the cursor of the cell of :math:` a_{i-1} ` for i > 0 and 0 for i = 0, so that insert() and remove() find the link to change at hand and take O( 1 ) time (amortized, for the growth of the space); :math:` pos_n ` is the cursor of the last cell (0 if the list is empty) and :math:` pos_{-1} ` is -1. tail() and prev() scan the list, in O( n ).

The contracts [see File Contract.h]: read(), write() and remove() need a position that holds an item; insert() and write() ensure that v is read back in its position; the invariant of the space is that the free cells and the cells in use are all the places but 0, the free list having no cycle. A list made with no space has a space of its own; the lists of a space share it, and the space lives as long as one of them does. The operations are defined in CursorList.tpp.

    1. Aho, J. E. Hopcroft, J. D. Ullman, Data Structures and Algorithms, Addison-Wesley, 1983, section 2.2 (the realization with cursors, the free list and the procedure move)

    1. Knuth, The Art of Computer Programming, vol. 1, 3rd ed., Addison-Wesley, 1997, section 2.2.3 (the available space list)

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes