詳解java數(shù)據(jù)結(jié)構(gòu)與算法之雙鏈表設(shè)計(jì)與實(shí)現(xiàn)

更新時(shí)間：2017年06月21日 11:17:50 作者：zejian_

本篇文章主要介紹了詳解java數(shù)據(jù)結(jié)構(gòu)與算法之雙鏈表設(shè)計(jì)與實(shí)現(xiàn)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

在單鏈表分析中，我們可以知道每個(gè)結(jié)點(diǎn)只有一個(gè)指向后繼結(jié)點(diǎn)的next域，倘若此時(shí)已知當(dāng)前結(jié)點(diǎn)p，需要查找其前驅(qū)結(jié)點(diǎn)，那么就必須從head頭指針遍歷至p的前驅(qū)結(jié)點(diǎn)，操作的效率很低，因此如果p有一個(gè)指向前驅(qū)結(jié)點(diǎn)的next域，那效率就高多了，對(duì)于這種一個(gè)結(jié)點(diǎn)中分別包含了前驅(qū)結(jié)點(diǎn)域pre和后繼結(jié)點(diǎn)域next的鏈表，稱之為雙鏈表。本篇我們將從以下結(jié)點(diǎn)來(lái)分析雙鏈表

雙鏈表的設(shè)計(jì)與實(shí)現(xiàn)

雙鏈表的主要優(yōu)點(diǎn)是對(duì)于任意給的結(jié)點(diǎn)，都可以很輕易的獲取其前驅(qū)結(jié)點(diǎn)或者后繼結(jié)點(diǎn)，而主要缺點(diǎn)是每個(gè)結(jié)點(diǎn)需要添加額外的next域，因此需要更多的空間開銷，同時(shí)結(jié)點(diǎn)的插入與刪除操作也將更加耗時(shí)，因?yàn)樾枰嗟闹羔樦赶虿僮?。雙鏈表的結(jié)構(gòu)圖如下：

創(chuàng)建HeadDoubleILinkedList類并實(shí)現(xiàn)IlinekedList接口(和上篇博文的接口一樣)

/**
 * Created by zejian on 2016/10/23.
 * 雙鏈表的實(shí)現(xiàn),帶頭結(jié)點(diǎn)(不帶數(shù)據(jù))的雙鏈表,為了更高的效率該類包含指向尾部的指針tail
 */
public class HeadDoubleILinkedList<T> implements ILinkedList<T> {

  protected DNode<T> head; //不帶數(shù)據(jù)的頭結(jié)點(diǎn)
  protected DNode<T> tail; //指向尾部的指針

  public HeadDoubleILinkedList(){
    //初始化頭結(jié)點(diǎn)
    this.head =this.tail= new DNode<>();     
  }
  //先省略其他代碼
  ........
}

結(jié)點(diǎn)類結(jié)構(gòu)如下：

package com.zejian.structures.LinkedList.doubleLinked;

/**
 * Created by zejian on 2016/10/23.
 * 雙鏈表結(jié)點(diǎn)
 */
public class DNode<T> {

  public T data;
  public DNode<T> prev, next;//前繼指針和后繼指針
  public DNode(T data, DNode<T> prev, DNode<T> next)
  {
    this.data = data;
    this.prev = prev;
    this.next = next;
  }

  public DNode(T data)
  {
    this(data, null, null);
  }

  public DNode()
  {
    this(null, null, null);
  }

  public String toString()
  {
    return this.data.toString();
  }
}

通過(guò)上篇的分析，我們對(duì)鏈表的插入、刪除、查找、替換等操作也比較熟悉了，因此針對(duì)雙鏈表的實(shí)現(xiàn)，主要分析其插入、刪除、查找、替換等方法，其他沒有分析的看實(shí)現(xiàn)源碼即可（最后會(huì)給出雙鏈表的實(shí)現(xiàn)代碼）

雙鏈表的插入操作分析與實(shí)現(xiàn)

我們先來(lái)看看雙鏈表的插入，雖然有不帶數(shù)據(jù)的頭結(jié)點(diǎn)，但是由于是雙向鏈表，所以在插入雙鏈表時(shí)需分兩種情況，一種是在插入空雙鏈表和尾部插入，另一種是雙鏈表的中間插入，如下圖在空雙鏈表插入值x：

