数据结构（一）——线性表、栈和队列

数据结构是编程的起点，理解数据结构可以从三方面入手：

  1. 逻辑结构。逻辑结构是指数据元素之间的逻辑关系，可分为线性结构和非线性结构，线性表是典型的线性结构，非线性结构包括集合、树和图。
  2. 存储结构。存储结构是指数据在计算机中的物理表示，可分为顺序存储、链式存储、索引存储和散列存储。数组是典型的顺序存储结构；链表采用链式存储；索引存储的优点是检索速度快，但需要增加附加的索引表，会占用较多的存储空间；散列存储使得检索、增加和删除结点的操作都很快，缺点是解决散列冲突会增加时间和空间开销。
  3. 数据运算。施加在数据上的运算包括运算的定义和实现。运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体操作步骤。

因此，本章将以逻辑结构（线性表、树、散列、优先队列和图）为纵轴，以存储结构和运算为横轴，分析常见数据结构的定义和实现。

在Java中谈到数据结构时，首先想到的便是下面这张Java集合框架图：

Java 集合框架图

从图中可以看出，Java集合类大致可分为List、Set、Queue和Map四种体系，其中：

  • List代表有序、重复的集合；
  • Set代表无序、不可重复的集合；
  • Queue代表一种队列集合实现；
  • Map代表具有映射关系的集合。

在实现上，List、Set和Queue均继承自Collection，因此，Java集合框架主要由Collection和Map两个根接口及其子接口、实现类组成。

本文将重点探讨线性表的定义和实现，首先梳理Collection接口及其子接口的关系，其次从存储结构（顺序表和链表）维度分析线性表的实现，最后通过线性表结构导出栈、队列的模型与实现原理。主要内容如下：

  1. Iterator、Collection及List接口
  2. ArrayList / LinkedList实现原理
  3. Stack / Queue模型与实现

一、Iterator、Collection及List接口

Collection接口是List、Set和Queue的根接口，抽象了集合类所能提供的公共方法，包含size()、isEmpty()、add(E e)、remove(Object o)、contains(Object o)等，iterator()返回集合类迭代器。

public interface Collection<E> extends Iterable<E> {
    int size();
    boolean isEmpty();
    Iterator<E> iterator();
    boolean add(E e);
    boolean addAll(Collection<? extends E> c);
    boolean remove(Object o);
    boolean removeAll(Collection<?> c);
    boolean contains(Object o);
    boolean containsAll(Collection<?> c);
    void clear();
    boolean equals(Object o);
    int hashCode();
}

Collection接口继承自Iterable接口，实现Iterable接口的集合类可以通过迭代器对元素进行安全、高效的遍历，比如for-each，Iterable的iterator方法负责返回Iterator迭代器。

public interface Iterable<T> {
    Iterator<T> iterator();
}

Iterator迭代器包含集合迭代时两个最常用的方法：hasNext和next。hasNext用于查询集合是否存在下一项，next方法用于获取下一项。

public interface Iterator<E> {
    boolean hasNext();
    E next();
}

List接口继承自Collection接口，相比于Collection接口已有的增删改查的方法，List主要增加了index属性和ListIterator接口。因此，除Collection接口方法，List接口的主要方法如下：

public interface List<E> extends Collection<E> {
    public E get(int location);
    public int indexOf(Object object);
    public int lastIndexOf(Object object);
    public ListIterator<E> listIterator();
    // ……
}

ListIterator接口继承Iterator接口，因此，在正向遍历方法hasNext和next的基础上，ListIterator接口增加了实现逆序遍历的方法hasPrevious和previous，使其具有双向遍历的特性。如下所示：

public interface ListIterator<E> extends Iterator<E> {
    public boolean hasPrevious();
    public E previous();
    public int previousIndex();
    // ……
}

下面举个栗子说明采用ListIterator进行双向遍历。

List<String> list = new ArrayList<>();
list.add("aaa");
list.add("bbb");
list.add("ccc");

ListIterator<String> listIterator = list.listIterator();
while(listIterator.hasNext()) {
    System.out.print(listIterator.next());
}
while (listIterator.hasPrevious()) {
    System.out.print(listIterator.previous());
}

ArrayList通过内部类Itr实现了ListIterator接口，Itr包含指示迭代器当前位置的域cursor，next()方法会把cursor向后推动，相反，previous()方法则把cursor向前推动，所以上述代码能对该List的元素进行双向遍历。

