<<数据结构-Java描述>>之数组线性表

参考代码: <<Java语言程序设计与数据结构>> 机械工业出版社 梁勇著 P147-155

实现结构

java.util.Iterable (顶层)

• <<interface>> java.util.Collection (extends)

  • <<interface>> MyList (extends)

    • 重写

      Collection中定义的 add、isEmpty、remove、containsAll、addAll、
      removeAll、retainAll、toArray()和toArray(T[ ])方法

    • 添加

      add()、get()、indexOf()、lastIndexOf()、remove()和set()方法

    • MyArrayList (implements)

      • 重写

        Object类中的 toString()方法

        Collection接口中的 contains()、clear()、size()方法

        MyList接口中的 add()、get()、seindexOf()、lastIndexOf()、remove()和set()方法

        Iterable接口中的 iterator()方法

        用一个实现于Iterator的类, 重写Iterator接口中的 hasNext()、next()和remove()方法

      • 添加

        trimToSize()、ensureCapacity()、checkIndex()方法

MyList.java

package data_structures.linearlist;

import java.util.Collection;

public interface MyList<E> extends Collection<E> {
  /** Add a new element at the specified index in this list */
  public void add(int index, E e);

  /** Return the element from this list at the specified index */
  public E get(int index);

  /** Return the index of the first matching element in this list.
   *  Return -1 if no match. */
  public int indexOf(Object e);

  /** Return the index of the last matching element in this list
   *  Return -1 if no match. */
  public int lastIndexOf(E e);

  /** Remove the element at the specified position in this list
   *  Shift any subsequent elements to the left.
   *  Return the element that was removed from the list. */
  public E remove(int index);

  /** Replace the element at the specified position in this list
   *  with the specified element and returns the new set. */
  public E set(int index, E e);

  @Override /** Add a new element at the end of this list */
  public default boolean add(E e) {
    add(size(), e);
    return true;
  }

  @Override /** Return true if this list contains no elements */
  public default boolean isEmpty() {
    return size() == 0;
  }

  @Override /** Remove the first occurrence of the element e 
   *  from this list. Shift any subsequent elements to the left.
   *  Return true if the element is removed. */
  public default boolean remove(Object e) {
    if (indexOf(e) >= 0) {
      remove(indexOf(e));
      return true;
    }
    else
      return false;
  }

  @Override
  public default boolean containsAll(Collection<?> c) {
    for (Object e: c)
      if (!this.contains(e))
        return false;

    return true;
  }

  /** Adds the elements in otherList to this list.
   * Returns true if this list changed as a result of the call */
  @Override
  public default boolean addAll(Collection<? extends E> c) {
    for (E e: c)
      this.add(e);

    return c.size() > 0;
  }

  /** Removes all the elements in otherList from this list
   * Returns true if this list changed as a result of the call */
  @Override
  public default boolean removeAll(Collection<?> c) {
    boolean changed = false;
    for (Object e: c) {
      if (remove(e))
        changed = true;
    }

    return changed;
  }

  /** Retains the elements in this list that are also in otherList
   * Returns true if this list changed as a result of the call */
  @Override
  public default boolean retainAll(Collection<?> c) {
    boolean changed = false;
    for (int i = 0; i < this.size(); ) {
      if (!c.contains(this.get(i))) {
        this.remove(get(i));
        changed = true;
      }
      else
        i++;
    }

    return changed;
  }

  @Override
  public default Object[] toArray() {
    // Left as an exercise
    Object[] result = new Object[size()];
    for (int i = 0; i < size(); i++) {
      result[i] = this.get(i);
    }
    return result;
  }

  @Override
  public default <T> T[] toArray(T[] a) {
    // Left as an exercise
    for (int i = 0; i < size(); i++) {
      a[i] = (T)this.get(i);
    }
    return a;
  }
}

MyArrayList.java

package data_structures.linearlist;

public class MyArrayList<E> implements MyList<E> {
  public static final int INITIAL_CAPACITY = 16;
  private E[] data = (E[])new Object[INITIAL_CAPACITY];
  private int size = 0; // Number of elements in the list

  /** Create an empty list */
  public MyArrayList() {
  }

  /** Create a list from an array of objects */
  public MyArrayList(E[] objects) {
    for (int i = 0; i < objects.length; i++)
      add(objects[i]); // Warning: don’t use super(objects)! 
  }

  @Override /** Add a new element at the specified index */
  public void add(int index, E e) {   
    // Ensure the index is in the right range
    if (index < 0 || index > size)
      throw new IndexOutOfBoundsException
        ("Index: " + index + ", Size: " + size);

    ensureCapacity();

    // Move the elements to the right after the specified index
    for (int i = size - 1; i >= index; i--)
      data[i + 1] = data[i];

    // Insert new element to data[index]
    data[index] = e;

    // Increase size by 1
    size++;
  }

