Guide > Simple, Basic, and Advanced Data Types > Basic Data Types > Singly Linked Lists

Singly Linked Lists

The data type slist can be used to store a number of objects of an arbitrary type T sequentially. Each element in the list knows its successor. Singly Linked Lists are closely connected to Linear Lists. The elements of a Singly Linked List are of type slist_item.

Example

The following program shows how to use Singly Linked Lists. It generates an slist SL of int and appends the numbers 1 to 100 to SL. Then it iterates over all elements of SL by starting at the first element and always accessing the successor of the current element. 
#include <LEDA/core/slist.h>

int main()
{
  leda::slist<int> SL;

  int i;
  for (i=1; i<=100; i++) SL.append(i);

  leda::slist_item lit=SL.first();
  while (lit!=nil) { //you can also use the forall()-macro
    std::cout << SL[lit] << " ";
    lit=SL.succ(lit);
  }
  std::cout << std::endl;

  return 0;
}

Strengths

  • space is proportional to number of objects stored in the list (needs even less space than Linear List)
  • objects are ordered sequentially
  • direct access to first and last element
  • direct access to successor of an element
  • iterating over all elements is fast in one direction
  • inserting/deleting an element at a specified position is efficient (front and end of list, after an element)

Disadvantages

  • no direct access to predecessor of an element
  • searching for an element is slow, i.e., 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 slist to replace a Linear List if memory is a major issue and you do not need access to the predecessors the list elements.
  • If you need to search frequently, consider using a Set.
  • If you need to access objects by position frequently, consider using a One Dimensional Array.

See also:

Linear Lists

One Dimensional Arrays

Sets

Manual Entries:

Manual Page Singly Linked Lists

User Defined Parameter Types

LEDA Item Concept



Algorithmic Solutions Software GmbH