List Introduction - 列表简介

Made by Mike_Zhang

---

数据结构与算法主题：

---

1. Introduction to List

List is a more general Abstract Data Type than Stack and Queue mentioned before, which has more general method in adding or removing elements at arbitrary positions.

Locating an element is very important in linear data structure.

In Array, it is easy to locate with a integer index.

Index: for an element e, its index in a sequence is the number of elements before it in that sequence.

In LinkedList, it is not easy to locate an element with a integer index, since we have to traverse all elements before that element.

Based on index, Java has a more general interface, java.util.List.

---

2. List ADT

Some methods in java.util.List Interface:

• size(): Returns the number of elements in the list.
• isEmpty() : Returns true if the list contains no elements, false otherwise.
• get(i): Returns the element at the specified position in the list, error if the index is out of range.
• set(i,e): Replace the element at index i with e, return the old element in that position, error if the index is out of range.
• add(i,e): Inserts the element e at index i by moving all the elements after i one position to the right, error if the index is out of range.
• remove(i): Removes and return the element at index i by moving all the elements after i one position to the left, error if the index is out of range.

Notice:

• The index of an element may be changed after adding or removing an element.
• Adding and removing an element requires shifting the elements after the index.

Some List ADT Java implementations:

public interface List<E> {
    int size();
    boolean isEmpty();
    E get(int i) throws IndexOutOfBoundsException;
    E set(int i, E e) throws IndexOutOfBoundsException;
    void add(int i, E e) throws IndexOutOfBoundsException;
    E remove(int i) throws IndexOutOfBoundsException;
}

---

3. List Implementations

List ADT can be easily implemented by Array and optimized by Dynamic Array.

---

3.1 Array Implementation

Implementation in Array is a intuitive way for List implementation.

For method get(i) and set(i,e), they can be easily implemented by indexing the array, A[i].
However, for method add(i,e) and remove(i), we need to shift the elements after index i.

In above figure, (a) is the shifting process for adding an element into index i; (b) is the shifting process for removing an element from index i.

ArrayList Java implementation:

public class ArrayList<E> implements List<E> {
    private E[] data;
    private int size = 0;
    private static final int CAPACITY = 16; // default capacity 16

