以线性排列的方式管理事物的集合,称为 “表” 也就是我们常说 List。表是一种基础的、也是最常用的数据结构。表通常可以使用数组或者链表进行实现,这两种实现方式也各有特点。

一、表(List)数据结构

1.1 表的数组实现

数组是一种固定容量的、通过下标访问元素的集合,是最基本的数据结构之一。表的所有操作都可以通过数组来实现。但是由于数组的容量固定,在使用数组时需要对表的大小进行估算。所以由数组实现的表还需要一种对数组进行扩容的方法:

int[] arr = new int[10];
...
// 下面对数组进行扩容(将数据复制到较大的新数组中)
int[] newArr = new int[arr.length * 2];
for (int i = 0; i < arr.length; i++){
newArr[i] = arr[i]
}
arr = newArr;

数组的实现通过下标访问元素,使得 findByIndex 操作在常数时间下完成。但是由于数组数据连续性的问题,在插入和删除操作上却要花费更多开销。在最坏的情况下,在数组的 0 位置进行插入元素,首先需要将整个数组向后移动一个位置将 0 位置空出来。而删除 0 位置的元素,需要将整个数组向前移动一个位置。因此,这两个操作在最坏的情况下需要线性的时间。如果对数组的最后的元素进行插入和删除操作,只需要常数时间。但是在平均来看,仍然需要线性的时间。

如果只对表的末端进行操作,且只使用下标进行元素访问,那么数组是一种很好的实现。

1.2 表的链表实现

链表是由一系列节点组成的集合,节点中包含了表元素以及后续节点组成的链。所以链表中的节点不必在内存中连续存储。

链表表示

public class Node<T>{
T item; // 节点存储的元素
Node<T> next; // 下一个节点
}

不需要在内存中连续存储的链表解决了数组中插入和删除操作高昂的开销。删除操作只需要修改 next 引用即可实现。插入操作只需要将前一个节点的 next 引用修改为新节点,将新节点的 next 引用指向后一个引用即可。但是,在链表的实现中,由于不能通过下标访问, findByIndex 操作不如数组实现的效率高,需要花费线性时间。

我们可以看到,在确定表需要变动的地方,那么链表实现的插入和删除不需要移动表元素,只需要常数时间。但是,如果需要删除链表中最后一个元素,删除操作也只需要常数时间,不过我们必须找到指向最后一个节点的节点,将它的 next 引用改为 null。这导致了我们必须花费时间去寻找指向最后一个节点的节点。以此类推,倒数第二、倒数第三 … 的元素也一样。为了减少这类操作的开销,我们通常会将链表设计成 “双链表”,双链表中的节点不仅会指向后一个节点,还会指向前一个节点。

二、表的数据模型设计

我们参考 Java 的集合框架,以此来设计表的数据模型 API。

2.1 Java Collections API

API 描述
int size() 返回集合中元素的个数
boolean isEmpty() 当集合大小为 0 时,返回 true
boolean contains(T item) 当 item 在集合中,返回 true
boolean add(T item) 添加元素。添加成功时,返回 true(如果集合不允许添加重复元素时,可能添加失败)
boolean remove(T item) 删除元素。删除成功时,返回 true(如果被删除的元素不存在,会导致删除失败)
Iterator<\T> iterator() 返回迭代器

2.2 Iterator 接口

API 描述
boolean hasNext() 返回集合是否存在下一元素
T next() 返回集合的下一元素
void remove() 删除当前元素

实现 Iterable 接口的集合类都需要实现一个返回 Iterator 迭代器的方法。实现 Iterable 接口的集合可以使用增强 for 循环。

for (T item : list){
...
}
// 上述代码等价于下方代码
Iterator<T> itr = list.iterator();
while(itr.hasNext()){
T item = itr.next();
...
}

另一个方面是,我们可以发现 Iterator 包含了 remove 方法。Iterator.remove 的优势在于,Collection.remove 方法必须首先找到被删除的元素。但是在迭代器中,remove 方法已经确定了被删除元素的准确位置,那么它的操作开销就小得多。对集合的删除操作,迭代器有着更高的效率。

2.3 List 接口

API 描述
T get(int index) 通过索引获取元素
T set(int index, T item) 通过索引修改元素的值
void add(int index, T item) 通过索引添加元素
void remove(int index) 通过索引删除元素

List 接口有两种流行的实现方法。ArrayList 提供了一种可增长数组的实现,使用 ArrayList 的优势在于 get 和 set 操作只需要花费常数时间。其缺点在于,除非对 ArrayList 末端操作,否则插入和删除操作都需要花费线性时间。LinkedList 这提供了双链表的实现,使用 LinkedList 的优势在于,对位置已知的元素进行插入和删除只需要花费常数时间。其缺点在于,它适合通索引进行访问,因此对 get 操作需要花费线性时间。