從圖可以看出（a）和（b）屬于同種情況，需要注意front.next != null的情況，否則就會(huì)拋空指針，而（c）的情況屬于中間插入無(wú)需無(wú)需理會(huì)front.next != null的條件，因?yàn)橹虚g插入時(shí)無(wú)論如何其后繼結(jié)點(diǎn)時(shí)不會(huì)為null的，插入方法的實(shí)現(xiàn)代碼如下：

/**
 * 插入結(jié)點(diǎn)
 * @param index
 * @param data
 * @return
 */
@Override
public boolean add(int index, T data) {
  if(index<0||data==null)
    throw new NullPointerException("index < 0 || data == null");

    int j = 0;
    DNode<T> front = this.head;
    //查找要插入結(jié)點(diǎn)位置的前一個(gè)結(jié)點(diǎn)
    while (front.next != null && j < index) {
      j++;
      front = front.next;
    }

    //創(chuàng)建需要插入的結(jié)點(diǎn),并讓其前繼指針指向front,后繼指針指向front.next
    DNode<T> q = new DNode<T>(data, front, front.next);

    //空雙鏈表插入和尾部插入，無(wú)需此操作
    if(front.next != null) {
      //更改front.next的前繼指針
      front.next.prev = q;
    }
    //更改front的后繼指針
    front.next = q;

    //在尾部插入時(shí)需要注意更新tail指向
    if(front==this.tail){
      this.tail=q;
    }
    return true;
}

雙鏈表的刪除操作分析與實(shí)現(xiàn)

雙鏈表的刪除操作與插入操作原理上是相似的，我們可以看出（a）（b）是屬于同種情況，需要防止 p.next.prev拋空指針的情況，而對(duì)于（c）情況則無(wú)需關(guān)系 p.next.prev的值，刪除的具體實(shí)現(xiàn)如下：

/**
 * 根據(jù)下標(biāo)刪除結(jié)點(diǎn)
 * 1.頭刪除
 * 2.中間刪除
 * 3.尾部刪除,更新tail指向
 * @param index 下標(biāo)起始值為0
 * @return
 */
 @Override
 public T remove(int index) {

   int size=length();
   T temp=null;

   if(index<0||index>=size||isEmpty()){
     return temp;
   }

   DNode<T> p=this.head;
   int j=0;
   //頭刪除/尾刪除/中間刪除,查找需要?jiǎng)h除的結(jié)點(diǎn)(要?jiǎng)h除的當(dāng)前結(jié)點(diǎn)因此i<=index)
   while (p!=null&&j<=index){
     p=p.next;
     j++;
   }
   //當(dāng)雙鏈表只有一個(gè)結(jié)點(diǎn)時(shí)或尾部刪除時(shí),無(wú)需此步
   if(p.next!=null){
     p.next.prev=p.prev;
   }
   p.prev.next=p.next;
   //如果是尾結(jié)點(diǎn)
   if (p==this.tail) {
     this.tail = p.prev;//更新未結(jié)點(diǎn)的指向
   }
   temp=p.data;

   return temp;
 }

雙鏈表的查值操作分析與實(shí)現(xiàn)

雙鏈表的查找值的操作與單鏈表并沒有什么區(qū)別，只要找到需要查找的當(dāng)前結(jié)點(diǎn)獲取其值即可，如下：

代碼實(shí)現(xiàn)如下：

@Override
public T get(int index) {
  if (index>=0)
  {
    int j=0;
    //注意起始結(jié)點(diǎn)為this.head.next
    //如果起始點(diǎn)為this.head時(shí)，j的判斷為j<=index，
    //因?yàn)樾枰獙ふ业氖钱?dāng)前結(jié)點(diǎn)而不是前一個(gè)結(jié)點(diǎn)。
    DNode<T> pre=this.head.next;
    while (pre!=null && j<index)
    {
      j++;
      pre=pre.next;
    }
    if (pre!=null)
      return pre.data;
  }
  return null;
}

雙鏈表的替換值操作分析與實(shí)現(xiàn)

雙鏈表的替換值過(guò)程，需要先查找到需要替換的結(jié)點(diǎn)，這個(gè)過(guò)程跟獲取值的過(guò)程是一樣的，找到結(jié)點(diǎn)后直接替換值并返回舊值即可。比較簡(jiǎn)單直接上代碼：

@Override
public T set(int index, T data) {
  T old=null;
  if (index>0&&data!=null){
    int j=0;
    DNode<T> pre =this.head.next;
    //查找需要替換的位置
    while (pre!=null&&j<index){
      j++;
      pre=pre.next;
    }
    if (pre!=null){
      old=pre.data;
      //替換數(shù)據(jù)
      pre.data=data;
    }
  }
  return old;
}

