3. Lists

A list organizes data in a collection of items, think of a regular array, but with more options that are abstracted away from the developer.

Abstract Data Type: List

Data:

• A collection of objects in a specific order and having the same data type.
• The number of objects in the collection.

Pseudocode	UML	Description
add(entry)	+add(entry: T): void	Adds a new entry to the end of the list.
add(position, entry)	+add(position: integer, entry: T): void	Adds a new entry at a specific position.
remove(position)	+remove(position: integer): T	Removes an entry at a position and returns it.
clear()	+clear(): void	Removes all entries from the list.
set(position, entry)	+set(position: integer, entry: T): T	Replaces the entry at position with the new entry.
get(position)	+get(position: integer): T	Returns the entry at position.
toArray()	+toArray: T[]	Returns an array of the list.
contains(entry)	+contains(entry: T): boolean	Checks if list contains entry.
length()	+length(): integer	Returns the length of the list.
isEmpty()	+isEmpty(): boolean	Dectects whether the list is empty.

Interface of the ADT List

public interface ListInterface<T> {
    /** Adds a new entry to the end of this list. Entries currently in the list are unaffected. The list's size is increased by 1.
    @param entry The object to be added as a new entry. */
    public void add(T entry);

    /** Adds a new entry at a specified position within this list. Entries originally at and above the specified position are at the next higher position within the list. The list's size is increased by 1.
    @param position An integer that specifies the desired position of the new entry.
    @param entry The object to be added as a new entry.
    @throws IndexOutOfBoundsException if either position < 0 or position > getLength() + 1. */
    public void add(int position, T entry);

    /** Removes the entry at a given position from this list. Entries originally at positions higher than the given position are at the next lower position within the list, and the list's size is decreased by 1.
    @param position An integer that indicates the position the entry to be removed.
    @return A reference to the removed entry.
    @throws IndexOutOfBoundsException if either position < 0 or position > getLength(). */
    public T remove(int position);

    /** Removes all entries from this list. */
    public void clear();

    /** Replaces the entry at a given position in this list.
    @param position An integer that indicates the position the entry to be replaced.
    @param entry The object that will replace the entry at the position position.
    @return The original entry that was replaced.
    @throws IndexOutOfBoundsException if either position < 0 or position > getLength(). */
    public T set(int position, T entry);

    /** Retrieves the entry at a given position in this list.
    @param position An integer that indicates the position of the desired entry.
    @return A reference to the indicated entry.
    @throws IndexOutOfBoundsException if either position < 0 or position > getLength(). */
    public T get(int position);

    /** Retrieves all entries that are in this list in the order in which they occur in the list.
    @return A newly allocated array of all the entries in the list. If the list is empty, the returned array is empty. */
    public T[] toArray();

    /** Sees whether this list contains a given entry.
    @param entry The object that is the desired entry.
    @return True if the list contains entry, or false if not. */
    public boolean contains(T entry);

    /** Gets the length of this list.
    @return The integer number of entries currently in the list. */
    public int length();

    /** Sees whether this list is empty.
    @return True if the list is empty, or false if not. */
    public boolean isEmpty();
}

An Array-Based Implementation

The most obvious way to implement the list ADT is through an array, so let's do that.

public class ArrayList<T> implements ListInterface<T> {
    private T[] array;
    private int length;
    private int capacity;

    public ArrayList() {
        this(256);
    }

    public ArrayList(int capacity) {
        this.capacity = capacity;
        this.array = (T[]) new Object[capacity];
    }

    public void add(T entry) {
        if (length + 1 >= capacity)
            ensureCapacity();
        array[length++] = entry;
    }

    public void add(int position, T entry) {
        if (position < 0 || position > length + 1)
            throw new IndexOutOfBoundsException();
        if (length == 0) {
            array[length] = entry;
        } else {
            for (int i = length - 1; i >= position; i--) {
                array[i + 1] = array[i];
            }
            array[position] = entry;
        }
        length++;
        ensureCapacity();
    }

    public T remove(int position) {
        if (position < 0 || position > length)
            throw new IndexOutOfBoundsException();
        T element = array[position];
        for (int i = position; i < length; i++) {
            array[i] = array[i + 1];
        }
        length--;
        return element;
    }

    public void clear() {
        this.array = (T[]) new Object[capacity];
        this.length = 0;
    }

    public T set(int position, T entry) {
        if (position < 0 || position > length)
            throw new IndexOutOfBoundsException();
        T element = array[position];
        array[position] = entry;
        return element;
    }

    public T get(int position) {
        if (position < 0 || position > length)
            throw new IndexOutOfBoundsException();
        return array[position];
    }

    public T[] toArray() {
        T[] result = (T[]) new Object[length];
        for (int i = 0; i < length; i++) {
            result[i] = array[i];
        }
        return result;
    }

    public boolean contains(T entry) {
        for (int i = 0; i < length; i++) {
            if (array[i].equals(entry)) {
                return true;
            }
        }
        return false;
    }

    public int length() {
        return length;
    }

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

    private void ensureCapacity() {
        if (length == capacity) {
            this.capacity *= 2;
            T[] newArray = (T[]) new Object[this.capacity];
            for (int i = 0; i < length; i++) {
                newArray[i] = array[i];
            }
            this.array = newArray;
        }
    }
}

A Linked-Based Implementation

A less-so obvious way to implement the list ADT is through linked data. Each piece of data has a node which are linked in some way.

public class LinkedList<T> implements ListInterface<T> {
    private Node first;
    private Node last;
    private int length;

