数据结构（一）-- 数组和链表

前言

在进入本系列文章之前，我们先明确几个概念。可能很多同学不太理解，为什么要学数据结构？为什么面试一定会问数据结构？平时写代码的时候感觉也没用过数据结构啊，数据结构到底重要在哪儿呢？首先，我可以很明确、很负责任的说，数据结构非常非常重要，百分之99的Java面试都会问到，不问数据结构只能说明面试官是个棒槌（不一定直接问，而是通过其他问题引出来）。

本文首发于心安-XinAnzzZ 的个人博客，转载请注明出处~

那么，第一个问题，数据结构是什么？百度百科传送门。我个人不是很喜欢特别官方的说法，感觉简单的问题说的太深奥，太高大上，看不懂。所以这里我还是说说自己对于数据结构的理解。我个人的理解就是，数据结构其实就是数据在计算机中的存储方式。我们所有看到的、听到的都是数据，那么这些数据应该以何种方式存储在计算机中，如何让我们高效的使用这些数据，这就是数据结构解决的问题。

举个简单的例子，我们知道在Java的集合类中，有ArrayList和LinkedList，Java基础比较不错的同学肯定马上就明白这个类的区别了。不清楚的也没有关系，本文后面会讲到这两种经典的数据结构。这里我先告诉大家，ArrayList对于查询操作，速度会优于LinkedList，而对于插入操作LinkedList却优于ArrayList。现在我们有一个需求，选用一个类来存储一个班级里面的所有同学的联系方式以供查询，聪明的同学肯定马上回答，肯定选择ArrayList，查询速度快嘛。答案是正确的，因为我们不太需要插入操作，更多的是查询操作，所以选择查询速度较快的ArrayList。

通过这个简单的例子我们就知道数据结构的重要性。试想一下，如果不了解数据结构，选择了错误的数据结构存储了一个word文档，结果打开这个文档竟然花费了5分钟，这是一件多么可怕的事情啊。同样的，设计合理的数据结构来让我们的数据更加高效、快速的存储和传输，对于我们程序设计者来说，简直太重要了。ok，一顿哔哔这么多，很多同学已经很烦了，赶紧进入正题开始搞事情吧。

数组

  • 数组的特点

有程序设计基础的同学相信都很熟悉数组这个名词了，几乎所有的程序语言都会有这种数据结构。那么数组是什么呢？它其实就是用来存储多个相同数据类型的数据的集合。

数组的特点：数组是在内存中开辟的一块连续的空间，数据存储是有序的，数组带有索引，并且索引值从0开始，数组的长度是不可变的。我们可以通过数组名[索引值]来访问数组中的元素，由于存在索引，所以数组的查询速度较快。

  • 为什么数组这么快

很多资料上面都这么说，但是却没有被解释为什么。这里我解释一下，我们要查询（访问）一个元素，就需要知道这个元素在内存中的位置，也就是内存地址，那么我们现在有一个数组，我们知道数组的内存地址(数组的索引中记录的就是数组的内存地址起始位置，这里描述的不准确，只是为了读者方便理解)，我们也可以通过数组元素的类型很容易知道每个元素的长度，那么每个元素的内存地址我们就可以通过数组起始地址加上该元素在数组中的位置乘以数组元素的长度来确定。如下：

image

上面的只是为了更好的和读者说明数组查询速度快的原理，与数组实际在内存中的存储可能有些出入，但是不妨碍大家理解。

  • 数组插入元素

    对容器的操作一共四种：增、删、改、查。上面我们说了数组的查询速度很快，并且讲述了其原理。下面我们看一下数组元素的插入。往数组中间插入一个新元素，如果要插入的位置上面已经有元素了就需要将后面的元素往后面移动一位，然后插入，同时，由于要插入新元素，所以原本的数组容量不再满足需求，所以需要创建新数组，把数据复制过去，然后插入新元素。如下图：

    image

    我们会发现数组的插入会受到插入的位置的影响。

    如果插入到数组的最后一个位置，那么只需要扩容然后插入即可，如果不考虑扩容的时间复杂度，那么插入到数组尾部的时间复杂度是O(1)；

    但是如果插入到数组头位置，就需要将整个数组的元素都往后移动一遍；同样不考虑扩容的时间复杂度，那么插入到数组头部的时间复杂度是O(n)；

    那么我们计算平均时间复杂度就是O(n/2) = O(n)。所以，结论就是数组插入元素到指定位置的时间复杂度是O(n)，这个时间复杂度是比较差的。

ArrayList

前面说了数组，发现数组最大的弊端就是数组的长度是不可变的，也就是当我们声明了一个长度为L的数组，这个数组的长度就不能再变化了。那么如果说我们的数据量大于数组长度的时候，这个数组就不再满足我们的需求了。Java在1.0版本就提供了一种“动态数组”，Vector，顾名思义就是长度可以自由变化的数组。但是由于这个类是线程安全的，效率相对较低，所以在Java1.2版本又推出了我们的主角ArrayList。ArrayList和Vector的主要区别就是ArrayList是线程不同步的，所以效率更高，也就逐渐取代了Vector。那么我们着重看一下这个ArrayList，看一下它是如何做到长度可以自由变化的。