ok~，到此雙鏈表的主要操作實(shí)現(xiàn)已分析完，下面給出雙鏈表的實(shí)現(xiàn)源碼：

package com.zejian.structures.LinkedList.doubleLinked;

import com.zejian.structures.LinkedList.ILinkedList;

/**
* Created by zejian on 2016/10/23.
* 雙鏈表的實(shí)現(xiàn),帶頭結(jié)點(diǎn)(不帶數(shù)據(jù))的雙鏈表,為了更高的效率該類包含指向尾部的指針tail
*/
public class HeadDoubleILinkedList<T> implements ILinkedList<T> {

 protected DNode<T> head; //不帶數(shù)據(jù)的頭結(jié)點(diǎn)
 protected DNode<T> tail; //指向尾部的指針

 public HeadDoubleILinkedList(){
   this.head =this.tail= new DNode<>();     //初始化頭結(jié)點(diǎn)
 }


 /**
 * 傳入一個(gè)數(shù)組,轉(zhuǎn)換成鏈表
 * @param array
 */
 public HeadDoubleILinkedList(T[] array)
 {
   this();
   if (array!=null && array.length>0)
   {
     this.head.next = new DNode<T>(array[0]);
     tail =this.head.next;
     tail.prev=this.head;
     int i=1;
     while (i<array.length)
     {
       tail.next=new DNode<T>(array[i++]);
       tail.next.prev=tail;
       tail = tail.next;
     }
   }
 }

 @Override
 public boolean isEmpty() {
   return head.next==null;
 }


 @Override
 public int length() {
   int length=0;
   DNode<T> pre=head.next;
   while (pre!=null){
     length++;
     pre=pre.next;
   }
   return length;
 }


 @Override
 public T get(int index) {
   if (index>=0)
   {
     int j=0;
     DNode<T> pre=this.head.next;
     while (pre!=null && j<index)
     {
       j++;
       pre=pre.next;
     }
     if (pre!=null)
       return pre.data;
   }
   return null;
 }


 @Override
 public T set(int index, T data) {
   T old=null;
   if (index>0&&data!=null){
     int j=0;
     DNode<T> pre =this.head.next;
     //查找需要替換的位置
     while (pre!=null&&j<index){
       j++;
       pre=pre.next;
     }
     if (pre!=null){
       old=pre.data;
       //替換數(shù)據(jù)
       pre.data=data;
     }
   }
   return old;
 }

 /**
 * 插入結(jié)點(diǎn)
 * @param index
 * @param data
 * @return
 */
 @Override
 public boolean add(int index, T data) {
   if(index<0||data==null)
     throw new NullPointerException("index < 0 || data == null");

     int j = 0;
     DNode<T> front = this.head;
     //查找要插入結(jié)點(diǎn)位置的前一個(gè)結(jié)點(diǎn)
     while (front.next != null && j < index) {
       j++;
       front = front.next;
     }

     //創(chuàng)建需要插入的結(jié)點(diǎn),并讓其前繼指針指向front,后繼指針指向front.next
     DNode<T> q = new DNode<T>(data, front, front.next);

     //空雙鏈表插入,需要確保front.next不為空
     if(front.next != null) {
       //更改front.next的前繼指針
       front.next.prev = q;
     }
     //更改front的后繼指針
     front.next = q;

     //在尾部插入時(shí)需要注意更新tail指向
     if(front==this.tail){
       this.tail=q;
     }

     return true;
 }

 /**
 * 尾部添加
 * @param data
 * @return
 */
 @Override
 public boolean add(T data) {
   if (data==null)
     return false;
   //創(chuàng)建新結(jié)點(diǎn),并把其前繼指針指向tail
   DNode<T> q = new DNode<T>(data, tail, null);
   tail.next=q;
   //更新尾部結(jié)點(diǎn)
   this.tail=q;
   return true;
 }

