Topic:
arrays
Topic:
list processing
Topic:
tuples
| |
Summary
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 
| Quote: keep bidirectional iterators separate from random access iterators; e.g., different algorithms for rotate and random shuffle using these iterators
|
Subtopic: element type
| Quote: ABC restricts data types to numbers, text, tuples, lists, and tables; lists and tables of the same type [»pembS1_1987]
|
Subtopic: doubly-linked
| 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
| 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
Quote: extend a list with a dummy header that includes the terminal sentinel; simplifies search and insert
[»ancoM6_1998]
|
Related Topics
Topic: arrays (58 items)
Topic: list processing (15 items)
Topic: tuples
(17 items)
|
