这篇文章我们来说说 Java 里一个很重要的数据结构 -- 线性表, 还是这张图, 线性表对应着下图里的 List.
红框里的内容就是线性表的大家族了, 其中黄色部分是要重点了解的, 线性表里的元素是按线性排列的 (这里的线性指逻辑上的) 线性表分为两大类, 分别是顺序表和链表:
一, 顺序表
顺序表中的数据元素存储是连续的, 内存划分的区域也是连续的. 存储结构如下图:
我们的 ArrayList 底层是数组实现的, 底层元素在内存中是按顺序排列的, ArrayList 是 Java 中顺序表的体现.
二, 链表
链表在物理存储上通常是非连续, 非顺序的方式存储的, 数据元素的逻辑顺序是通过链表中的引用来实现的.
1, 单向链表
很简单, 内存中的对象是随机分布的, 对象不但存储了张三, 李四等数据, 还持有一个 next 引用, 指向下一个对象, 来确定一组对象的逻辑顺序.
2, 循环链表
也很简单, 和单向链表一样, 只不过最后一个对象的 next 又指向了第一个对象.
3, 双向链表
不但持有 next 引用, 指向下一个对象, 还持有一个 prev 引用, 指向上一个对象.
记住双向链表这个图, 很重要, 下一篇文章我们要讲的 LinkedList 就是以双向链表的方式实现的. 三, 栈和队列栈和队列是两种比较特殊的线性表.
1, 栈
栈是一种操作受限制的线性表. 其限制是仅允许在线性表的尾部进行添加和删除操作, 这一端被称为栈顶, 另一端称为栈底. 向一个栈添加新元素叫压栈, 删除元素又称为出栈.
如上图, 把赵六放入到栈中叫压栈, 不放入赵六, 直接取出 (删除) 王五的过程叫出栈, 只能从栈顶放入和删除元素. 本文第一张图里的 Stack 就是栈在 Java 中的实现. 举个例子, 最后洗好的盘子都是叠放在最上面的, 但每次用的时候都是从最上面拿, 最先洗好的盘子反而不容易用到.
2, 队列
队列也是一种操作受限制的线性表. 只能从头部删除 (取出) 元素, 从队尾添加元素, 进行删除操作的端称为队头.
看上面的图, 只能从队尾添加元素, 队头取出 (删除) 元素. 本文第一张图里的 Queue 就是队列的体现, Queue 是基于链表来体现的. 注意, Queue 是一个接口, 直接写如下代码是会报错的
Queue queue = new Queue();// 会报错, Queue 是接口, 不允许实例化
正确的用法是
Queue queue = new LinkedList();// 正确的用法, 基于链表来实现
队列的链表实现是通过子类 LinkedList 来实现的, Queue 接口收窄了 LinkedList 的访问权限, 只提供从队尾, 队头等的操作.
为了加深大家的印象, 我举一个例子, 恶心了一点, 但保证大家能记住, 大家在喝啤酒的过程中, 正常去厕所小解的, 这个过程叫做队例. 喝多了吐出来的过程, 叫做栈.
以上就是 Java 线性表的介绍, 面试中会经常被问起, 后续文章会把重点都说一下, 希望对大家能有所帮助.
来源: https://juejin.im/post/5a7458925188257a6049699c