另外，在List上使用for-each语法遍历集合时，编译器判断List实现了Iterable接口，会调用iterator的方法来代替for循环。

// 程序版本
private void traversalA() {
    for (String s : list) {
        Log.d("TraversalA Test:", s);
    }
}
// 编译器版本
private void traversalB() {
    Iterator<String> iterator = list.iterator();
    while (iterator.hasNext()) {
        String s = iterator.next();
        Log.d("TraversalB:", s);
    }
}

二、ArrayList / LinkedList实现原理

Java程序员都知道ArrayList 基于数组、LinkedList基于链表实现，因此，这里不再对基本原理进行赘述，下面主要从数据结构、添加/删除方法和迭代器三个方面分别说明ArrayList和LinkedList实现原理：

对比内容 ArrayList LinkedList
数据结构 数组 双向链表
添加/删除方法 System.arraycopy复制 改变前后元素的指向
迭代器 Iterator和ListIterator ListIterator

2.1 ArrayList实现原理

ArrayList是可改变大小的、基于索引的数组，使用索引读取数组中的元素的时间复杂度是O(1)，但通过索引插入和删除元素却需要重排该索引后所有的元素，因此消耗较大。但相比于LinkedList，其内存占用是连续的，空间利用效率更高。

2.1.1 扩容

扩容是ArrayList能够改变元素存储数组大小的保证。在JDK1.8中，ArrayList存放元素的数组的默认容量是10，当集合中元素数量超过它时，就需要扩容。另外，ArrayList最大的存储长度为Integer.MAX_VALUE - 8（虚拟机可能会在数组中添加一些头信息，这样避免内存溢出）。

private static final int DEFAULT_CAPACITY = 10;
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

扩容方法主要通过三步实现：1）保存旧数组；2）扩展新数组；3）把旧数据拷贝回新数组。

// 扩容方法
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}
// Arrays拷贝
public static <T> T[] copyOf(T[] original, int newLength) {
    return (T[]) copyOf(original, newLength, original.getClass());
}
// 调用System.arraycopy实现
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    T[] copy = ((Object)newType == (Object)Object[].class) ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));
    return copy;
}

由于oldCapacity >> 1等于oldCapacity / 2，所以扩容后的数组大小为旧数组大小的1.5倍。另外，Arrays中的静态方法是通过调用Native方法System.arraycopy来实现的。

2.1.2 add / remove方法

当在ArrayList末尾添加/删除元素时，由于对其他元素没有影响，所以时间负责度仍为O(1)。这里忽略这种情况，以通过索引插入/删除数据为例说明add / remove方法的实现：

public void add(int index, E element) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    elementData[index] = element;
    size++;
}

