Linear Lists
The data type list can be used to store a number of objects of an arbitrary type T sequentially. Each element in the list knows its predecessor
and successor. The elements of a List are of type list_item.
Example
The following program shows how to use lists. It generates a list
L of int and appends the numbers 1 to 100 to L. Then
it iterates over all elements of L and outputs each element.
The last two lines of the program show how the first element of the list
and the predecessor and successor of elements can be accessed.
#include <LEDA/core/list.h>
int main()
{
leda::list<int> L;
int i;
for (i=1; i<=100; i++) L.append(i);
forall(i,L) std::cout << i << " ";
std::cout << std::endl;
std::cout << L.head() << std::endl;
std::cout << L.inf(L.pred(L.succ(L.first()))) << std::endl;
return 0;
}
Strengths
- space is proportional to current number of objects in the list
- objects are ordered sequentially
- direct access to first and last element
- direct access to predecessor and successor of an element
- iterating over all elements is fast in both directions (see also
Singly Linked Lists)
- inserting and deleting an element at a specified position is efficient
(front and end of list, before and after an element)
Disadvantages
- searching for an element is slow (proportional to the size of the
list) (alternative: Sets)
- access to the i-th element of the list is slow (alternative: One
Dimensional Array)
Tips
- Use list if you frequently have to iterate over your objects or the
number of objects to store varies a lot or if you need to insert/delete
elements fast at an arbitrary position.
- If you do not need direct access to the predecessor of an element
and memory is a major issue, consider using a Singly
Linked List.
- If you need to search frequently, consider using a Set.
- If you need to access your objects by position frequently, consider
using a One Dimensional Array.
|
See also:
Singly Linked Lists
Sets
One Dimensional Arrays
Lists of Node
Manual Entries:
Manual
Page Linear Lists
User
Defined Parameter Types
LEDA
Item Concept
|