 /**
 * 根據(jù)下標(biāo)刪除結(jié)點(diǎn)
 * 1.頭刪除
 * 2.中間刪除
 * 3.尾部刪除,更新tail指向
 * @param index 下標(biāo)起始值為0
 * @return
 */
 @Override
 public T remove(int index) {

   int size=length();
   T temp=null;

   if(index<0||index>=size||isEmpty()){
     return temp;
   }

   DNode<T> p=this.head;
   int j=0;
   //頭刪除/尾刪除/中間刪除,查找需要?jiǎng)h除的結(jié)點(diǎn)(要?jiǎng)h除的當(dāng)前結(jié)點(diǎn)因此i<=index)
   while (p!=null&&j<=index){
     p=p.next;
     j++;
   }
   //當(dāng)鏈表只要一個(gè)結(jié)點(diǎn)時(shí),無(wú)需此步
   if(p.next!=null){
     p.next.prev=p.prev;
   }
   p.prev.next=p.next;
   //如果是尾結(jié)點(diǎn)
   if (p==this.tail) {
     this.tail = p.prev;//更新未結(jié)點(diǎn)的指向
   }
   temp=p.data;

   return temp;
 }

 /**
 * 根據(jù)data刪除結(jié)點(diǎn),無(wú)需像單向鏈表那樣去存儲(chǔ)要?jiǎng)h除結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)
 * 1.頭刪除
 * 2.中間刪除
 * 3.尾部刪除,更新tail指向
 * @param data
 * @return
 */
 @Override
 public boolean removeAll(T data) {

   boolean isRemove=false;

   if(data==null||isEmpty())
     return isRemove;

   //注意這里的起點(diǎn),如果起點(diǎn)為this.head,那么情況區(qū)別如同前面的根據(jù)index的刪除實(shí)現(xiàn)
   DNode<T> p=this.head.next;

   //頭刪除/尾刪除/中間刪除(size>1),查找所有需要?jiǎng)h除的結(jié)點(diǎn)
   while (p!=null){

     if(data.equals(p.data)){
       if (p==this.tail){
         //如果是尾結(jié)點(diǎn)
         this.tail=p.prev;//更新未結(jié)點(diǎn)的指向
         p.prev=null;
         this.tail.next=null;
       }else {
         //如果是在中間刪除,更新前繼和后繼指針指向
         p.prev.next=p.next;
         p.next.prev=p.prev;
       }
       isRemove=true;
       p=p.next;//繼續(xù)查找
     }else {
       p=p.next;
     }

   }
   return isRemove;
 }

 /**
 * 清空鏈表
 */
 @Override
 public void clear() {
   this.head.next=null;
   this.tail=this.head;
 }


 @Override
 public boolean contains(T data) {

   if(data==null){
     return false;
   }

   DNode<T> p=this.head.next;
   while (p!=null){
     if (data.equals(p.data)){
       return true;
     }else {
       p=p.next;
     }
   }

   return false;
 }

 @Override
 public String toString() {
   String str="(";
   DNode<T> pre = this.head.next;
   while (pre!=null)
   {
     str += pre.data;
     pre = pre.next;
     if (pre!=null)
       str += ", ";
   }
   return str+")";
 }

 public static void main(String[] args){

   String[] letters={"A","B","C","D","Z","E","F"};
//    String[] letters={"A"};
   HeadDoubleILinkedList<String> list=new HeadDoubleILinkedList<>(letters);

   System.out.println("list.get(3)->"+list.get(3));
   System.out.println("list:"+list.toString());

   System.out.println("list.add(4,Y)—>"+list.add(0,"Y"));
   System.out.println("list:"+list.toString());
   System.out.println("list.add(Z)—>"+list.add("Z"));
   System.out.println("list:"+list.toString());


   System.out.println("list.contains(Z)->"+list.contains("Z"));
   System.out.println("list.set(4,P)-->"+list.set(4,"P"));
   System.out.println("list:"+list.toString());


   System.out.println("list.remove(6)-->"+list.remove(6));
//    System.out.println("list.remove(Z)->"+list.removeAll("Z"));
   System.out.println("list:"+list.toString());
 }
}

循環(huán)雙鏈表的設(shè)計(jì)與實(shí)現(xiàn)

如果雙鏈表的最后一個(gè)結(jié)點(diǎn)的next指針域指向頭結(jié)點(diǎn)，而頭結(jié)點(diǎn)的prev指針指向頭最后一個(gè)結(jié)點(diǎn)，則構(gòu)成了雙鏈表（Circular Doubly LinkedList），其結(jié)構(gòu)如下圖示：

在循環(huán)雙鏈表中我們不再需要尾指向結(jié)點(diǎn)，因?yàn)檎麄€(gè)鏈表已構(gòu)成循環(huán)，在頭結(jié)點(diǎn)head的位置也可以輕松獲取到尾部結(jié)點(diǎn)的位置。對(duì)于循環(huán)雙鏈表的插入、刪除操作也無(wú)需區(qū)分位置操作的情況，這是由于循環(huán)雙鏈表的本身的特殊性，使p.next.pre永遠(yuǎn)不可能為null，因此我們?cè)诓迦牒蛣h除時(shí)代碼實(shí)現(xiàn)相對(duì)簡(jiǎn)單些。下面我們先分析一下循環(huán)雙鏈表的插入操作，圖示如下：