    public ArrayList() {
        this(CAPACITY);
    }
    public ArrayList(int capacity) {
        data = (E[]) new Object[capacity];
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public E get(int i) throws IndexOutOfBoundsException {
        checkIndex(i, size);
        return data[i];
    }

    public E set(int i, E e) throws IndexOutOfBoundsException {
        checkIndex(i, size);
        E temp = data[i];
        data[i] = e;
        return temp;
    }

    public void add(int i, E e) throws IndexOutOfBoundsException {
        checkIndex(i, size + 1);
        if (size == data.length) {
            throw new IllegalStateException("Array is full");
        }
        for (int j=size-1; j>=i; j--) {
            data[j + 1] = data[j];
        }
        data[i] = e;
        size++;
    }

    public E remove(int i) throws IndexOutOfBoundsException {
        checkIndex(i, size);
        E temp = data[i];
        for (int j = i; j < size - 1; j++) {
            data[j] = data[j + 1];
        }
        data[size] = null;
        size--;
        return temp;
    }

    private void checkIndex(int i, int n) throws IndexOutOfBoundsException {
        if (i < 0 || i >= n) {
            throw new IndexOutOfBoundsException("Illegal index: " + i);
        }
    }
}

ArrayList Performance:

Method	Running time
size()	$O(1)$
isEmpty()	$O(1)$
get(i)	$O(1)$
set(i,e)	$O(1)$
add(i,e)	$O(n)$
remove(i)	$O(n)$

Advantages:

• Easy to implement.
• Constant time in getting and setting elements due to direct access.

Drawbacks:

• More time required to add and remove elements. Because all element after the position need to be shifted. On average, $\frac{n}{2}$ elements need to be shifted, which results in the time complexity of $O(n)$.
• The maximum capacity of the ArrayList is fixed, which means that it cannot be resized.

In fact, Java’s ArrayList has no pre-requisite on the capacity, which is implemented by the dynamic array.

---

3.2 Dynamic Array Implementation

Dynamic Array is still implemented by the traditional array with fixed capacity but with some special strategies.

Key points:

1. Keep the internal array’s capacity greater than the current length of the array;
2. If the array is full, Java requires a new and larger array, and copy all elements into the new array for extension.
3. With enlarged ArrayList, more elements can be added.

So, the main step is to “enlarge” the array:

1. Create a new Array B with larger capacity (Step a);
2. Set $B[0,1,2,…,n]=A[0,1,2,…,n]$ where $n$ is the current length of the array A (Step b);
3. A = B, Array A is now the reference to the new larger array (Step c).

Some optimization of ArrayList with Dynamic Array:

// ...
// Dynamic Array Resizing
private void resize(int capacity) {
    E[] temp = (E[]) new Object[capacity];
    for (int i = 0; i < size; i++) {
        temp[i] = data[i];
    }
    data = temp;
}
// ...
public void add(int i, E e) throws IndexOutOfBoundsException {
    checkIndex(i, size + 1);
    if (size == data.length) {
        // throw new IllegalStateException("Array is full");
        resize(2 * data.length); // Dynamic Array Resizing without throwing exception
    }
    for (int j=size-1; j>=i; j--) {
        data[j + 1] = data[j];
    }
    data[i] = e;
    size++;
}
// ...

With the help of Dynamic Array, the List capacity will not be limited. However, user can also set a proper capacity in the constructor, which can improve the performance due to less resizing time.

---

4. Introduction to Positional List

There are two problems in traditional linear data structures:

1. Numeric indices are not good for linked list because it need to traverse all elements from the beginning to that index, which is expensive.
2. Index may be changed due to the insertion or deletion of elements.

The solution is the positional list, which can easily refer to any element in the sequence, as well as perform arbitrary insertions and deletions in $O(1)$.

Actually, the similar ADT is DoublyLinkedList, where all element are stored in the node who indicates element’s position. However, the Node field is private, which cannot be accessed by the user directly.

The solution is to create our own “Node” which is the Position.

---

5. Position ADT

Position ADT offers a more general way to describe the location of an element in the sequence. The association between the element and its position is immutable.

Position Interface only contains one method:

public interface Position<E> {
    E getElement() throws IllegalStateException;
}

---

6. Positional List ADT

Positional List is a collection of Positions.

Methods defined in Positional List:

• first(): Return the position of the first element in the List, or null if the List is empty;
• last(): Return the position of the last element in the List, or null if the List is empty;
• before(p): Return the position of the element immediately before the position p, or null if p is the first position;
• after(p): Return the position of the element immediately after the position p, or null if p is the last position;
• isEmpty(): Return true if the List is empty, otherwise false;
• size(): Return the number of elements in the List;
• addFirst(e): Insert an element to the front of the List, return the position of the new element;
• addLast(e): Insert an element to the end of the List, return the position of the new element;
• addBefore(p, e): Insert an element before the position p, return the position of the new element;
• addAfter(p, e): Insert an element after the position p, return the position of the new element;
• set(p, e): Replace the element at the position p with e, return the element previously at p;
• remove(p): Remove and return the element at the position p, invalidating position p;

Notice: “Return the position” means the position instance is returned, not the element inside.

PositionalList Java Interface:

public interface PositionList<E> {
    int size();
    boolean isEmpty();
    Position<E> first();
    Position<E> last();
    Position<E> before(Position<E> p) throws IllegalStateException;
    Position<E> after(Position<E> p) throws IllegalStateException;
    Position<E> addFirst(E e);
    Position<E> addLast(E e);
    Position<E> addBefore(Position<E> p, E e) throws IllegalArgumentException;
    Position<E> addAfter(Position<E> p, E e) throws IllegalArgumentException;
    E set(Position<E> p, E e) throws IllegalArgumentException;
    E remove(Position<E> p) throws IllegalArgumentException;
}

---

7. Positional List Implementations

Positional List can be implemented by Doubly Linked List and pure Array.

---

7.1 Doubly Linked List Implementation

It is intuitive that the Doubly Linked List is used to implement PositionalList.

The Node reference in Doubly Linked List can be seen as the Position of the element.

However, the Node reference is private in Doubly Linked List, which cannot be accessed by the user directly. We need to design our own Node who implements Position.

Positional List Java Implementation:

public class LinkedPositionalList<E> implements PositionList<E> {

    // Nested Node Class to implement position
    private static class Node<E> implements Position<E> {
        private E element;
        private Node<E> prev;
        private Node<E> next;
        public Node(E e, Node<E> p, Node<E> n) {
            element = e;
            prev = p;
            next = n;
        }
        public E getElement() throws IllegalStateException {
            if (next == null) {
                throw new IllegalStateException("Position no longer valid");
            }
            return element;
        }
        public Node<E> getPrev() {
            return prev;
        }
        public Node<E> getNext() {
            return next;
        }
        public void setPrev(Node<E> p) {
            prev = p;
        }
        public void setNext(Node<E> n) {
            next = n;
        }
        public void setElement(E e) {
            element = e;
        }
    }

    private Node<E> header;
    private Node<E> trailer;
    private int size = 0;

    public LinkedPositionalList() {
        header = new Node<E>(null, null, null);
        trailer = new Node<E>(null, header, null);
        header.setNext(trailer);
    }

