关于线性结构中的双向链表如何实现？

前言

在上一篇文章中，主要是给大家介绍了单向链表的特点及其原理，但是我们没有通过代码进行练习。今天我会继续通过一篇文章，来给大家讲解双向链表的内容，尤其是会通过代码来进行链表的操作，希望大家重点关注哦。
全文大约【3500】 字，不说废话，只讲可以让你学到技术、明白原理的纯干货！本文带有丰富的案例及配图视频，让你更好地理解和运用文中的技术概念，并可以给你带来具有足够启迪的思考...
一. 双向链表简介

1. 概念

在上一篇文章中，我们在介绍链表的种类时，曾经提到过双向链表。双向链表相比较于单链表，除数据域外，还具前和后两个指向指针。

双向链表中的结构术语可以解释为：

• data：链表每个结点中存储的数据域；
  
• next：链表每个结点中包含的指向下一个结点地址的指针域；
  
• prev：链表每个结点中包含的前一个结点地址的指针域。
  

2. 编码定义

根据上述对双向链表结点的定义，我们给出双向链表结点结构的Java定义实现：

1. class DNode{
2.     Object data;
3.     Node prev;
4.     Node next;
5. }

复制代码

双向链表是一条真实存在的链表，由多个结点组成。在实际的编程中，通常会标记链表的两个特殊结点，分别为：头结点、尾结点。用另外一个变量size表示链表中元素的个数。

• 头结点： 链表中的第一个结点
  
• 尾结点： 链表中的最后一个元素
  

因此有如下链表类的定义：

1. public class DoubleLinkList{
2.     private int size;//大小
3.     private DNode head;//头结点
4.     private DNode last;//尾结点
5. }

复制代码

在本篇文章接下来的内容中，我们将利用该DNode、DoubleLinkList两个定义来实现双向链表的各项操作。
二. 常见操作

因为双向链表是单链表的基础上扩展出来的结构，因此双向链表的很多操作与单链表的操作都是相同的，比如：查找元素、更新元素、插入元素、删除元素。
1. 查找元素

1.1 查找头结点

因为DoubleLinkList中已经记录了头结点head，因此头结点的查找非常简单，如下：

1. public Object getHead(){
2.     if(head == null){
3.         return null;
4.     }
5.     return head.data;
6. }

复制代码

时间复杂度为O(1)。
1.2 查找尾结点