我們可以看出（a）（b）（c）三種情況都無(wú)需關(guān)系位置插入的區(qū)別，其代碼實(shí)現(xiàn)如下：

/**
 * 根據(jù)index插入
 * 循環(huán)鏈表中無(wú)論是prev還是next都不存在空的情況,因此添加時(shí)
 * 無(wú)論是頭部還是尾部還是中,都視為一種情況對(duì)待
 * @param index
 * @param data
 * @return
 */
@Override
public boolean add(int index, T data) {
  int size=length();
  if(data==null||index<0||index>=size)
    return false;

  int j=0;
  DNode<T> p=this.head;
  //尋找插入點(diǎn)的位置
  while (p.next!=head&&j<index){
    p=p.next;
    j++;
  }

  //創(chuàng)建新結(jié)點(diǎn),如果index=3,那么插入的位置就是第4個(gè)位置
  DNode<T> q=new DNode<>(data,p,p.next);
  p.next=q;
  p.next.prev=q;

  return true;
}

循環(huán)雙鏈表的刪除操作圖示如下：

雙鏈表的刪除操作圖示

同樣地，從圖中我們也可以發(fā)現(xiàn)由于循環(huán)雙鏈表的特性，（a）（b）（c）三種情況都無(wú)需區(qū)分操作位置，其代碼實(shí)現(xiàn)如下：

@Override
public T remove(int index) {
  T old = null;
  int size=length();

  if (index<0||index>=size)
    return old;

  int j=0;
  DNode<T> p=this.head.next;

  while (p!=head && j<index)
  {
    j++;
    p = p.next;
  }

  if (p!=head)
  {
    old = p.data;
    p.prev.next = p.next;
    p.next.prev = p.prev;
  }
  return old;
}

至于循環(huán)雙鏈表的查找值、替換值等操作與雙鏈表并沒有多大的區(qū)別，但是需要特別注意的是在遍歷循環(huán)雙鏈表時(shí)，結(jié)束標(biāo)志不再是尾部結(jié)點(diǎn)是否為空，而是尾結(jié)點(diǎn)的next指針是否指向頭結(jié)點(diǎn)head。好~，下面我們給出循環(huán)雙鏈表的實(shí)現(xiàn)代碼：

package com.zejian.structures.LinkedList.doubleLinked;

import com.zejian.structures.LinkedList.ILinkedList;

/**
* Created by zejian on 2016/10/24.
* 循環(huán)雙鏈表,帶空頭結(jié)點(diǎn)(不含數(shù)據(jù)),循環(huán)鏈表可以不需要尾部指針
*/
public class LoopHeadDILinkedList<T> implements ILinkedList<T> {

 protected DNode<T> head; //不帶數(shù)據(jù)的頭結(jié)點(diǎn)
//  protected DNode<T> tail; //指向尾部的指針

 public LoopHeadDILinkedList(){
   this.head = new DNode<>();//初始化頭結(jié)點(diǎn)
   this.head.next=head;
   this.head.prev=head;

 }

 

 /**
 * 傳入一個(gè)數(shù)組,轉(zhuǎn)換成鏈表
 * @param array
 */
 public LoopHeadDILinkedList(T[] array)
 {
   this();
   if (array!=null && array.length>0)
   {
     DNode<T> p= new DNode<>(array[0]);
     head.next=p;
     head.prev=p;
     p.prev=head;
     p.next=head;

     int i=1;
     while (i<array.length)
     {
       p.next=new DNode<>(array[i++],p,head);
       head.prev=p.next;
       p=p.next;
     }
   }
 }

 

 @Override
 public boolean isEmpty() {
   return this.head.next==head;//循環(huán)雙鏈表的后繼指針指向自己說(shuō)明是空鏈表
 }

 @Override
 public int length() {

   int length=0;
   DNode<T> p=this.head.next;
   while (p!=this.head){
     length++;
     p=p.next;
   }
   return length;
 }

 @Override
 public T get(int index) {

   if (index>=0)
   {
     int j=0;
     DNode<T> p=this.head.next;
     while (p!=head && j<index)
     {
       j++;
       p=p.next;
     }
     if (p!=head)
       return p.data;
   }
   return null;
 }