    // Implicitly cast Position parameter instance to a Node instance
    // while check the position is invalid or not.
    private Node<E> validate(Position<E> p) throws IllegalArgumentException {
        if (!(p instanceof Node)) {
            throw new IllegalArgumentException("Invalid position");
        }
        Node<E> node = (Node<E>) p; // safe cast !!!
        if (node.getNext() == null) {
            throw new IllegalArgumentException("Position no longer in the list");
        }
        return node;
    }

    // Return a Position to the user from Node
    // while hide the header and trailer sentinel nodes from the user.
    private Position<E> position(Node<E> node) {
        if (node == header || node == trailer) {
            return null; // Keep sentinel node unseen by users
        }
        return node;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public Position<E> first() {
        return position(header.getNext());
    }

    public Position<E> last() {
        return position(trailer.getPrev());
    }

    public Position<E> before(Position<E> p) throws IllegalArgumentException {
        Node<E> node = validate(p);
        return position(node.getPrev());
    }

    public Position<E> after(Position<E> p) throws IllegalArgumentException {
        Node<E> node = validate(p);
        return position(node.getNext());
    }

    // Keep addBetween() method private to prevent client from calling it directly, it is a dangerous operation!!!
    // As well as unify the implementation of insertion methods
    private Position<E> addBetween(E e, Node<E> before, Node<E> after) {
        Node<E> node = new Node<E>(e, before, after);
        before.setNext(node);
        after.setPrev(node);
        size++;
        return node;
    }

    public Position<E> addFirst(E e) {
        return addBetween(e, header, header.getNext());
    }

    public Position<E> addLast(E e) {
        return addBetween(e, trailer.getPrev(), trailer);
    }

    public Position<E> addBefore(Position<E> p, E e) throws IllegalArgumentException {
        Node<E> node = validate(p);
        return addBetween(e, node.getPrev(), node);
    }

    public Position<E> addAfter(Position<E> p, E e) throws IllegalArgumentException {
        Node<E> node = validate(p);
        return addBetween(e, node, node.getNext());
    }

    public E set(Position<E> p, E e) throws IllegalArgumentException {
        Node<E> node = validate(p);
        E ele = node.getElement();
        node.setElement(e);
        return ele;
    }

    public E remove(Position<E> p) throws IllegalArgumentException {
        Node<E> node = validate(p);
        Node<E> before = node.getPrev();
        Node<E> after = node.getNext();
        before.setNext(after);
        after.setPrev(before);
        size--;
        E ele = node.getElement();
        node.setElement(null); // GC
        node.setPrev(null); // GC
        node.setNext(null); // GC
        return ele;
    }

    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("Header -> ");
        Position<E> p = first();
        while (p != null) {
            sb.append(p.getElement());
            p = after(p);
            if (p != null) {
                sb.append(", ");
            }
        }
        sb.append(" <- Trailer");
        return sb.toString();
    }
}

Test:

public static void main(String[] args) {
    LinkedPositionalList<Integer> list = new LinkedPositionalList<Integer>();
    Position<Integer> p1 = list.addFirst(1);
    Position<Integer> p2 = list.addAfter(p1, 2);
    Position<Integer> p3 = list.addAfter(p2, 3);
    System.out.println(list.toString());
    System.out.println(list.size());
    System.out.println(list.isEmpty());
    System.out.println(list.first().getElement());
    System.out.println(list.last().getElement());
    System.out.println(list.before(p3).getElement());
    System.out.println(list.after(p1).getElement());
    Position<Integer> p5 = list.addLast(5);
    System.out.println(list.toString());
    list.addBefore(p5, 4);
    System.out.println(list.toString());
    list.set(p5, 6);
    System.out.println(list.toString());
    list.remove(p3);
    System.out.println(list.toString());
}

Output:

Header -> 1, 2, 3 <- Trailer
3
false
1
3
2
2
Header -> 1, 2, 3, 5 <- Trailer
Header -> 1, 2, 3, 4, 5 <- Trailer
Header -> 1, 2, 3, 4, 6 <- Trailer
Header -> 1, 2, 4, 6 <- Trailer

Performance:

With the help of DoublyLinkedList, all methods in Positional List ADT run in $O(1)$ time in LinkedPositionalList.

---

7.2 Array Implementation

Since pure Array uses index for position, we have to store the block of [index, element] inside to store the Position objects.

• When inserting and deleting elements, we have to update all shifted positions inside the block iteratively.
• Comparing with the Positional List, array implementation is slower due to shifting takes $O(n)$ time.

---

References

Goodrich, M., Tamassia, R., & O’reilly, A. (2014). Data Structures and Algorithms in Java, 6th Edition. John Wiley & Sons.

---

写在最后

List 相关的知识会继续学习，继续更新.
最后，希望大家一起交流，分享，指出问题，谢谢！

---

原创文章，转载请标明出处
Made by Mike_Zhang

感谢你的支持