File SinglyList.h

↰ Parent directory (ADS/sequence)

A SEQUENCE [see File ADT.h] realized as a singly linked list, not circular and with no sentinel (Esercizio 4.6 of the book).

Definition (ADS/sequence/SinglyList.h)

Detailed Description

The position :math:` pos_i ` is the address of the cell of :math:` a_{i-1} ` for i > 0 and nil for i = 0, so that the cell before an item, which insert() and remove() change, is always at hand: every operation takes O( 1 ) time but tail() and prev(), which scan the list and take O( n ). :math:` pos_n ` is the address of the last cell (nil if the list is empty), and :math:` pos_{-1} ` a distinguished address of the list itself. This is the convention of the realizations of a list with pointers or with cursors in which a position is the cell that precedes the item, e.g., in the book by Aho, Hopcroft and Ullman.

The contracts [see File Contract.h]: read(), write() and remove() need a position that holds an item, i.e., one that is not finished(); insert() and write() ensure that v is read back in its position. A list is copied cell by cell and moved in O( 1 ) time, the one moved from left empty. Beyond the book, the cells come from an ObjectPool [see File ObjectPool.h] of the list, which takes back the cell of remove() for the next insert(), so that a cell costs no call to the allocator, the cells made one after another are next to each other in memory, and a list of items with a trivial destructor dies in one step per block; the price is that the list keeps the memory of its largest size until it dies. The operations are defined in SinglyList.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, Esercizio 4.6, https://algoritmicamente.it/materiali/libro/capitoli/cap04.pdf

    1. Aho, J. E. Hopcroft, J. D. Ullman, Data Structures and Algorithms, Addison-Wesley, 1983, section 2.2

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

  • ADS/Contract.h (File Contract.h)

  • ADS/memory/ObjectPool.h (File ObjectPool.h)

  • ADS/sequence/impl/SinglyList.tpp

  • cstddef

  • initializer_list

  • iterator

  • type_traits

  • utility

Namespaces

Classes