transient Object[] elementData;

// 添加一个元素
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

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);
}

上面是ArrayList类的部分源码，首先有一个成员变量Object[] elementData，它就是用来装载元素的数组，之所以定义成Object类型是为了支持泛型，这里我们暂时不关注这个。

我们看到当添加元素的时候，也就是调用了add(E e)方法，它先是调用了ensureCapacityInternal(int minCapacity)，传入的参数是原本数组的size + 1，也就是添加新元素之后数组的size。接着调用ensureExplicitCapacity(int minCapacity)，在这里有一行if (minCapacity - elementData.length > 0)代码，这一行就是当添加了一个元素之后的数据量大于数组的size要执行的操作，也就是说现在这个数组装不下了，那么就调用grow(int minCapacity)方法，我们着重看一看这个方法。

这个方法第一行是保存了目前数组的长度，然后声明了一个新的变量newCapacity，新变量的值就等于原来数组长度 + 原数组长度右移一位，其实新数组长度等于原数组长度 * 1.5，不了解位运算的同学自行百度。下面还是几句代码还是操作这个新容量newCapacity，没有太多需要解释的，无非是处理一下容量的边界问题。最后一句代码是将原本数组中的元素复制到新数组中。

通过上面的分析，相信各位同学不难发现，其实ArrayList实现动态长度的原理无非是当发现数组满了，就扩容，通过源码发现，每次扩容到原来的1.5倍，然后建立新的数组，最后把旧数组中的数据复制到新数组中。

Tips: 线程安全指的是，在多个线程同时需要操作某个对象的时候，一个线程在操作的时候，就会给这个对象加上一把锁，避免其他线程同时操作。
简单来说就是，我在操作这个数组的时候别人都不能操作，这样虽然安全，但是效率会低很多。

链表

上面讲到数组是在内存中开辟的一块连续的空间来存储数据的，数据是有序的，而链表和数组则不同，链表是在内存中不连续的。链表是一个节点一个节点连接起来组成的线性结构，每个节点里面一部分存储了数据值，一部分存储了下一个节点的位置的“指针”。当然更复杂的还有双向链表，不仅存储了下一个节点的指针还存储了上一个节点的指针。单向链表在内存中的示意图如下：

image

那么看一下最简单的实现思路，实现一个 Node 类来表示每个节点，代码比较简单，就不过多解释了，看懂这个最基础版的再去看 Java 实现的会轻松很多：

public class LinkedList<E> {

    class Node {

        Node next;

        E e;

        Node(Node next, E e) {
            this.next = next;
            this.e = e;
        }

        Node(E e) {
            this(null, e);
        }

        Node() {
            this(null, null);
        }

        @Override
        public String toString() {
            return e.toString();
        }
    }

    private Node head;

    private int size;

    public int size() {
        return this.size;
    }

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

    /**
     * 在 index 位置插入元素 e
     *
     * @param e     新插入的元素
     * @param index 要插入的位置
     */
    public void add(E e, int index) {
        checkIndex(index);
        // 定义一个前置指针指向头结点，循环结束后这个指针将会指向 index - 1 位置
        Node preNode = this.head;
        for (int i = 0; i < index; i++) {
            preNode = preNode.next;
        }
        // 找到 index 位置的元素
        // Node next = preNode.next;

        // 通过元素 e 来构建新节点，并且让这个节点指向 index 位置的元素
        // Node newNode = new Node(next, e);

        // 让 index - 1 位置的元素的 next 指向新元素
        // preNode.next = newNode;
        // 下面这行代码是上面三行的简写
        preNode.next = new Node(preNode.next, e);
        size++;
    }

    /**
     * 查询指定位置的元素，修改指定位置的元素和此方法一致
     *
     * @param index 要查询的元素的索引
     * @return 节点的元素
     */
    public E get(int index) {
        checkIndex(index);
        Node current = head;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        return current.e;
    }

    /**
     * 移除指定索引位置的节点，并且返回节点的元素
     *
     * @param index 要删除的节点的索引值
     * @return 被删除的节点的元素
     */
    public E remove(int index) {
        checkIndex(index);
        Node preNode = head;
        for (int i = 0; i < index; i++) {
            preNode = preNode.next;
        }
        // 循环结束 preNode 指向 index - 1 位置
        // preNode 的下一个元素就是目标元素
        Node targetNode = preNode.next;
        // 让 index - 1 位置的元素指向 index + 1 位置的元素
        preNode.next = targetNode.next;
        targetNode.next = null;
        return targetNode.e;
    }

    private void checkIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("错误的索引值.");
        }
    }
}

笔者偷个懒，不画插入和删除节点的图示了，网上很容易就能找到，结合代码也能看得懂。

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