Java数据结构之线性表
这篇文章我们来说说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的访问权限，只提供从队尾，队头等的操作。
为了加深大家的印象，我举一个例子，恶心了一点，但保证大家能记住， 大家在喝啤酒的过程中，正常去厕所小解的，这个过程叫做队例。喝多了吐出来的过程，叫做栈 。
正文到此结束
热门推荐
相关文章
Loading...
![[HBLOG]公众号](http://www.liuhaihua.cn/img/qrcode_gzh.jpg)
