前言
前文介绍了单向链表,相信大家也了解单向链表是一个怎样的数据结构,除了单向链表,链表还有双向链表。
从名字也可以看出来,双向链表就是不止于从前(头部)向后(尾部)寻址,还可以从后向前寻址,显而易见的是,这样的数据结构,在某些场景,比如从尾部插入,删除等,比单向链表更有效率,相应的,由于每一个结点中存储了两个结点的地址,所以,双向链表比单向链表需要更大的空间,其实,这便是数据结构中空间换时间的思想。
在实际的应用中,并没有绝对最好的数据结构这样的说法, 事实上,根据场景的不同,选择合适的数据结构,合理平衡空间与时间是最有益的。
双向链表
对于链表来说,仍然是理解结点以及结点寻址!
以下代码均由java实现:
/*** @program: thinking-in-all* @description: 双向链表* @author: Lucifinil* @create: -12-30**/public class TwoWayLinkedList<T> {}
Node
对于双向链表的结点,与单向链表的结点相比,其区别就是结点存储两个地址,分别指向前驱和后继。
使用java来实现:
private class Node {T value;Node precursor;Node successor;public Node(T value, Node precursor, Node successor) {this.value = value;this.precursor = precursor;this.successor = successor;}Node(T value) {this(value, null, null);}Node() {this(null, null, null);}@Overridepublic String toString() {return value.toString();}}
属性
从上图的结点,我们很容易能想象到双向链表的样子:
可以看到,有两个特殊结点head和tail,head只存储后继结点地址,而tail只存储前驱结点地址,中间的所有node都存储前驱和后继结点的地址。
同样的,头结点和尾结点我们可以使用虚拟结点来表示,这样做的好处是:避免了在空链表或者只有一个结点时,head和tail的重叠,以及创建和删除结点时的复杂操作。
我们可以看看其区别,没有虚拟头尾结点:
我们可以看到,添加一个第一个结点,第二个结点,以及第三个及以后结点是三种不同的情况,究其原因,便是我们需要对头尾结点进行单独处理,而有虚拟头尾结点:
我们无论添加多少个结点,都是从头尾结点中间添加,不涉及到对头尾结点的操作,唯一的缺点的是多占了两个node的空间,微乎不计…
下面,用代码来实现虚拟头结点和尾结点!
//虚拟头结点private Node dummyHead; //虚拟尾结点结点private Node dummyTail;
如此简单,如此美妙!
除此之外,元素数量是我们必不可少的属性!
//链表元素数量private int size;
构造器
其实,链表本身的构造器很简单,因为链表是真正意义上的动态数据结构,它的创建不需要预先设置一个大小,我们需要给其固有的属性赋予初始值,并且让头尾结点指向彼此形成空链表的初始状态:
public TwoWayLinkedList() {dummyHead = new Node();dummyTail = new Node();dummyHead.successor = dummyTail;dummyTail.precursor = dummyHead;size = 0;}
辅助函数
获取元素数量,判空,是否包含元素等是各个数据结构几乎都有的辅助函数:
获取元素数量:
//获取链表元素数量public int size() {return size;}
判断链表是否为空:
//获取链表是否为空链表public boolean isEmpty() {return size == 0;}
这两个函数很简单,获得元素数量,直接返回size就可以了,我们需要注意的是对size的维护,判断是否为空,只要判断size是否尾0。
是否包含元素e :
//判断链表中是否包含元素epublic boolean contains(T e) {Node cur = dummyHead.successor;while (cur != null) {if (cur.value.equals(e)) {return true;}cur = cur.successor;}return false;}
这里我们需要注意的是,是否包含元素e这个方法,虽然双向链表相较于单向链表增加了尾结点,但事实上这个方法我们不知道元素e在链表更靠近头部还是尾部,所以,这里我沿用了单向链表的实现,从头部遍历,直到找到该元素或者遍历全部,当然,我们也可以选择从尾部遍历,甚至,两端一起遍历:
public boolean contains(T e) {Node cur1 = dummyHead.successor;Node cur2 = dummyTail.precursor;while (true) {if (cur1.value.equals(e)) {return true;}if (cur2.value.equals(e)){return true;}cur1 = cur1.successor;if (cur1.equals(cur2)){return false;}cur2 = cur2.precursor;}}
增加与删除结点
其实,看到这里,很容易可以想到双向链表的增删结点怎么完成的,无非是在单向链表的基础上,多改变一次结点的指向地址!
增加结点:
从上图可以看到,增加结点,无论是头部还是尾部增加,都是改变新增结点的前驱结点和后继结点的地址指向,只不过与单向链表不同的是,它是改变两个地址,而且它的遍历是可选择的,不再是一定要通过头部来寻址,它也可以通过尾部来寻址。
越靠近头部的便从头部开始遍历,越靠近尾部的便从尾部开始遍历,这样可以保证寻址效率更高:
public void add(int index, T e) {if (index < 0 || index > size) {throw new IllegalArgumentException("Add failed.Illegal index.");}if (index <= size / 2) {Node prev = dummyHead;for (int i = 0; i < index; i++) {//获得新增结点的前驱prev = prev.successor;}//创建新增结点Node node = new Node(e);//获得新增结点的后继Node succ = prev.successor;//为了结构清晰,这里把新增操作的三个结点都表示出来//使新增结点的后继指向succnode.successor = succ;//使新增结点的前驱指向prevnode.precursor = prev;//此刻新增结点已经添加进去了,但是其前驱和后继的地址还有待修正//修正前驱结点,使其后继指向node,而非succprev.successor = node;//修正后继结点,使其前驱指向node,而非prevsucc.precursor = node;} else {Node succ = dummyTail;for (int i = size - 1; i > index; i--) {//同上,只是从尾部开始寻址!succ = succ.precursor;}Node node = new Node(e);Node prev = succ.precursor;node.precursor = prev;node.successor = succ;succ.precursor = node;prev.successor = node;}size++;}
代码中的关键步骤,已经给出说明,这里不再赘述!其实上述代码是可以简化的,数据结构与算法的学习,在前期不太熟悉的时候,写清晰每一步,有助于我们的理解!不过,我们很容易地观察到,除了找到三个相关结点(新增结点,前驱后继)的方式有所差异,后续操作完全相同,优化后的代码为:
public void add(int index, T e) {if (index < 0 || index > size) {throw new IllegalArgumentException("Add failed.Illegal index.");}Node prev;//创建新增结点Node node = new Node(e);Node succ;if (index <= size / 2) {prev = dummyHead;for (int i = 0; i < index; i++) {//获得新增结点的前驱prev = prev.successor;}//获得新增结点的后继succ = prev.successor;} else {succ = dummyTail;for (int i = size; i > index; i--) {//同上,只是从尾部开始寻址!//获得新增结点的后继succ = succ.precursor;}//获得新增结点的前驱prev = succ.precursor;}//为了结构清晰,这里把新增操作的三个结点都表示出来//使新增结点的后继指向succnode.successor = succ;//使新增结点的前驱指向prevnode.precursor = prev;//此刻新增结点已经添加进去了,但是其前驱和后继的地址还有待修正//修正前驱结点,使其后继指向node,而非succprev.successor = node;//修正后继结点,使其前驱指向node,而非prevsucc.precursor = node;size++;}
删除结点:
从图片可以看到,被删除结点,所有与其相关引用全部置空,其前驱与后继建立相互引用!
代码如下:
public T remove(int index){if (isEmpty()) {throw new IllegalArgumentException("Remove failed.Linklist is empty.");}if (index < 0 || index >= size) {throw new IllegalArgumentException("Remove failed.Illegal index.");}if (index <= size / 2) {Node prev = dummyHead;for (int i = 0; i < index; i++) {//获得待删除结点的前驱prev = prev.successor;}//获得待删除结点Node node = prev.successor;//获得待删除结点的后继Node succ = node.successor;//同样的,我们获得删除操作所涉及的三个结点,更加清晰地进行结点的删除操作//将待删除结点的前驱结点的后继指向待删除结点的后继结点//这句话需要好好理解,也就是说前驱结点跳过了待删除结点指向后继结点,在图中可以看到prev.successor = succ;//同样的,将待删除结点的后继结点的前驱指向待删除结点的前驱结点//经过这样两步,这样结点就在链表中被"剔除"了succ.precursor = prev;//由于java的内存是GC管理,但存在引用的对象,是可能继续占用内存的//养成良好的编码习惯,将不适用的对象引用置空node.precursor = null;node.successor = null;size--;return node.value;}else {Node succ = dummyTail;for (int i = size - 1; i > index; i--) {//同理succ = succ.precursor;}Node node = succ.precursor;Node prev = node.precursor;node.precursor = null;node.successor = null;prev.successor = succ;succ.precursor = prev;size--;return node.value;}}
代码中的关键步骤已经用注释说明,这样我们需要注意的是,对于链表中管理索引的步骤,应当小心警惕!
另外,经过观察可以看到,文中有大量重复代码,经过优化后:
public T remove(int index) {if (isEmpty()) {throw new IllegalArgumentException("Remove failed.Linklist is empty.");}if (index < 0 || index >= size) {throw new IllegalArgumentException("Remove failed.Illegal index.");}//我们获得删除操作所涉及的三个结点,更加清晰地进行结点的删除操作Node prev;Node node;Node succ;if (index <= size / 2) {prev = dummyHead;for (int i = 0; i < index; i++) {//获得待删除结点的前驱prev = prev.successor;}//获得待删除结点node = prev.successor;//获得待删除结点的后继succ = node.successor;} else {succ = dummyTail;for (int i = size-1 ; i > index; i--) {//同理succ = succ.precursor;}node = succ.precursor;prev = node.precursor;}//将待删除结点的前驱结点的后继指向待删除结点的后继结点//这句话需要好好理解,也就是说前驱结点跳过了待删除结点指向后继结点,在图中可以看到prev.successor = succ;//同样的,将待删除结点的后继结点的前驱指向待删除结点的前驱结点//经过这样两步,这样结点就在链表中被"剔除"了succ.precursor = prev;//由于java的内存是GC管理,但存在引用的对象,是可能继续占用内存的//养成良好的编码习惯,将不适用的对象引用置空node.precursor = null;node.successor = null;size--;return node.value;}
代码的优化,说明了一个关键点,从图中我们也能观察到这个结论,那就是删除结点,除了遍历方式不同,删除结点的方式,修正前驱后继结点引用的方式都是相同的!
查改元素
到了这样,我觉得小伙伴们想到修改与查询元素是very easy滴,上图!
从图上,我们可以看到双向链表的修改与单向链表几乎是一样的,不同的只是双向链表寻址的方式可以从尾部开始遍历,结合上文的增删结点,我们可以得到查改的代码:
查询:
public T get(int index ){if (isEmpty()) {throw new IllegalArgumentException("Get failed.Linklist is empty.");}if (index < 0 || index >= size) {throw new IllegalArgumentException("Get failed.Illegal index.");}Node cur;if (index <= size / 2) {cur = dummyHead.successor;for (int i = 0; i < index; i++) {cur = cur.successor;}} else {cur = dummyTail.precursor;for (int i = size-1; i >index ; i--) {cur = cur.precursor;}}return cur.value;}
修改:
public void set(int index, T e) {if (isEmpty()) {throw new IllegalArgumentException("Set failed.Linklist is empty.");}if (index < 0 || index >= size) {throw new IllegalArgumentException("Set failed.Illegal index.");}Node cur;if (index <= size / 2) {cur = dummyHead.successor;for (int i = 0; i < index; i++) {cur = cur.successor;}} else {cur = dummyTail.precursor;for (int i = size-1; i >index ; i--) {cur = cur.precursor;}}cur.value = e;}
头尾操作
既然双向链表头部和尾部的操作效率都是O(1),我们可以利用其特性,复用上文实现的函数,实现对头尾的crud操作:
头部操作:
public void addFirst(T e){add(0,e);}public T removeFirst(){return remove(0);}public T getFirst(){return get(0);}public void setFirst(T e){set(0,e);}
尾部操作:
public void addLast(T e) {add(size , e);}public T removeLast() {return remove(size-1);}public T getLast() {return get(size-1 );}public void setLast(T e) {set(size-1 , e);}
因为添加操作是在index所在位置添加,在尾部添加其实是对一个不存在的元素进行添加,该位置是index等于size的地方!
我相信,小伙伴们对这种头部和尾部的操作一定不会陌生!因为栈,队列等结构便是涉及头部尾部的操作!
我们可以使用双向链表封装自己的栈和队列等!
完整代码
以下代码已经经过测试,小伙伴们放心食用,不要忘了点赞哟!–来自帅帅的路西菲尔:)
package com.lucifer.linkedlist;/*** @program: thinking-in-all* @description: 双向链表* @author: Lucifinil* @create: -12-30**/public class TwoWayLinkedList<T> {private class Node {T value;Node precursor;Node successor;Node(T value, Node precursor, Node successor) {this.value = value;this.precursor = precursor;this.successor = successor;}Node(T value) {this(value, null, null);}Node() {this(null, null, null);}@Overridepublic String toString() {return value.toString();}}//虚拟头结点private Node dummyHead;//虚拟尾结点结点private Node dummyTail;//链表元素数量private int size;public TwoWayLinkedList() {dummyHead = new Node();dummyTail = new Node();dummyHead.successor = dummyTail;dummyTail.precursor = dummyHead;size = 0;}//获取链表元素数量public int size() {return size;}//获取链表是否为空链表public boolean isEmpty() {return size == 0;}public boolean contains(T e) {Node cur1 = dummyHead.successor;Node cur2 = dummyTail.precursor;while (true) {if (cur1.value.equals(e)) {return true;}if (cur2.value.equals(e)) {return true;}cur1 = cur1.successor;if (cur1.equals(cur2)) {return false;}cur2 = cur2.precursor;}}public void add(int index, T e) {if (index < 0 || index > size) {throw new IllegalArgumentException("Add failed.Illegal index.");}Node prev;//创建新增结点Node node = new Node(e);Node succ;if (index <= size / 2) {prev = dummyHead;for (int i = 0; i < index; i++) {//获得新增结点的前驱prev = prev.successor;}//获得新增结点的后继succ = prev.successor;} else {succ = dummyTail;for (int i = size; i > index; i--) {//同上,只是从尾部开始寻址!//获得新增结点的后继succ = succ.precursor;}//获得新增结点的前驱prev = succ.precursor;}//为了结构清晰,这里把新增操作的三个结点都表示出来//使新增结点的后继指向succnode.successor = succ;//使新增结点的前驱指向prevnode.precursor = prev;//此刻新增结点已经添加进去了,但是其前驱和后继的地址还有待修正//修正前驱结点,使其后继指向node,而非succprev.successor = node;//修正后继结点,使其前驱指向node,而非prevsucc.precursor = node;size++;}public T remove(int index) {if (isEmpty()) {throw new IllegalArgumentException("Remove failed.Linklist is empty.");}if (index < 0 || index >= size) {throw new IllegalArgumentException("Remove failed.Illegal index.");}//我们获得删除操作所涉及的三个结点,更加清晰地进行结点的删除操作Node prev;Node node;Node succ;if (index <= size / 2) {prev = dummyHead;for (int i = 0; i < index; i++) {//获得待删除结点的前驱prev = prev.successor;}//获得待删除结点node = prev.successor;//获得待删除结点的后继succ = node.successor;} else {succ = dummyTail;for (int i = size-1 ; i > index; i--) {//同理succ = succ.precursor;}node = succ.precursor;prev = node.precursor;}//将待删除结点的前驱结点的后继指向待删除结点的后继结点//这句话需要好好理解,也就是说前驱结点跳过了待删除结点指向后继结点,在图中可以看到prev.successor = succ;//同样的,将待删除结点的后继结点的前驱指向待删除结点的前驱结点//经过这样两步,这样结点就在链表中被"剔除"了succ.precursor = prev;//由于java的内存是GC管理,但存在引用的对象,是可能继续占用内存的//养成良好的编码习惯,将不适用的对象引用置空node.precursor = null;node.successor = null;size--;return node.value;}public void set(int index, T e) {if (isEmpty()) {throw new IllegalArgumentException("Set failed.Linklist is empty.");}if (index < 0 || index >= size) {throw new IllegalArgumentException("Set failed.Illegal index.");}Node cur;if (index <= size / 2) {cur = dummyHead.successor;for (int i = 0; i < index; i++) {cur = cur.successor;}} else {cur = dummyTail.precursor;for (int i = size - 1 ; i > index; i--) {cur = cur.precursor;}}cur.value = e;}public T get(int index) {if (isEmpty()) {throw new IllegalArgumentException("Get failed.Linklist is empty.");}if (index < 0 || index >= size) {throw new IllegalArgumentException("Get failed.Illegal index.");}Node cur;if (index <= size / 2) {cur = dummyHead.successor;for (int i = 0; i < index; i++) {cur = cur.successor;}} else {cur = dummyTail.precursor;for (int i = size - 1; i > index; i--) {cur = cur.precursor;}}return cur.value;}public void addFirst(T e) {add(0, e);}public T removeFirst() {return remove(0);}public T getFirst() {return get(0);}public void setFirst(T e) {set(0, e);}public void addLast(T e) {add(size, e);}public T removeLast() {return remove(size - 1);}public T getLast() {return get(size - 1);}public void setLast(T e) {set(size - 1, e);}@Overridepublic String toString() {StringBuilder res = new StringBuilder();res.append("head [ ");Node cur = dummyHead.successor;for (int i = 0; i < size; i++) {res.append(cur.toString()).append(" <-> ");cur = cur.successor;}res.append("tail ]");return res.toString();}}
总结
链表的形式多种多样,不止于此,除了这样的双向链表,还有单向环链表,双向环链表等等。
除了前文提到的使用循环遍历来寻址,链表和树这样的动态结构,是具有递归性质的,我们可以使用递归来实现。
其实,就算是基础的数据结构,我们在剖析与实现的过程中,也会学习到一些思想,对于双向链表来说,以空间换时间就是对于单向链表效率的进一步提升,当然,除了这样的思路,数据结构和算法,还有许许多多的方法和技巧,我觉得这就是数据结构与算法 的魅力所在。
最后,今天是的最后一天,希望我与小伙伴们以及我爱的人们都能身体健康,万事如意!也期待未来的一年能得到更好的发展,能将学习作为自己的事业坚持下去!
我是帅气的路西菲尔,期待与你一同成长:)
如有不正,敬请指出,原文来自路西菲尔/csdn_1364491554/article/details/103768706!