程序员必须知道的数据结构：线性表与链表

关注

发布于: 2021 年 03 月 06 日

既然我们这一节要说的是线性表与链表的内容，那么肯定要对数据结构的概念有一个认识。首先，数据结构一般分为逻辑结构、物理结构，逻辑结构指的是数据对象元素之间的相互关系，物理结构一般指的是数据的存储结构。逻辑结构主要包括集合结构、线性结构、树形结构、图形结构，物理结构主要有链式存储和线性存储。在数据结构的分析过程中，逻辑结构和物理结构是一种相辅相成的关系。

线性表的数据存储位置都是独立的、并且一个位置紧跟着下一个位置，在第 0 个位置上存储的数据是 a1、第一个位置上是 a2、以此类推，直到最后一个数据 an。假如说，要删除其中的一个数据 a2、那么紧接着 a3 就会移动到原来 a2 的位置、a4 就会移动到 a3 的位置，以至于最后 a2 之后的每一个数据都要向前移动一位，这也就使得线性存储的数据在删除的过程中效率会变得比较低。反之，线性存储结构存储数据时都是顺序存储的，没有指针对位置的指引操作，它的查询速度是相对比较快的。

在 Java 语言中，比较明显的线性表、链式表分别是 ArrayList、LinkedList，研究过 JDK 源码应该知道，这两种表分别都有的各自的添加、删除、查询方法，其两种表在实现这三种方法时也是截然不同的。下面我们分别拿出 ArrayList、LinkedList 的 add() 方法进行比较一下。注意：这里实例用的是 JDK1.8 源码展示。


// ArrayList 实现 add() 方法public boolean add(E e) {        ensureCapacityInternal(size + 1);  // Increments modCount!!        elementData[size++] = e;        return true;}// add() 方法没有指定添加的数据对象的位置// 实现也比较简单，直接将数据对象赋值到数组中// LinkedList 实现 add() 方法public void add(int index, E element) {        checkPositionIndex(index);        if (index == size)            linkLast(element);        else            linkBefore(element, node(index));}void linkBefore(E e, Node<E> succ) {        // assert succ != null;        final Node<E> pred = succ.prev;        final Node<E> newNode = new Node<>(pred, e, succ);        succ.prev = newNode;        if (pred == null)            first = newNode;        else            pred.next = newNode;        size++;        modCount++;    }

复制代码

本节就说到这里，以免大家视觉疲劳、源码部分有兴趣的猿童鞋可以自己深入研究。下一节我们看一下栈与队列的数据结构，记得关注后续更新、哈哈！

更多精彩前往微信公众号【老王说编程】>>>

发布于: 2021 年 03 月 06 日阅读数: 12

原文链接:【http://xie.infoq.cn/article/d08c4a2f9dab0251bbd410a7c】。文章转载请联系作者。

老王说编程

关注

还未添加个人签名 2021.03.03 加入

微信公众号【Python 集中营】作者，擅长后端编程语言开发，每天更新原创文章，专注于 Python实战干货技术，快来关注我吧！

发布

暂无评论

创作场景

程序员必须知道的数据结构：线性表与链表

老王说编程

评论