List
External
Internal
Overview
A list is an implementation of a dynamic set.
Linked Lists
A linked list is a data structure implementing a dynamic set in which the elements are arranged in a linear order. The order is determined by pointers maintained by elements to other elements in the list. All dictionary operations (INSERT, DELETE, SEARCH) can be implemented for a list.
A simply linked list has elements that maintain a next pointer to the next element in the list. The last element's next pointer contains NULL. A doubly linked list has elements that maintain a next pointer to successor in the list and a prev pointer to the predecessor in the list.
The first element of a list is called head and the last element is called tail. For a doubly linked list, the head.prev is NULL, and for all linked lists, tail.next is NULL.
A list is said to be sorted if the linear order of the list corresponds to the linear order of keys stored in the elements of the list. A circular list is a list whose head's prev pointer points to the tail, and the tail's next pointer points to the head.
List Operations
CLRS page 237.
Array List
Lists in Java
public interface List<E> extends Collection<E> {
int size();
boolean isEmpty();
boolean contains(Object o);
boolean add(E e);
boolean remove(Object o);
// ...
default void sort(Comparator<? super E> c) {
...
}
void clear();
// ...
E get(int index);
E set(int index, E element);
void add(int index, E element);
E remove(int index);
int indexOf(Object o);
int lastIndexOf(Object o);
// ...
}