与头结点同理，查找尾结点的时间复杂度同样为O(1），编码如下：

1. public Object getLast(){
2.     if(last == null){
3.         return null;
4.     }
5.     return last.data;
6. }

复制代码

1.3 查找指定位置结点

当需要查找指定位置的结点元素时，双向链表比单链表的实现方式有所不同，原因是： 单链表因为是单向的，因此只能从头结点向后单向查找；但双向链表前后均可查找，因此在进行指定位置查找时，为了提高查找效率，会首先判断要查找的位置处于链表的前半段还是后半段，若前半段则从头结点向后查找，若后半段则从尾结点向前查找，具体编程如下所示：

1. public Object get(int index){
2.     //排除边界异常
3.     if(index <0 || index>=size){
4.         return null;
5.     }
6.         //要查找的位置位于链表前半段
7.         if(index < (size>>1)){
8.         DNode x = head;
9.         for(int i = 0; i < index; i++){
10.             x = x.next;
11.         }
12.         return x.data;
13.     }else {//要查找的位置位于链表后半段
14.         DNode x = last;
15.         for(int i = size - 1; i >= index; i--){
16.             x = x.prev;
17.         }
18.         return x.data;
19.     }
20. }

复制代码

在上述代码中，size >> 1 的写法比较少见，“>>”在计算机编程中代表移位操作。常见的移位操作有两种：

通过实际的编程验证，我们可以知道：执行右移1位操作，变量数据会缩小为原来的1/2。左移相反。同时，我们可以分析出时间复杂度为O(n)。
2. 更新元素

更新元素操作需要两步：

• 找到要更新的元素
  
• 执行更新操作
  

根据位置的不同，可以将更新操作分为三种情况：更新头结点，更新尾结点，更新指定位置结点。
2.1 更新头结点

更新头结点代码与查找头结点类似，如下：

1. public boolean updateHead(Object obj){
2.     if(head == null){
3.         return false;
4.     }
5.         head.data = obj;
6.         return true;
7. }

复制代码

更新头结点的时间复杂度为O(1)。
2.2 更新尾结点

1. public boolean updateLast(Object obj){
2.     if(last == null){
3.         return false;
4.     }
5.         last.data = obj;
6. }

复制代码

更新尾结点的时间复杂度同样是O(1)。
2.3 更新指定位置结点

1. public boolean update(int index, Object obj){
2.     if(index < 0 || index >= size){
3.         return false;
4.     }
5.     if(index < (size>>1)){
6.         DNode x = head;
7.         for(int i = 0; i < index; i++){
8.             x = x.next;
9.         }
10.         x.data = obj;
11.     }else {
12.         DNode x = last;
13.         for(int i = size-1; i >= index; i--){
14.             x = last.prev;
15.         }
16.         x.data = obj;
17.     }
18.     return true;
19. }public boolean addHead(Object data){
20.     DNode h = head;
21.         DNode newNode = new DNode(null,data,h);
22.         head = newNode;
23.         if(h == null);{
24.         last = newNode;
25.     }else {
26.         h.prev = newNode;
27.     }
28.         size++;
29.         return true;
30. }

复制代码

如上代码所示，修改指定结点元素的值采用的算法也是：先判断要操作的位置在前半段还是后半段，然后再进行精准查找，最后执行修改操作。
指定位置修改操作的时间复杂度为O(n)。
3. 插入元素

分析过了查找元素和更新元素操作的具体情况，我们很清晰的便能分析出插入元素操作的具体情况，其实也分为三种具体情景：头结点位置插入，尾结点位置插入，指定位置插入元素。
3.1 头结点位置插入

1. public boolean addHead(Object data){
2.     DNode h = head;
3.         DNode newNode = new DNode(null,data,h);
4.         head = newNode;
5.         if(h == null);{
6.         last = newNode;
7.     }else {
8.         h.prev = newNode;
9.     }
10.         size++;
11.         return true;
12. }

复制代码

根据如上代码，我们可以看到，在头结点位置插入新的元素，只需要将新添加的结点置为head结点，同时处理好新结点和原链表中头结点的指向关系即可。很明显，头结点位置插入的时间复杂度为O(1)。
3.2 尾结点位置插入

尾结点插入与头结点插入原理相同，只需要替换为尾结点以及指针的指向。如下所示：

1. public boolean addLast(Object data){
2.     DNode l = last;
3.         DNode newNode = new DNode(l,data,null);
4.         last = newNode;
5.         if(last == null){
6.         head = last;
7.     }else {
8.         l.next = newNode;
9.     }
10.         size++;
11.         return true;
12. }

复制代码

时间复杂度为O(1)。
3.3 指定位置插入

在进行指定位置插入时，编程代码稍多些，原因是需要以下几步完成：

• 判断插入的位置是否超范围
  
• 若插入的位置在最后，则执行在尾结点的插入逻辑
  
• 先根据要插入的位置，查找并获取到对应位置的结点元素
  
• 然后执行插入逻辑
  

1. public boolean add(int index,Object data){
2.     if(index < 0 || index > size){
3.         return false;
4.     }
5.     if(index == size){
6.         addLast(data);
7.         return true;
8.     }else {
9.         //先找到要插入的指定位置的结点
10.         DNode x = index(index);
11.             //执行插入操作
12.         DNode prevNode = x.prev;
13.         DNode newNode = new DNode(prevNode,data,x);
14.         x.prev = newNode;
15.         if(prevNode == null){
16.             head = newNode;
17.         }else {
18.             prevNode.next = newNode;
19.         }
20.         size++;
21.     }
22. }
24. //查找index位置上的结点并返回
25. public DNode index(int index){
26.     if( index < 0 || index >= size){
27.         return null;
28.     }
29.         if( index < (size>>1)){
30.         DNode x = head;
31.         for(int i = 0; i < index; i++){
32.             x = x.next;
33.         }
34.         return x;
35.     }else {
36.         DNode x = last;
37.         for(int i = size-1; i >= index; i--){
38.             x = x.prev;
39.         }
40.         return x;
41.     }
42. }

复制代码

根据上述代码，我们可以发现插入指定位置的代码，需要用到查找指定位置的操作，先查找再插入，因此时间复杂度同样为O(n)。
4. 删除元素

有了前面的分析经验，我们可以非常自然的分析出删除操作同样分三种：删除头结点、删除尾结点、删除指定结点。接下来，一起来看看详细的情况：
4.1 删除头结点

1. public Object removeHead(){
2.     if(head == null){
3.         return null;
4.     }
5.     DNode h = head;
6.     Object data = h.data;
7.     DNode next = h.next;
8.         //将原来头结点的数据域和指针域均赋值为null置空
9.     h.data = null;
10.     h.next = null;
12.     //将当前结点的next作为新的头结点
13.     head = next;
15.     //如果next为null，则说明当前链表只有一个节点，删除该节点，则链表的first、last都为null
16.     if(next == null){
17.         last = null;
18.     }else {
19.         // next要作为新的头节点，则其prev属性为null
20.         next.prev = null;
21.     }
22.     size--;
23.     return data;
24. }

复制代码

删除头结点只涉及头结点的逻辑判断和操作，因此删除头结点时间复杂度为O(1)。
4.2 删除尾结点

与删除头结点原理相同，操作尾结点。代码如下：

1. public Object removeLast(){
2.     DNode l = last;
3.     if(l == null){
4.         return null;
5.     }
6.     Object data = l.data;
7.     DNode prev = l.prev;
8.         //将当前尾节点的属性赋值为null，为了GC清理
9.     l.data = null;
10.     l.prev = null;
11.         // 让当前尾节点的prev作为新的尾节点，赋值给last属性
12.     last = prev;
13.         // 如果prev为null，则说明当前链表只有一个节点，删除该节点，则链表的first、last都为null
14.     if(prev == null){
15.         head = null;
16.     }else {
17.         // prev要作为新的尾节点，则其next属性为null
18.         prev.next = null;
19.     }
20.     size--;
21.     return data;
22. }

复制代码

很明显，删除尾结点的时间复杂度为O(1)。
4.3 删除指定结点

删除指定结点的编码实现如下：

1. public Object remove(int index){
2.     if(index < 0 || index >= size){
3.         return null;
4.     }
5.         //首先通过查找方法，查找到
6.         DNode node = index(index;
7.         //执行删除操作
8.         Object data = node.data;
9.         DNode next = node.next;
10.         DNode prev = node.prev;
12.         // 如果prev是null，则说明删除的是当前头节点，则将next作为新的头节点，赋值给head
13.         if(prev == null){
14.         head = prev;
15.     }else {
16.         // 如果删除的不是当前头节点，则将要删除节点的prev与next连接一起，即将prev的next属性赋值成next
17.         prev.next = next;
18.         // 如果prev不是null，则赋值为null
19.         node.prev = null;
20.     }
22.         // 如果next是null，则说明删除的是当前尾节点，则将prev作为新的尾节点，赋值给last
23.         if(next == null){
24.         last = prev;
25.     }else {
26.         // 如果删除的不是当前尾节点，则将要删除节点的prev与next连接一起，即将next的prev赋值成prev
27.         next.prev = prev;
28.         // 如果next不是null，则赋值为null
29.         node.next = null;
30.     }
31.         //将要删除的结点的data数据域设置为null
32.         node.data = null;
33.         //链表的结点个数-1操作
34.         size--;
35.         return data;
36. }

复制代码

如上代码所示，删除指定位置的结点元素也需要先执行index(index)查找算法，至于index的实现，在前文介绍指定位置插入结点操作时，已经进行了实现，此处直接进行使用。
我们不难分析得到，删除指定位置的结点的时间复杂度是O(n)。
三. 其他操作

作为一种常见的数据结构，除了对自身结点元素的一些操作，还有一些对链表状态的获取，比如链表的长度，链表是否为空等，这里给大家介绍一下双向链表的一些其他操作。
1. 链表的大小(元素结点的个数)

1. public int size(){
2.     return size;
3. }

复制代码

2. 判断链表是否为空

1. public boolean isEmpty(){
2.     return size == 0;
3. }

复制代码

3. 获取链表元素组成的数组

1. public Object[] toArray(){
2.     Object[] result = new Object[size];
3.     int i = 0;
4.     for(DNode node = head; node != null; node = node.next){
5.         resunt[i++] = node.data;
6.     }
7.     return result;
8. }

复制代码

4. 清空链表

1. public void clear(){
2.     for(DNode node = head; node != null; ){
3.         DNode next = node.next;
4.         node.data = null;
5.         node.next = null;
6.         node.prev = null;
7.         node = next;
8.     }
9.     head = last = null;
10.     size = 0;
11. }

复制代码

四. 结语

至此，我们已经连续用两篇文章给大家介绍了链表的相关知识。
在上一篇文章中，我们主要介绍了链表的基础知识和单链表的常规操作， 同时辅以图示来说明各种操作情况。在本篇文章中，主要是从Java编程角度作为切入点，来进一步讲解双向链表的一些操作。 特别是本篇文章中的大量代码实践，需要大家能够理清逻辑关系，希望你可以动手练起来哦。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！