前言
链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。
由于链表不必按照顺序存储,故在插入数据时可以达到O(1)的复杂度,但是查找的时候就需要遍历,时间复杂度为O(n)。
分类
链表根据实现方式一般有三种分类:单向链表、循环链表、双向链表。
单向链表
单向链表指的是链表中的元素的指向只能指向链表中的下一个元素或者为空,元素之间不能相互指向。也就是一种线性链表。
图示:
普通单向链表
用Java代码实现一普通的单向链表。
1 | public class SingleLinkList { |
栈具有先进后出的原则,所以单向链表可以用来实现栈。Java代码如下:
1 | public class StackSingleLinkList { |
我们可以看出,如果对链表的最后一个元素进行操作,需要遍历到链表尾部,在进行操作,十分消耗资源。
双端链表
还有一种单向链表称为双端链表。这种链表有一个特点,即在链表内添加了对链表尾部的引用。这使得链表可以方便的操作尾部元素。
Java代码实现如下:
1 | public class DoublePointLinkList { |
双端链表可以用来实现队列,相关实现如下:
1 | public class QueueLinkList { |
有序链表
上面所说的单链表数据都是无序的,我们可以构建一个有序的单向链表。即有序链表。
1 | public class OrderLinkList { |
对于有序链表,可以看出,插入或删除某一项最多需要O(n)的时间复杂度(遍历),但如果我们每次只删除最小值,且对插入没有过高要求的话,有序链表是一个不错的选择,比如优先级队列就可以利用有序链表实现。
比如我们插入int数并以最小值为优先级,每次取最小的int值的队列。
1 | public class QueueOrderLinkList { |
单向链表的用途可以说是十分广泛的。
双向链表
双向链表即是这样一个有序的结点序列,每个链表元素既有指向下一个元素的指针,又有指向前一个元素的指针,其中每个结点都有两种指针,即left和right。left指针指向左边结点,right指针指向右边结点。所以双向链表是可以从两个方向进行遍历的。
图示:
双向链表的Java实现:
1 | public class DoubleWayLinkList { |
使用双向链表可以构建双端队列。在这儿就不上代码了,和之前的队列构造类似。
循环链表
循环链表指的是在单向链表和双向链表的基础上,将两种链表的最后一个结点指向第一个结点从而实现循环。
图示:
循环链表的Java实现:
1 | public class CircleLinkList<T> { |
同样,使用循环链表可以实现循环队列。
总结
链表作为数据结构的一部分,应用是十分广泛的,我们上面说明了几种链表在不同情况下的应用,链表是我们应当学会掌握和使用的。