Guide > Simple, Basic, and Advanced Data Types > Basic Data Types > Linear Lists

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



Algorithmic Solutions Software GmbH