Skip to content

List

final class List<Type>

Doubly-linked list. Provides constant-time operations at the front and back of the list, and linear-time operations elsewhere.

  • Type Element type. Must be default-constructible.

The data structure is a doubly-linked list:

graph LR this --"front()"--> a[1] --> b[2] --> c[3] --> d[4] --> e(...) --> f[n] this --"back()"--> f --> e --> d --> c --> b --> a

Note

As a recursive data structure, List has good performance properties under Birch's lazy deep copy mechanism. It is, however, doubly-linked rather than singly-linked. Consider whether a singly-linked data structure such as Stack or Tape can be used instead, as this may improve performance further.

Attention

Large recursive data structures can cause an execution stack overflow on destruction that usually manifests as a segmentation fault. Possible solutions include:

  1. Use an array (Type[_]) or Array instead.
  2. Remove items one-by-one before the object goes out of scope.
  3. Increase the execution stack size with the shell command ulimit.

Slices

Name Description
[...] Reference to an element.

Member Functions

Name Description
size Number of elements.
empty Is this empty?
clear Clear all elements.
front Get the first element.
back Get the last element.
get Get an element.
set Set an element.
pushFront Insert an element at the front.
pushFront Insert a new default-constructed element at the front and return it.
pushBack Insert an element at the back.
pushBack Insert a new default-constructed element at the back and return it.
popFront Remove the first element.
popBack Remove the last element.
insert Insert a new element.
erase Erase an element.
walk Obtain an iterator.
getNode Get a node.

Member Slice Details

[i:Integer] -> Type

Reference to an element.

Member Function Details

back

function back() -> Type

Get the last element.

clear

function clear()

Clear all elements.

empty

function empty() -> Boolean

Is this empty?

erase

function erase(i:Integer)

Erase an element.

  • i Position.

front

function front() -> Type

Get the first element.

get

function get(i:Integer) -> Type

Get an element.

  • i Position.

getNode

function getNode(i:Integer) -> ListNode<Type>

Get a node.

  • i Position.

insert

function insert(i:Integer, x:Type)

Insert a new element.

  • i Position.
  • x Value.

Inserts the new element immediately before the current element at position i. To insert at the back of the container, use a position that is one more than the current size, or pushBack().

popBack

function popBack()

Remove the last element.

popFront

function popFront()

Remove the first element.

pushBack

function pushBack(x:Type)

Insert an element at the back.

  • x Value.

function pushBack() -> Type

Insert a new default-constructed element at the back and return it.

pushFront

function pushFront(x:Type)

Insert an element at the front.

  • x Value.

function pushFront() -> Type

Insert a new default-constructed element at the front and return it.

set

function set(i:Integer, x:Type)

Set an element.

  • i Position.
  • x Value.

size

function size() -> Integer

Number of elements.

walk

function walk() -> Iterator<Type>

Obtain an iterator.

Returns an iterator across elements in forward order.