双向链表

亦凉 2022-07-18 05:29 216阅读 0赞

### 前面叙述了关于单链表、双端链表、有序链表的结点插入以及遍历查找等示例。这几种链表都只能从前往后进行遍历，反向遍历是非常麻烦的一件事。 ###

### 考虑一下下面这个情况：如果文本编辑器用链表来存储文本，当用户向下移动光标时，程序移动到下一个链结点操作新一行，假设链表每个结点存放的是一行字符串。光标向下移动前面所说的几种链表结构已经实现了。但是光标上移就显得复杂，至少在不使用双向链表的前提下没那么向下移动光标（遍历下一个Node）方便。不使用双向链表的方式是不断修改current指针，效率比较低。使用双向链表就会提高遍历效率。 ###

### 双向链表提供了前向遍历和后向遍历的能力。由于引入了前向指针，以下是双向链表的示意图： ###

![这里写图片描述][20160906211643131]

### 从上图可以看出，双向链表有两个引用指向null,第一个节点的pre引用和最后一个节点的next引用。这两个null是判断前向遍历和后向遍历结束的标志。 ###

### **创建双向链表结点** ###

class Link5
    {
    public long dData;                 
    public Link5 next;                
    public Link5 previous;             
    
    public Link5(long d)                
       { 
       dData = d; 
       }
    public void displayLink()        
       { 
           System.out.print(dData + " "); 
       }
    
    }

### 双向链表每次插入或者删除一个节点以后需要处理四个链结点的引用，这是比单链表复杂之处。两个引用连接前一个node，两个引用连接后一个node。 ###

### **从链表头部插入node：** ###

public void insertFirst(long dd) 
       {
       Link5 newLink = new Link5(dd);   
    
       if( isEmpty() )  //判断first==null即链表为空              
          last = newLink;             
       else
          first.previous = newLink;   
       newLink.next = first;         
       first = newLink;               
       }

### **以上过程可以用以下示意图标志**： ###

![这里写图片描述][20160906213415138]

### 需要注意的是如果链表是null则last字段必须改变，这样已形成了一个双端队列。 ###

### **从链表尾部插入Node与以上步骤相一致**。 ###

public void insertLast(long dd)   
       {
       Link5 newLink = new Link5(dd);  
       if( isEmpty() )                
          first = newLink;            
       else
          {
          last.next = newLink;  //添加前一个节点的next引用      
          newLink.previous = last; //添加该节点的previous引用   
          }
       last = newLink;  //last指向最后一个节点              
       }

### **在指定位置插入Node** ###

### 除了以上在链表头部和tail添加Node，有时候还可以在某一项特定的数据项后面插入一个Node。 ###

public boolean insertAfter(long key, long dd)
       {                            
       Link5 current = first;          
       while(current.dData != key)//从前往后搜索该关键字key    
          {
          current = current.next;     
          if(current == null)
             return false;            
          }
        //找到了该关键字key,进行添加数据项
       Link5 newLink = new Link5(dd);  
    
       if(current==last)    //在链表最后一项进行添加？          
          {
          newLink.next = null;        
          last = newLink;             
          }
       else                           
          {
          newLink.next = current.next;                           
          current.next.previous = newLink;
          }
       newLink.previous = current;    
       current.next = newLink;        
       return true;                   
       }

### 以下是删除Node代码，同样删除节点也可以从first和last开始删除。 ###

public Link5 deleteFirst()         
       {                             
       Link5 temp = first;
       if(first.next == null)        
          last = null;               
       else
          first.next.previous = null; //从first处删除节点后将first指向的节点previous引用置为null
       first = first.next;            
       return temp;
       }
    //-------------------------------------------------------------
    public Link5 deleteLast()          
       {                             
       Link5 temp = last;
       if(first.next == null)         
          first = null;               
       else
          last.previous.next = null; //从last处开始删除Node后需要将last引用的Node的next引用指向null
       last = last.previous;          
       return temp;
       }

### **从任意位置删除Node** ###

public Link5 deleteKey(long key)   
       {                              
       Link5 current = first;          
       while(current.dData != key)    
          {
          current = current.next;     
          if(current == null)
             return null;             
          }
       if(current==first)  //找到了关键字key 如果删除的是第一个Node           
          first = current.next;       
       else                                                       
          current.previous.next = current.next;//将被删除那个节点前面的节点next引用指向被删除节点的后面那个节点
    
       if(current==last)              
          last = current.previous;   
       else                           
    
          current.next.previous = current.previous;//将被删除那个节点后面那个节点的previous引用指向被删除那个节点前面那个几点
       return current;               
       }

### **在任意位置删除节点的核心操作语句是以下代码**： ###

current.previous.next = current.next;
    current.next.previous = current.previous;

### **以上操作可以用以下示意图表示**： ###

![这里写图片描述][20160906220011416]

### **关于遍历** ###

### 遍历链表是链表操作的一个重要环节。双向链表含有前向和反向遍历。 ###

### **前向遍历** ###

public void displayForward()
       {
       System.out.print("List (first-->last): ");
       Link5 current = first;          
       while(current != null)        
          {
          current.displayLink();     
          current = current.next;     
          }
       System.out.println("");
       }

### **反向遍历** ###

public void displayBackward()
       {
       System.out.print("List (last-->first): ");
       Link5 current = last;           
       while(current != null)         
          {
          current.displayLink();      
          current = current.previous; 
          }
       System.out.println("");
       }

## **测试双向链表** ##

DoublyLinkedList theList = new DoublyLinkedList();
    
       theList.insertFirst(22);//从链表first处开始插入Node     
       theList.insertFirst(44);
       theList.insertFirst(66);
    
       theList.insertLast(11); //从链表last处开始添加Node     
       theList.insertLast(33);
       theList.insertLast(55);
    
       theList.displayForward(); //前向遍历链表  
       theList.displayBackward();//反向遍历链表    
    
       theList.deleteFirst();  //从first删除一个Node      
       theList.deleteLast();   //从last处删除一个Node     
       theList.deleteKey(11);  //删除数据项关键字是11的Node     
    
       theList.displayForward();   //前向遍历链表  
    
       theList.insertAfter(22, 77); //在数据项是22的节点再插入一个Node，其数据项是77
       theList.insertAfter(33, 88); //在数据项是33的节点后再插入一个Node，其数据项是88
    
       theList.displayForward();  //前向显示链表Node数据项

### **测试结果：** ###

List (first-->last): 66 44 22 11 33 55 
    List (last-->first): 55 33 11 22 44 66 
    List (first-->last): 44 22 33 
    List (first-->last): 44 22 77 33 88

### 以上实验结果表明双向链表比单向链表功能更多一些，使用更灵活。以上其实是一种带双端链表的双向链表，这种双向链表可以实现双端队列。另外在以上代码中，在删除Node时需要检查链表是否为空，这样才更严谨。 ###

[20160906211643131]: /images/20220717/fcf67515b5fc4f3abbe94300605c08e8.png
[20160906213415138]: /images/20220717/3d04e6ea618b4ac79cc60e12966469c0.png
[20160906220011416]: /images/20220717/8cd635007bcb48379653f7e455917195.png