 /**
 * 根據(jù)index修改data
 * @param index
 * @param data
 * @return 返回被替換的data
 */
 @Override
 public T set(int index, T data) {

   if (data==null){
     return null;
   }

   if(index>=0){
     int j=0;
     DNode<T> p=this.head.next;

     while (p!=head&&j<index){
       j++;
       p=p.next;
     }

     //如果不是頭結(jié)點(diǎn)
     if(p!=head){
       T old = p.data;
       p.data=data;

       return old;
     }
   }

   return null;
 }

 /**
 * 根據(jù)index添加
 * 循環(huán)鏈表中無(wú)論是prev還是next都不存在空的情況,因此添加時(shí)
 * 無(wú)論是頭部還是尾部還是中,都視為一種情況對(duì)待
 * @param index
 * @param data
 * @return
 */
 @Override
 public boolean add(int index, T data) {
   int size=length();
   if(data==null||index<0||index>=size)
     return false;

   int j=0;
   DNode<T> p=this.head;
   //尋找插入點(diǎn)的位置
   while (p.next!=head&&j<index){
     p=p.next;
     j++;
   }

   //創(chuàng)建新結(jié)點(diǎn),如果index=3,那么插入的位置就是第4個(gè)位置
   DNode<T> q=new DNode<>(data,p,p.next);
   p.next=q;
   p.next.prev=q;

   return true;
 }

 /**
 * 尾部添加
 * @param data
 * @return
 */
 @Override
 public boolean add(T data) {

   if(data==null)
     return false;
   //創(chuàng)建新結(jié)點(diǎn),讓前繼指針指向head.pre,后繼指針指向head
   DNode<T> p=new DNode<>(data,head.prev,head);
   //更新tail后繼指針的指向
   this.head.prev.next=p;
   this.head.prev=p;

   return true;
 }

 @Override
 public T remove(int index) {
   T old = null;
   int size=length();

   if (index<0||index>=size)
     return old;

   int j=0;
   DNode<T> p=this.head.next;

   while (p!=head && j<index)
   {
     j++;
     p = p.next;
   }

   if (p!=head)
   {
     old = p.data;
     p.prev.next = p.next;
     p.next.prev = p.prev;
   }

   return old;
 }

 @Override
 public boolean removeAll(T data) {
   boolean isRemove=false;

   if(data==null){
     return isRemove;
   }

   DNode<T> p=this.head.next;
   while (p!=head){
     if(data.equals(p.data)){
       p.prev.next=p.next;
       p.next.prev=p.prev;
       isRemove=true;
     }
     p=p.next;
   }

   return isRemove;
 }

 @Override
 public void clear() {
   this.head.prev = head;
   this.head.next = head;
 }

 @Override
 public boolean contains(T data) {

   if (data==null){
    return false;
   }

   DNode<T> p=this.head.next;

   while (p!=head){
     if(data.equals(p.data)){
       return false;
     }

     p=p.next;
   }

   return false;
 }

 @Override
 public String toString()
 {
   String str="(";
   DNode<T> p = this.head.next;
   while (p!=head)
   {
     str += p.data.toString();
     p = p.next;
     if (p!=head)
       str += ", ";
   }
   return str+")";
 }
 public static void main(String[] args){

   String[] letters={"A","B","C","D","Z","E","F"};
   LoopHeadDILinkedList<String> list=new LoopHeadDILinkedList<>(letters);

   System.out.println("init list-->"+list.toString());

   System.out.println("list.get(3)->"+list.get(3));
   System.out.println("list:"+list.toString());

   System.out.println("list.add(4,Y)—>"+list.add(4,"Y"));
   System.out.println("list:"+list.toString());
   System.out.println("list.add(Z)—>"+list.add("Z"));
   System.out.println("list:"+list.toString());


   System.out.println("list.contains(Z)->"+list.contains("Z"));
   System.out.println("list.set(4,P)-->"+list.set(4,"P"));
   System.out.println("list:"+list.toString());


   System.out.println("list.remove(3)-->"+list.remove(3));
   System.out.println("list.remove(Z)->"+list.removeAll("Z"));
   System.out.println("list:"+list.toString());
 }
}

排序循環(huán)雙鏈表的實(shí)現(xiàn)

