List

Internal

• Data Structures
• Mathematical List

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.

Lists in Java

https://docs.oracle.com/javase/10/docs/api/java/util/List.html

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);

    // ...

}