Java中ArrayList与顺序表的定义与实现方法

什么是ArrayList与顺序表

在Java中，ArrayList与顺序表都是线性表的数据结构。简单说，线性表就是元素排成线性关系的数据结构。

ArrayList是Java官方提供的动态数组类，其底层是使用数组实现的。因为其底层采用了数组存储数据的方式，所以在插入、删除等一些操作时可能需要大量的移动元素，所以在大规模的数据存取操作时效率会比较低。

顺序表也是动态数组的一种实现方式，与ArrayList不同的是，它以一个固定大小的数组存储线性表中的元素。因为其底层是使用数组实现的，所以在随机访问元素时效率会比较高。

ArrayList的定义与实现方法

定义

在Java中，我们只需要使用import java.util.ArrayList;语句导入java.util包中的ArrayList类即可使用。下面是一段ArrayList的简单定义：

import java.util.ArrayList;

public class Example {
  public static void main(String[] args) {
    ArrayList<String> list = new ArrayList<String>();
  }
}

实现方法

一、添加元素

我们可以通过add()方法或addAll()方法向ArrayList中添加元素，其中add()方法可以添加一个元素，addAll()方法可以添加多个元素。下面是一些添加元素的示例代码：

import java.util.ArrayList;

public class Example {
  public static void main(String[] args) {
    ArrayList<String> list = new ArrayList<String>();

    // 添加单个元素
    list.add("Hello");

    // 添加多个元素
    ArrayList<String> anotherList = new ArrayList<String>();
    anotherList.add("World");
    anotherList.add("!");
    list.addAll(anotherList);
  }
}

二、获取元素

ArrayList提供了多个获取元素的方法，比如get()方法可以获取指定下标的元素，subList()方法可以获取一段子元素列表。下面是一些获取元素的示例代码：

import java.util.ArrayList;

public class Example {
  public static void main(String[] args) {
    ArrayList<String> list = new ArrayList<String>();
    list.add("Hello");
    list.add("World");
    list.add("!");

    // 获取指定下标的元素
    String s = list.get(1);

    // 获取一段子元素列表
    ArrayList<String> subList = list.subList(0, 2);
  }
}

三、删除元素

我们可以使用remove()方法或removeAll()方法来删除ArrayList中的元素，其中remove()方法可以删除指定索引位置的元素，removeAll()方法可以删除一个ArrayList中与另一个ArrayList中相同元素。下面是一些删除元素的示例代码：

import java.util.ArrayList;

public class Example {
  public static void main(String[] args) {
    ArrayList<String> list = new ArrayList<String>();
    list.add("Hello");
    list.add("World");
    list.add("!");

    // 删除指定索引位置的元素
    list.remove(1);

    // 删除一个ArrayList中与另一个ArrayList中相同元素
    ArrayList<String> anotherList = new ArrayList<String>();
    anotherList.add("Hello");
    list.removeAll(anotherList);
  }
}

顺序表的定义与实现方法

定义

顺序表的定义需要我们手动实现类，这里我们以一个顺序表的简单示例代码来展示：

public class MyArrayList<T> {
  private Object[] data = null;
  private int size = 0;

  public MyArrayList() {
    this(10);
  }

  public MyArrayList(int initialCapacity) {
    if (initialCapacity < 0) {
      throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
    }
    this.data = new Object[initialCapacity];
  }

  public void add(T t) {
    if (size == data.length) {
      grow(size + 1);
    }

    data[size++] = t;
  }

  public T get(int index) {
    checkIndex(index);
    return (T) data[index];
  }

  public void remove(int index) {
    checkIndex(index);
    int numMoved = size - index - 1;
    if (numMoved > 0) {
      System.arraycopy(data, index + 1, data, index, numMoved);
    }
    data[--size] = null;
  }

  private void grow(int minCapacity) {
    int oldCapacity = data.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0) {
      newCapacity = minCapacity;
    }
    data = Arrays.copyOf(data, newCapacity);
  }

  private void checkIndex(int index) {
    if (index < 0 || index > (size - 1)) {
      throw new IndexOutOfBoundsException();
    }
  }
}

实现方法

顺序表的实现方法与ArrayList类似，我们也可以通过添加元素、获取元素、删除元素等操作来实现对顺序表的操作。下面是一些简单的示例代码：

public class Example {
  public static void main(String[] args) {
    MyArrayList<String> list = new MyArrayList<String>();
    list.add("Hello");
    list.add("World");
    list.add("!");

    // 获取指定下标的元素
    String s = list.get(1);

    // 删除指定索引位置的元素
    list.remove(1);
  }
}

总结

ArrayList与顺序表都是线性表数据结构的实现方式，在Java中，ArrayList提供了官方的实现类，其底层采用了数组存储数据的方式；而顺序表需要我们手动实现，其底层也是使用数组存储数据的方式。在实际使用过程中，我们可以根据具体需要来选择使用ArrayList或顺序表来实现对线性表的操作。