Topic: lists

topics > computer science > data > Group: sequences

list processing


Lists are variable length sequences made up of linked components. They are recursively defined by: a list is a sequence of components consisting of atoms or lists. An atom or a null list is the list terminator. Lists are representations of trees or sequences. Element insertion and deletion is just moving link values. Doubly-linked lists have both forward and backward links further simplifying insertions and deletions. Lists need an empty predicate, an atom predicate, a head and tail selector, and a list constructor. By providing a list representation for defined functions, both data and programming language can use lists as their data type. (cbb 5/80)
Subtopic: bidirectional vs. random access iterators up

Quote: keep bidirectional iterators separate from random access iterators; e.g., different algorithms for rotate and random shuffle using these iterators

Subtopic: element type up

Quote: ABC restricts data types to numbers, text, tuples, lists, and tables; lists and tables of the same type [»pembS1_1987]

Subtopic: doubly-linked up

Quote: a doubly-linked list with back pointers to node before last is 3-detectable and 1-correctable [»taylDJ11_1980]
Quote: use pointer-difference for a memory-efficient doubly linked list; efficient [»sinhP1_2005]

Subtopic: list implementation up

QuoteRef: landPJ_1966 ;;112 List has null predicate and head and tail selectors
QuoteRef: mccaJ_1960 ;;187 Lists made of ordered pairs (S expressions) must terminate with nil
QuoteRef: mckeWM_1966 ;;101 Euler: list by a sequence of memory locations

Subtopic: list header up

Quote: extend a list with a dummy header that includes the terminal sentinel; simplifies search and insert

Related Topics up

Topic: arrays (58 items)
Topic: list processing (15 items)
Topic: tuples
(17 items)

Updated barberCB 7/04
Copyright © 2002-2008 by C. Bradford Barber. All rights reserved.
Thesa is a trademark of C. Bradford Barber.