三、实现表数据模型

3.1 ArrayList 的实现

public class MyArrayList<T> implements Iterable<T> {

private static final int DEFAULT_CAPACITY = 10;
private T[] items;
private int size;

public MyArrayList(){
this(DEFAULT_CAPACITY);
}
public MyArrayList(int capacity) {
this.items = (T[]) new Object[capacity];
this.size = 0;
}

public int size(){
return size;
}

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

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

public boolean add(T item){
add(size(), item);
return true;
}

public void add(int index, T item){
if (items.length == size()){
ensureCapacity(size * 2);
}
// 元素向后移动
for (int i = size(); i > index; i--){
items[i] = items[i - 1];
}
items[index] = item;
size++;
}

public boolean remove(T item){
int index = -1;

for (int i = 0; i < size(); i++){
if (item.equals(items[i])){
index = i;
break;
}
}
if (index != -1){
remove(index);
return true;
}
return false;
}

public void remove(int index){
for (int i = index; i < items.length; i++){
items[i] = items[i + 1];
}
size--;
}

public void ensureCapacity(int capacity){
if (capacity < size) return;

T[] old = items;
items = (T[]) new Object[capacity];
for (int i = 0; i < capacity; i++){
items[i] = old[i];
}
}

public T get(int index){
if (index < 0 || index >= size()){
throw new ArrayIndexOutOfBoundsException();
}
return items[index];
}

public Iterator<T> iterator() {
return new ArrayListIterator();
}

private class ArrayListIterator implements Iterator<T>{

private int current = 0;

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

public T next() {
if (! hasNext()){
throw new NoSuchElementException();
}
return items[current++];
}

public void remove() {
MyArrayList.this.remove(--current);
}
}
}

3.2 LinkedList 的实现

public class MyLinkedList<T> implements Iterable<T> {

private int size;
private int modCount;
private final Node<T> startNode;
private final Node<T> endNode;

public MyLinkedList(){
this.startNode = new Node<T>(null, null, null);
this.endNode = new Node<T>(null, this.startNode, null);
this.startNode.next = this.endNode;

this.size = 0;
modCount++;
}

public int size(){
return size;
}

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

public boolean contains(T item){
Node<T> curr = startNode;
while (curr.next != null) {
curr = curr.next;
if (curr.data == item) return true;
}
return false;
}

public boolean add(T item) {
add(size(), item);
return true;
}

public void add(int index, T item){
addBefore(getNode(index, 0, size()), item);
}

private void addBefore(Node<T> node, T item){
Node<T> newNode = new Node<T>(item, node.prev, node);
newNode.prev.next = newNode;
node.prev = newNode;
size++;
modCount++;
}

public boolean remove(T item){
Node<T> curr = startNode;
while (curr.next != endNode){
curr = curr.next;
if (curr.data == item){
remove(curr);
return true;
}
}
return false;
}

public void remove(int index){
remove(getNode(index));
}

private void remove(Node<T> node){
node.prev.next = node.next;
node.next.prev = node.prev;
size--;
modCount++;
}

public Node<T> getNode(int index){
return getNode(index, 0, size() - 1);
}

public Node<T> getNode(int index, int lower, int upper){
Node<T> node;
if (index < lower || index > upper)
throw new IndexOutOfBoundsException();
if (index < size() / 2){
node = startNode.next;
for (int i = 0; i < index; i++){
node = node.next;
}
}else {
node = endNode;
for (int i = size(); i > index; i--){
node = node.prev;
}
}
return node;
}

public T get(int index){
return getNode(index).data;
}

public T set(int index, T item){
Node<T> node = getNode(index);
T oldValue = node.data;
node.data = item;
return oldValue;
}

public Iterator<T> iterator() {
return new LinkedListIterator();
}

public static class Node<T>{
public T data;
public Node<T> prev;
public Node<T> next;

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

public class LinkedListIterator implements Iterator<T>{

private Node<T> curr = startNode.next;
private int expectedModCount = modCount;
private boolean okToRemove = false;

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

public T next() {
if (modCount != expectedModCount){
throw new ConcurrentModificationException();
}
if (!hasNext()){
throw new NoSuchElementException();
}

T nextItem = curr.data;;
curr = curr.next;
okToRemove = true;
return nextItem;
}

public void remove() {
if (modCount != expectedModCount){
throw new ConcurrentModificationException();
}
if (!okToRemove){
throw new IllegalStateException();
}
MyLinkedList.this.remove(curr.prev);
expectedModCount++;
okToRemove = false;
}
}
}

评论