所謂的排序循環(huán)雙鏈表指的是在插入元素時(shí)，不再根據(jù)index標(biāo)志，而是根據(jù)值的大小尋找插入位置，但是有個(gè)插入值data必須是T或者T的父類而且實(shí)現(xiàn)了Comoarable接口。排序循環(huán)雙鏈表的實(shí)現(xiàn)比較簡(jiǎn)單，我們只需繼承前面的循環(huán)雙鏈表并重寫add方法即可，主要代碼實(shí)現(xiàn)如下：

package com.zejian.structures.LinkedList.doubleLinked;

/**
* Created by zejian on 2016/11/6.
* 升序排序鏈表，繼承LoopHeadDILinkedList
*/
public class SortLoopHeadDIlinkedList<T extends Comparable<? extends T>> extends LoopHeadDILinkedList<T> {
 /**
  * 順序插入
  * @param data
  * @return
  */
 @Override
 public boolean add(T data) {

   if(data==null||!(data instanceof Comparable))
     throw new NullPointerException("data can\'t be null or data instanceof Comparable must be true");

   Comparable cmp =data;//這里需要轉(zhuǎn)一下類型,否則idea編輯器上檢驗(yàn)不通過(guò).

   //如果data值比最后一個(gè)結(jié)點(diǎn)大,那么直接調(diào)用父類方法,在尾部添加.
   if(this.isEmpty() || cmp.compareTo(this.head.prev.data) > 0){
     return super.add(data);
   }

   DNode<T> p=this.head.next;
   //查找插入點(diǎn)
   while (p!=head&&cmp.compareTo(p.data)>0)
     p=p.next;

   DNode<T> q=new DNode<>(data,p.prev,p);
   p.prev.next=q;
   p.prev=q;

   return true;
 }

 public static void main(String[] args){
   SortLoopHeadDIlinkedList<Integer> list=new SortLoopHeadDIlinkedList<>();
   list.add(50);
   list.add(40);
   list.add(80);
   list.add(20);
   System.out.println("init list-->"+list.toString());
 }
}

雙鏈表的執(zhí)行效率分析

其實(shí)上一篇已分析得差不多了，這里再簡(jiǎn)單說(shuō)明一下，鏈表在插入和刪除元素時(shí)執(zhí)行效率比較高，從插入操作來(lái)看，我們假設(shè)front指向的是雙向鏈表中的一個(gè)結(jié)點(diǎn)，此時(shí)插入front的后繼結(jié)點(diǎn)或者是前驅(qū)結(jié)點(diǎn)所消耗的時(shí)間為常數(shù)時(shí)間O(1),這點(diǎn)在插入front的前驅(qū)結(jié)點(diǎn)的效率比單鏈表有所改善，無(wú)需從頭結(jié)點(diǎn)開始遍歷，但是上述都是從已知雙向鏈表中front結(jié)點(diǎn)的情況下討論的。如果從實(shí)現(xiàn)代碼的操作上看，無(wú)論是插入還是刪除，都需要查找插入結(jié)點(diǎn)或刪除結(jié)點(diǎn)，而這個(gè)過(guò)程訪問(wèn)結(jié)點(diǎn)所花費(fèi)的時(shí)間的是O(n)，因此雙鏈表的插入或刪除操作或是查值操作，其時(shí)間復(fù)雜度都為O(n),至于為什么說(shuō)鏈表更適合插入刪除，這點(diǎn)上一篇我們已討論過(guò)，這里就不重復(fù)了。最后給出一張關(guān)于鏈表、數(shù)組、動(dòng)態(tài)數(shù)組的比較表：

傳遞參數(shù)	鏈表	動(dòng)態(tài)數(shù)組
索引	O(n)	O(1)
在最前端插入或刪除	O(1)	O(n)
在最末端插入	O(n)	O(1),如果數(shù)組空間沒有被填滿;O(n),如果數(shù)組空間已填滿
在最末端刪除	O(n)	O(1)
在中間插入	O(n)	O(n)
在中間刪除	O(n)	O(n)
空間浪費(fèi)	O(n)	O(n)

異或高效存儲(chǔ)雙鏈表的設(shè)計(jì)原理概要

