Week 5. Lists

List

List

A list is a collection $S$ of elements stored in a certain linear order.

$$S:\{E_1,E_2,E_3,\dots ,E_i,\dots ,E_n\}$$

We can refer to the elements in $S$ as first, second, third, … The index of an element $e$ in $S$ is the number of elements before $e$ in $S$. The index can be used to specify where to insert a new element into the list, or where to remove an old element from.

Link to original

Array List ADT

Array List (ADT)

An instance is a sequence of $S$ of elements. Methods include:

• size(): return the number of elements in $S$
• isEmpty(): return true if $S$ has no elements, otherwise false
• get(i): return the element of $S$ with index $i$ ($1$-st element has index $0$) Error occurs if $i<0$ or $i>\text{size}()-1$.
• set(i,e): replace with $e$ the element at index $i$ and return the old element at this index Error occurs if $i<0$ or $i>\text{size}()-1$.
• add(i,e): insert a new element $e$ into $S$ to have index $i$ Error occurs if $i<0$ or $i>\text{size}()$.
• remove(i): remove from $S$ and return the element at index $i$ Error occurs if $i<0$ or $i>\text{size}()-1$.

Link to original

Extending full arrays

Inserting a new element to the list when the array is full: we allocate a new larger array and copy all elements to the new array.

Consider we start with an empty list and perform $n$ “add” operations, adding each new element at the end of the list. If we keep increasing the capacity of a full array by $1$, then the running time of this computation is $\Theta (1+2+3+\dots +n)=\Theta (n^2)$.

If we instead double the capacity, then the running time is $\Theta (n)$ for adding the elements when there is room in the array.

Performance

In the array-based implementation of the Array List ADT, if the list has $n$ elements:

• The space used is $O(n)$.
• Operations size, isEmpty, get, and set run in $O(1)$ time.
• Operation remove(i) runs in $O(n)$ time, or, more precisely in $\Theta (n-1)$.
• Removing the last element takes $O(1)$ time.
• Adding a new element at the end of the list takes $\Theta (n)$ time in the worst case (full array), but only $O(1)$ time on average.

Position

Position

The position is a place within a list where a single element is stored. In implementations, positions are nodes of lists.

Link to original

Node List ADT

Node List (ADT)

The Node List ADT models a sequence of positions storing elements of some arbitrary type. It establishes a before / after relation between positions.

It has generic methods:

• size()
• isEmpty()

We use an argument $p$ throughout to indicate the position. Accessor methods:

• first()
• last()
• prev(p)
• next(p) Update methods:
• set(p, e): replace the element at $p$ with $e$ and return the old eleent
• remove(p): remove and return the element at $p$
• addFirst(e) and addLast(e)
• addBefore(p, e) and addAfter(p, e)

Link to original

Doubly Linked List

A double-linked list provides a natural implementation of the Node List (ADT). Nodes implement Position and store:

• an element
• reference to the previous node
• reference to the next node There are also special trailer and header nodes. (or pointers can be null)

Link to original

Performance

In the implementation of the Node List ADT by means of a doubly linked list:

• The space used by each node of the list is $O(1)$.
• The space used by a list with $n$ elements is $\Theta (n)$.
• All the operations of the Node List ADT run in $O(1)$ time.
• The position operation element() runs in $O(1)$ time.
• No efficient implementation of operations which refer to the index of an element of a list.