    public LinkedList() {
        this.first = null;
        this.last = null;
    }

    public void add(T entry) {
        if (last == null) {
            first = new Node(entry);
            last = first;
        } else {
            last.next = new Node(entry);
            last = last.next;
        }
        length++;
    }

    public void add(int position, T entry) {
        if (position < 0 || position > length + 1) throw new IndexOutOfBoundsException();

        if (first == null && last == null && position == 0) {
            first = new Node(entry);
            last = first;
        } else if (first.equals(last)) {
            if(position == 0) {
                first = new Node(entry, first.next);
            } else {
                first.next = new Node(entry, null);
                last = first.next;
            }
        } else {
            Node curr = first;
            while(position-- > 1) {
                curr = curr.next;
            }
            Node newNode;
            if (curr.next == null) {
                newNode = new Node(entry, null);
                last = newNode;
            } else {
                newNode = new Node(entry, curr.next);
            }
            curr.next = newNode;
        }
        length++;
    }

    public T remove(int position) {
        if (position < 0 || position > length) throw new IndexOutOfBoundsException();
        T removed;
        if (first.equals(last)) {
            removed = first.data;
            first = null;
            last = null;
        } else {
            Node curr = first;
            int i = position;
            while(i-- > 1) {
                curr = curr.next;
            }
            removed = curr.data;
            if (position == 0) {
                this.first = curr.next;
            }
            if (position + 1 == length) {
                this.last = curr;
                curr.next = null;
            } else {
                curr.next = curr.next.next;
            }
        }

        length--;
        return removed;
    }

    public void clear() {
        this.first = null;
        this.last = null;
        length = 0;
    }

    public T set(int position, T entry) {
        if (position < 0 || position > length) throw new IndexOutOfBoundsException();
        Node curr = first;
        while(position-- > 0) {
            curr = curr.next;
        }
        T oldData = curr.data;
        curr.data = entry;
        return oldData;
    }

    public T get(int position) {
        if (position < 0 || position > length) throw new IndexOutOfBoundsException();
        Node curr = first;
        while(position-- > 0) {
            curr = curr.next;
        }
        return curr.data;
    }

    public T[] toArray() {
        T[] result = (T[]) new Object[length];
        Node curr = first;
        int i = 0;
        while(curr != null) {
            result[i++] = curr.data;
            curr = curr.next;
        }
        return result;
    }

    public boolean contains(T entry) {
        Node curr = first;
        for (int i = 0; i < length; i++) {
            if (curr.next.equals(entry)) {
                return true;
            }
        }
        return false;
    }

    public int length() {
        return length;
    }

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

    private class Node {
        T data;
        Node next;

        public Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }

        public Node(T data) {
            this(data, null);
        }
    }
}

The example above uses a singely linked-list, however, you can also achieve the same implementation with some trade-offs (less time complexity and more space complexity) with a doubely linked-list.

public class LinkedList<T> implements ListInterface<T> {
    // ... other required functions

    private class Node {
        T data;
        Node next;
        Node prev;

        public Node(T data, Node prev, Node next) {
            this.data = data;
            this.prev = prev;
            this.next = next;
        }

        public Node(T data) {
            this(data, null, null);
        }
    }
}

Linked-Based vs. Array-Based

So, what is the difference between the linked and array based implementations? Well, the time complexity of each method slightly differs with specific benefits and drawbacks for each. Below is a simple summary of each implementation.

Operation	Array	Linked
add(entry)	$O(1)$, if resized $O(n)$	$O(1)$
add(position, entry)	$O(n)$	$O(n)$
remove(position)	$O(n)$	$O(n)$
clear()	$O(1)$	$O(1)$
set(position, entry)	$O(1)$	$O(n)$
get(position)	$O(1)$	$O(n)$
toArray()	$O(n)$	$O(n)$
contains(entry)	$O(n)$	$O(n)$
length()	$O(1)$	$O(1)$
isEmpty()	$O(1)$	$O(1)$

Iterator Method

Problem: different implementations have different ways of accessing elements which is a problem when creating custom methods with the list ADT.

Solution: create a seperate interator class that standardizes the process of interation.

public interface Iterator<E> {
    /** Checks whether there is a next.
    @return True if there is a next element, or false if not. */
    public boolean hasNext();

    /** Retrieves the next element.
    @return returns the next element's data */
    public E next();
}

So, how do we use this interator interface? Well, we will create a new ListIterator class that a method in the List can call and return. Below are two implementations of Linked and Array based interators.

Linked-Based

public class LinkedList<T> implements ListInterface<T> {
    // ... all of the other methods and constructors

    public Iterator iterator() {
        return new LinkedListIterator(this);
    }

    private class LinkedListIterator implements Iterator {
        LinkedList<T> list;
        Node curr;

        public LinkedListIterator(LinkedList<T> list) {
            this.list = list;
            this.curr = list.first;
        }

        public boolean hasNext() {
            return curr != null;
        }

        public T next() {
            T result = curr.data;
            curr = curr.next;
            return result;
        }
    }
}

Array-Based

public class ArrayList<T> implements ListInterface<T> {
    // ... all of the other methods and constructors

    public Iterator iterator() {
        return new ArrayListIterator(this);
    }

    private class ArrayListIterator implements Iterator {
        ArrayList<T> list;
        int currentIndex;

        public ArrayListIterator(ArrayList<T> list) {
            this.list = list;
            this.currentIndex = 0;
        }

        public boolean hasNext() {
            return this.currentIndex < list.length();
        }

        public T next() {
            return list.get(this.currentIndex++);
        }
    }
}

Next Page →