Dynamic arrays and linked lists #
Dynamic array #
A dynamic array is typically used to implement the abstract data type list.
Structure #
A dynamic array stores the elements of a list in a regular array $A$, and keeps track of the size of the list. If the size of the list exceeds the capacity of $A$, then the content of $A$ is copied into a larger array $A’$, and $A$ is replaced with $A’$.
Alternative structure: array deque #
An array deque is a variant of a dynamic array that allows the list to be extended in both directions. The array is initially populated from its middle index.
In addition to a list, an array dequeue is commonly used to implement a queue and/or a stack.
in Java #
The class ArrayList implements the interface List as a (regular) dynamic array.
The class ArrayDeque implements the interfaces Queue and Deque as an array deque.
Linked list #
A linked list is a sequence of nodes, where each node (except for the last) points to its successor. A linked list maintains a pointer to its first node, called its head.
Example.
In addition to a list, a linked list is often used to implement a stack.
Doubly linked list #
A doubly linked list is a linked list where each node points in addition to its predecessor (if any). A doubly linked list maintains a pointer to its head and a pointer to its last node.
In addition to a list and/or a stack, a doubly linked list is often used to implement a queue.
in Java #
The class LinkedList implements the interfaces List and Deque as a double linked list.
Performance #
Determine the worst case running time of the following operations on a list, stack and/or queue, if the underlying data structure is:
- a (large enough) dynamic array
- a linked list
- a doubly-linked list
-
as a function of $i$:
- read or modify the value at position $i$
-
as a function of the size $n$ of the list:
- add an element at the beginning of the list
- add an element at the end of the list
- remove the element at position $i$
- remove the first element of the list
- remove the last element of the list
-
as a function of the cumulated size $n$ of the two lists:
- concatenate two lists
| problem | dynamic array | linked list | doubly linked list |
|---|---|---|---|
| read or modify the value at position $i$ | $\Theta(1)$ | $\Theta(i)$ | $\Theta(i)$ |
| add an element at the beginning of the list | $\Theta(n)$ | $\Theta(1)$ | $\Theta(1)$ |
| add an element at the end of the list | $\Theta(1)$ | $\Theta(n)$ | $\Theta(n)$ |
| remove the element at position $i$ | $\Theta(n)$ | $\Theta(n)$ | $\Theta(n)$ |
| remove the first element of the list | $\Theta(n)$ | $\Theta(1)$ | $\Theta(1)$ |
| remove the last element of the list | $\Theta(1)$ | $\Theta(n)$ | $\Theta(1)$ |
| concatenate two lists | $\Theta(n)$ | $\Theta(n)$ | $\Theta(1)$ |
Locality #
Besides constant time reading and writing, another benefit or arrays (ignored in the standard RAM model) is contiguity in memory. Iterating over an array can be more efficient than iterating over a linked list, because it benefits from caching.