  /** Create a new larger array, double the current size + 1 */
  private void ensureCapacity() {
    if (size >= data.length) {
      E[] newData = (E[])(new Object[size * 2 + 1]);
      System.arraycopy(data, 0, newData, 0, size);
      data = newData;
    }
  }

  @Override /** Clear the list */
  public void clear() {
    data = (E[])new Object[INITIAL_CAPACITY];
    size = 0;
  }

  @Override /** Return true if this list contains the element */
  public boolean contains(Object e) {
    for (int i = 0; i < size; i++)
      if (e.equals(data[i])) return true;

    return false;
  }

  @Override /** Return the element at the specified index */
  public E get(int index) {
    checkIndex(index);
    return data[index];
  }

  private void checkIndex(int index) {
    if (index < 0 || index >= size)
      throw new IndexOutOfBoundsException
        ("Index: " + index + ", Size: " + size);
  }

  @Override /** Return the index of the first matching element 
   *  in this list. Return -1 if no match. */
  public int indexOf(Object e) {
    for (int i = 0; i < size; i++)
      if (e.equals(data[i])) return i;

    return -1;
  }

  @Override /** Return the index of the last matching element 
   *  in this list. Return -1 if no match. */
  public int lastIndexOf(E e) {
    for (int i = size - 1; i >= 0; i--)
      if (e.equals(data[i])) return i;

    return -1;
  }

  @Override /** Remove the element at the specified position 
   *  in this list. Shift any subsequent elements to the left.
   *  Return the element that was removed from the list. */
  public E remove(int index) {
    checkIndex(index);

    E e = data[index];

    // Shift data to the left
    for (int j = index; j < size - 1; j++)
      data[j] = data[j + 1];

    data[size - 1] = null; // This element is now null

    // Decrement size
    size--;

    return e;
  }

  @Override /** Replace the element at the specified position 
   *  in this list with the specified element. */
  public E set(int index, E e) {
    checkIndex(index);
    E old = data[index];
    data[index] = e;
    return old;
  }

  @Override
  public String toString() {
    StringBuilder result = new StringBuilder("[");

    for (int i = 0; i < size; i++) {
      result.append(data[i]);
      if (i < size - 1) result.append(", ");
    }

    return result.toString() + "]";
  }

  /** Trims the capacity to current size */
  public void trimToSize() {
    if (size != data.length) { 
      E[] newData = (E[])(new Object[size]);
      System.arraycopy(data, 0, newData, 0, size);
      data = newData;
    } // If size == capacity, no need to trim
  }

  @Override /** Override iterator() defined in Iterable */
  public java.util.Iterator<E> iterator() {
    return new ArrayListIterator();
  }

  private class ArrayListIterator 
      implements java.util.Iterator<E> {
    private int current = 0; // Current index 

    @Override
    public boolean hasNext() {
      return current < size;
    }

    @Override
    public E next() {
      return data[current++];
    }

    @Override // Remove the element returned by the last next()
    public void remove() {
        if (current == 0) // next() has not been called yet
        throw new IllegalStateException(); 
      MyArrayList.this.remove(--current);
    }
  }

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

TestMyArrayList.java

package data_structures.linearlist;

public class TestMyArrayList {
  public static void main(String[] args) {
    // Create a list
    MyList<String> list = new MyArrayList<>();

    // Add elements to the list
    list.add("America"); // Add it to the list
    System.out.println("(1) " + list);

    list.add(0, "Canada"); // Add it to the beginning of the list
    System.out.println("(2) " + list);

    list.add("Russia"); // Add it to the end of the list
    System.out.println("(3) " + list);

    list.add("France"); // Add it to the end of the list
    System.out.println("(4) " + list);

    list.add(2, "Germany"); // Add it to the list at index 2
    System.out.println("(5) " + list);

    list.add(5, "Norway"); // Add it to the list at index 5
    System.out.println("(6) " + list);

    // Remove elements from the list
    list.remove("Canada"); // Same as list.remove(0) in this case
    System.out.println("(7) " + list);

    list.remove(2); // Remove the element at index 2
    System.out.println("(8) " + list);

    list.remove(list.size() - 1); // Remove the last element
    System.out.print("(9) " + list + "\n(10) ");

    for (String s: list)
      System.out.print(s.toUpperCase() + " ");
  }
}

输出结果

(1) [America]
(2) [Canada, America]
(3) [Canada, America, Russia]
(4) [Canada, America, Russia, France]
(5) [Canada, America, Germany, Russia, France]
(6) [Canada, America, Germany, Russia, France, Norway]
(7) [America, Germany, Russia, France, Norway]
(8) [America, Germany, France, Norway]
(9) [America, Germany, France]
(10) AMERICA GERMANY FRANCE 
Process finished with exit code 0