public E remove(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    modCount++;
    E oldValue = (E) elementData[index];

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

public static native void arraycopy(Object src,  int  srcPos, 
                            Object dest, int destPos, int length);

添加元素时，首先确保数组容量足够存放size+1个元素，然后将index后的size-index个元素依次后移一位，在index处保存新加入的元素element，同时增加元素总量；与添加元素相反，删除元素时将index后的size-(index+1)个元素依次前移动一位，同时减小元素总量。可见，添加/删除元素均通过调用System.arraycopy方法来实现数据的移动，效率较高。但另一方面，从上述实现可以看出，ArrayList并非线程安全，在并发环境下需要使用线程安全的容器类。

2.1.3 Iterator和ListIterator

如前所述，ArrayList实现了List接口，其包含两种迭代器：Iterator和ListIterator，ListIterator相比于Iterator能实现前向遍历。在ArrayList中，通过内部类Itr实现了Iterator接口，内部类ListItr继承自Itr并且实现了ListIterator，因此，ArrayList的iterator()方法放回的是Itr对象，listIterator()方法反回ListIterator对象。

private class Itr implements Iterator<E> {
    int cursor;
    int lastRet = -1;
    int expectedModCount = modCount;
    // ……
}

private class ListItr extends Itr implements ListIterator<E> {
    ListItr(int index) {
        super();
        cursor = index;
    }
    
    // ……
}

public Iterator<E> iterator() {
    return new Itr();
}

public ListIterator<E> listIterator() {
    return new ListItr(0);
}

Itr的成员变量中，cursor表示下一个访问对象的索引，lastRet表示上一个访问对象的索引，expectedModCount表示对ArrayList修改次数的期望值，初始值为modCount，而modCount是ArrayList父类AbstractList中定义的成员变量，初始值为0，在上述add()和remove()方法中，都会对modCount加1，增加修改次数。

在使用ArrayList的remove()方法进行对象删除时，一种常见的运行时异常是ConcurrentModificationException，虽名为并发修改异常，但实际上单线程环境中也可能报出，原因就是上述expectedModCount与modCount不相等的问题。

一种常见的使用场景是通过for-each语法删除元素：

public void removeElement(List<Integer> list) {
    for (Integer x : list) {
        if (x % 2 == 0) {
            list.remove(x); // 调用ArrayList的remove方法
        }
    }
}

上节提到，for-each是一种语法糖，编译之后依然调用了迭代器实现。而迭代器的next()方法会首先调用checkForComodification()方法检查expectedModCount与modCount，如果不等就抛出ConcurrentModificationException。

final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

所以，当上述代码中调用ArrayList的remove删除元素后，modCount自增，而迭代器中expectedModCount保持不变，就会抛出ConcurrentModificationException，但是，如果使用迭代器的remove()方法则不会抛出异常，为什么呢？

public void removeElement2(List<Integer> list) {
    Iterator<Integer> itr = list.iterator();
    while (itr.hasNext()) {
        if (itr.next() % 2 == 0) {
            itr.remove(); // 调用迭代器的remove方法
        }
    }
}

public void remove() {
    if (lastRet < 0)
        throw new IllegalStateException();
    checkForComodification();

    try {
        ArrayList.this.remove(lastRet); // 调用ArrayList的remove方法
        cursor = lastRet;
        lastRet = -1;
        expectedModCount = modCount; // 设置expectedModCount 为modCount
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
    }
}

从代码中可以看出，其实迭代的remove方法也是调用了ArrayList的remove方法实现元素删除，只不过在删除元素之后设置了expectedModCount为modCount，避免checkForComodification时抛出异常。

2.2 LinkedList实现原理

链表按照链接形式可分为：单链表、双链表和循环链表。单链表节点包含两个域：信息域和指针域，信息域存放元素，指针域指向下一个节点，因此只支持单向遍历。其结构如下图所示：

单链表存储结构

相比于单链表，双链表节点包含三个域：信息域、前向指针域和后向指针域，前向指针指向前一个节点地址，后向指针指向后一个节点地址，因此可以实现双向的遍历。其结构如下图所示：

双链表存储结构

循环链表分为单循环链表和双循环链表。即在普通单链表和双链表的基础上增加了链表头节点和尾节点的相互指向。头节点的前一个节点是尾节点，尾节点的下一个节点是头节点。其结构如下图所示：

循环链表存储结构

LinkedList基于双链表实现，插入和删除元素的时间复杂度是O(1)，支持这种实现的基础数据结构是LinkedList中定义的静态内部类Node：

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

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

Node有三个成员变量：item负责存储元素，next和prev分别指向下一个节点和前一个节点，因此可实现双向的元素访问，LinkedList的操作方法都是基于Node节点特性设计的。

2.2.1 插入/删除元素

在实现上，由于Deque接口同时具有队列（双向）和栈的特性，LinkedList实现了Deque接口，使得LinkedList能同时支持链表、队列（双向）和栈的操作。其插入/删除方法如下表所示：

方法 链表 队列 栈
添加 add(int index, E element) offer(E e) push(E e)
删除 remove(int index) E poll() E pop()

三者的差别在于，offer在链表末尾插入元素，调用linkLast实现；push在链表头部插入元素，调用linkFirst实现；而add在指定位置插入元素，根据位置判断调用linkLast或linkBefore方法。这里重点关注linkLast、linkFirst和linkBefore的实现。

private void linkFirst(E e) {
    final Node<E> f = first;
    // 创建新节点，其prev节点为null，元素值为e，next结点为之前的first节点
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    // 如果初始列表为空，则将尾结点设置为当前新节点
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    // 增加链表数量及修改次数
    size++;
    modCount++;
}

void linkLast(E e) {
    final Node<E> l = last;
    // 创建新节点，其prev结点为之前的尾节点，元素值为e，next节点为null
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    // 如果初始列表为空，则将头结点设置为当前新节点
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    // 增加链表数量及修改次数
    size++;
    modCount++;
}

void linkBefore(E e, Node<E> succ) {
    // 创建succ的prev节点引用
    final Node<E> pred = succ.prev;
    // 创建新节点，其prev节点为succ的prev节点，元素值为e，next节点为succ
    final Node<E> newNode = new Node<>(pred, e, succ);
    // 修改原succ节点的prev指向
    succ.prev = newNode;
    // 如果succ为头节点，则设置新节点为头节点
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    // 增加链表数量及修改次数
    size++;
    modCount++;
}

以上代码中的注释对linkLast、linkFirst和linkBefore的实现进行了详细的说明，其核心原理便是初始化新节点，并重新链接与原链表中元素的关系。remove、poll和pop在删除元素时调用了与插入操作相反的方法unlinkFirst、unlinkLast和unlink，由于实现原理类似，这里不再赘述。

2.2.2 查找及迭代器

从上节分析可以看出，LinkedList的插入/删除操作只需要改变节点元素的链接指向，因此效率较高。但其查找元素需要从头节点或尾节点开始对集合进行遍历，相比于ArrayList基于数组索引，效率较低。

Node<E> node(int index) {
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

LinkedList通过比较index与size/2（size >> 1）判断是从头节点还是尾节点开始遍历，然后通过分别获取该节点的next节点或prev节点来实现。另外，由于LinkedList本身就同时支持前向/后向移动，所以其iterator方法直接返回ListIterator实现。

public Iterator<E> iterator() {
    return listIterator();
}

三、Stack / Queue模型、实现及应用

Stack和Queue在模型设计上具有相似性，其核心方法对比如下：

方法 Stack Queue
插入 push(E item) offer(E e)
删除 E pop() poll()
查看 E peek() E peek()

两者的核心区别在于Stack是先进后出（FILO），数据操作在一端进行；而Queue是先进先出（FIFO），在一端存储，另一端取出（Deque继承自Queue，支持双向存储/取出）。

从上节可知，LinkedList是Queue（Deque）模型最常见的一种实现。下面通过一个实例，说明如何利用LinkedList的队列特征来模拟单向循环链表。比如有一个任务集合，任务有是否完成两种状态，初始状态均为未完成，需要实现从第一个任务开始的单向循环遍历，如果当前任务完成，则不再参与遍历，直到所有任务完成。

private Task getNextUnCompleteTask(LinkedList<Task> taskList) {
    Task task = taskList.peek(); 
    if (task == null) {
        return null;
    }
    if (task.isComplete()) {
        taskList.poll();
    } else {
        taskList.offer(taskList.poll());
    }
    return taskList.peek();
}

上述代码通过将未完成的任务重新添加至队尾，从而在循环调用getNextUnCompleteTask方法时，实现对未完成任务的循环遍历。

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 211,948评论 6赞 492
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 90,371评论 3赞 385
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 157,490评论 0赞 348
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 56,521评论 1赞 284
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 65,627评论 6赞 386
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 49,842评论 1赞 290
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,997评论 3赞 408
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 37,741评论 0赞 268
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,203评论 1赞 303
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,534评论 2赞 327
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,673评论 1赞 341
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,339评论 4赞 330
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,955评论 3赞 313
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,770评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,000评论 1赞 266
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 46,394评论 2赞 360
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 43,562评论 2赞 349

推荐阅读更多精彩内容

  • 线性表及ArrayList/LinkedList源码分析总结
    一.线性表 定义:零个或者多个元素的有限序列。也就是说它得满足以下几个条件:  ①该序列的数据元素是有限的。  ②...
    Geeks_Liu阅读 2,693评论 1赞 12
  • 集合总论
    Collection接口 Collection接口是所有集合的祖先类。他有两个构造方法，一个无参构造，一个是带Co...
    夜幕繁华阅读 585评论 0赞 0
  • java笔记
    java笔记第一天 == 和 equals ==比较的比较的是两个变量的值是否相等，对于引用型变量表示的是两个变量...
    jmychou阅读 1,488评论 0赞 3
  • 你拥有的越多，被占有的也就越多
    人为什么总是喜欢怀念小时候？因为那时我们一无所有，整日无忧。 长大后，我们拥有的越来越多，想拥有的也越来越多。 每...
    Lancy日记阅读 2,719评论 0赞 15
  • 七律~京胡咏（新韵）
    琴中应数谁为最，独忆京胡不解缘。 严父竹竿雕两把，顽儿马尾练七年。 推拉顿挫方知妙，急缓悠扬竟品甜。 梁绕余音君老...
    艾思阅读 973评论 21赞 23