在上述分析的雙鏈表的實(shí)現(xiàn)中，都是需要一個(gè)指向后繼結(jié)點(diǎn)的正向指針和一個(gè)指向前驅(qū)結(jié)點(diǎn)的反向指針，出于此點(diǎn)的考慮，我們需要在構(gòu)造一個(gè)結(jié)點(diǎn)類時(shí)需要一個(gè)數(shù)據(jù)域data、一個(gè)指向后繼結(jié)點(diǎn)的指針next以及一個(gè)指向前驅(qū)結(jié)點(diǎn)的指針prev。但為了設(shè)計(jì)更高效節(jié)省存儲(chǔ)空間，一種基于指針差運(yùn)算存儲(chǔ)高效的雙向鏈表就誕生了。這種鏈表的每個(gè)結(jié)點(diǎn)仍然與單鏈表一樣僅使用一個(gè)指針域來(lái)設(shè)計(jì)雙向鏈表，新的雙向鏈表結(jié)點(diǎn)類結(jié)構(gòu)如下：

package com.zejian.structures.LinkedList.XORLinked;

/**
 * Created by zejian on 2016/11/6.
 * 異或結(jié)點(diǎn)
 */
public class XORNode<T> {
  public T data;
  public XORNode<T> ptrdiff;//異或指針

  public XORNode() {
  }

  public XORNode(T data, XORNode<T> ptrdiff) {
    this.data = data;
    this.ptrdiff = ptrdiff;
  }
}

其中的ptrdiff字段存儲(chǔ)了后繼結(jié)點(diǎn)與前驅(qū)結(jié)點(diǎn)的地址差，指針的差通過(guò)異或運(yùn)行（對(duì)異或不熟悉的可以看博主的另一篇文章：java運(yùn)算符）來(lái)實(shí)現(xiàn)的，我們這里使用⊕表示異或操作，則有如下計(jì)算：

pridiff=后繼結(jié)點(diǎn)的地址⊕前驅(qū)結(jié)點(diǎn)的地址

如上圖，我們采用異或差值來(lái)計(jì)算各個(gè)結(jié)點(diǎn)的位置：

A的next域?yàn)閔ead⊕B
B的next域?yàn)锳⊕C
C的next域?yàn)锽⊕D
D的next域?yàn)镃⊕NULL

那么為什么可以這么計(jì)算呢？我們先來(lái)了解一下異或的特性：

X⊕X=0
X⊕0=X
X⊕Y=Y⊕X
(X⊕Y)⊕Z=X⊕(Y⊕Z)

所以我們可以很容易利用上述的異或特性找到結(jié)點(diǎn)的對(duì)象，比如指向P想從結(jié)點(diǎn)C移動(dòng)到結(jié)點(diǎn)B，已知C的ptrdiff值為B⊕D,那么就需要將結(jié)點(diǎn)C的ptrdiff的值與結(jié)點(diǎn)D的地址執(zhí)行異或運(yùn)算，這時(shí)就可以得到B的地址了，計(jì)算過(guò)程如下：

(B ⊕ D) ⊕ D = B ⊕(D ⊕ D) = B ⊕ 0 =B

如果想從C結(jié)點(diǎn)移動(dòng)到D結(jié)點(diǎn)，那么此時(shí)的計(jì)算如下：

(B ⊕ D) ⊕ B = D ⊕(B ⊕ B) =B ⊕ 0 = D

因此在確實(shí)可以通過(guò)一個(gè)next的指針域來(lái)實(shí)現(xiàn)雙向鏈表的移動(dòng)，而且這種存儲(chǔ)高效的雙向鏈表還可以節(jié)省空間開銷。實(shí)際上，存儲(chǔ)高效的雙鏈表介紹來(lái)自《數(shù)據(jù)結(jié)構(gòu)與算法經(jīng)典問(wèn)題分析》一書，不過(guò)博主發(fā)現(xiàn)，這種存儲(chǔ)高效的鏈表，使用C語(yǔ)言比較容易實(shí)現(xiàn)，因?yàn)閏語(yǔ)言可以通過(guò)指針(地址)獲取到對(duì)象直接操作，但在Java語(yǔ)言中，博主并沒有想到如何實(shí)現(xiàn)這種存儲(chǔ)高效的鏈表，至少目前還沒想到可行的方案，google了一把實(shí)現(xiàn)語(yǔ)言都是C，沒找到j(luò)ava的實(shí)現(xiàn)，不過(guò)博主想來(lái)想去都感覺這種存儲(chǔ)高效的鏈表不太適合java來(lái)實(shí)現(xiàn)（僅個(gè)人觀點(diǎn)），若有實(shí)現(xiàn)方案的還望留言告知，感謝呢。不過(guò)這樣算法設(shè)計(jì)思想方式還是蠻有不錯(cuò)的。ok~，關(guān)于雙向鏈表，我們暫且聊到這里。

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: