Java Fundamentals (Part 4)

/**
 * A dynamic array implementation of the List interface.
 *
 * @param <E> the type of elements in this list
 */
public class ArrayList<E> implements List<E> {
    private E[] elements;
    private int size;
    private int capacity;

    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList(){
        size = 0;
        capacity = 10;
        elements = (E[]) new Object[capacity];
    }

    /**
     * Appends the specified element to the end of this list.
     *
     * @param e element to be appended to this list
     */
    public void add(E e){
        if(size == capacity){
            ensureCapacity();
        }
        elements[size++] = e;
    }

    /**
     * Returns the element at the specified position in this list.
     *
     * @param index index of the element to return
     * @return the element at the specified position
     * @throws IndexOutOfBoundsException if the index is out of range
     */
    public E get(int index){
        if(index < 0 || index >= size){
            throw new IndexOutOfBoundsException();
        }
        return elements[index];
    }

    /**
     * Removes the element at the specified position in this list.
     *
     * @param index the index of the element to be removed
     * @return the element previously at the specified position
     * @throws IndexOutOfBoundsException if the index is out of range
     */
    public E remove(int index){
        if(index < 0 || index >= size){
            throw new IndexOutOfBoundsException();
        }
        E removedElement = elements[index];
        for(int i=index; i<size-1; i++){
            elements[i] = elements[i+1];
        }
        size--;
        return removedElement;
    }

    /**
     * Returns the number of elements in this list.
     *
     * @return the number of elements in this list
     */
    public int size(){
        return size;
    }

    /**
     * Increases the capacity of the array if necessary to ensure that it can hold at least the number of elements specified by the minimum capacity argument.
     */
    private void ensureCapacity(){
        int newCapacity = capacity * 2;
        E[] newElements = (E[]) new Object[newCapacity];
        for(int i=0; i<size; i++){
            newElements[i] = elements[i];
        }
        elements = newElements;
        capacity = newCapacity;
    }
}

/**
 * A doubly-linked list implementation.
 *
 * @param <E> the type of elements in this list
 */
public class LinkedList<E>{
    private static class Node<E> {
        E element;
        Node<E> next;
        Node<E> previous;

        Node(E element, Node<E> next, Node<E> previous){
            this.element = element;
            this.next = next;
            this.previous = previous;
        }
    }

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

    /**
     * Constructs an empty list.
     */
    public LinkedList(){
        header = new Node<E>(null, null, null);
        header.next = header;
        header.previous = header;
    }

    /**
     * Appends the specified element to the end of this list.
     *
     * @param e element to be appended to this list
     */
    public void add(E e){
        Node<E> newNode = new Node<>(e, header, header.previous);
        header.previous.next = newNode;
        header.previous = newNode;
        size++;
    }

    /**
     * Returns the element at the specified position in this list.
     *
     * @param index index of the element to return
     * @return the element at the specified position
     * @throws IndexOutOfBoundsException if the index is out of range
     */
    public E get(int index){
        if(index < 0 || index >= size){
            throw new IndexOutOfBoundsException();
        }
        Node<E> current = header.next;
        for(int i=0; i<index; i++){
            current = current.next;
        }
        return current.element;
    }

    /**
     * Removes the element at the specified position in this list.
     *
     * @param index the index of the element to be removed
     * @return the element previously at the specified position
     * @throws IndexOutOfBoundsException if the index is out of range
     */
    public E remove(int index){
        if(index < 0 || index >= size){
            throw new IndexOutOfBoundsException();
        }
        Node<E> current = header.next;
        for(int i=0; i<index; i++){
            current = current.next;
        }
        current.previous.next = current.next;
        current.next.previous = current.previous;
        size--;
        return current.element;
    }

    /**
     * Returns the number of elements in this list.
     *
     * @return the number of elements in this list
     */
    public int size(){
        return size;
    }
}

@article{nguyen2023java4,
  title   = "Java Fundamentals (Part 4)",
  author  = "Nguyen, Minh",
  journal = "mnguyen0226.github.io",
  year    = "2023",
  month   = "October",
  url     = "https://mnguyen0226.github.io/posts/java_fundamentals_4/post/"
}