在java項目中怎么設(shè)計雙鏈表

這篇文章將為大家詳細講解有關(guān)在java項目中怎么設(shè)計雙鏈表，文章內(nèi)容質(zhì)量較高，因此小編分享給大家做個參考，希望大家閱讀完這篇文章后對相關(guān)知識有一定的了解。

成都創(chuàng)新互聯(lián)公司是一家專業(yè)提供常州企業(yè)網(wǎng)站建設(shè),專注與網(wǎng)站設(shè)計制作、網(wǎng)站制作、HTML5、小程序制作等業(yè)務(wù)。10年已為常州眾多企業(yè)、政府機構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專業(yè)網(wǎng)站制作公司優(yōu)惠進行中。

雙鏈表的設(shè)計

雙鏈表的主要優(yōu)點是對于任意給的結(jié)點，都可以很輕易的獲取其前驅(qū)結(jié)點或者后繼結(jié)點，而主要缺點是每個結(jié)點需要添加額外的next域，因此需要更多的空間開銷，同時結(jié)點的插入與刪除操作也將更加耗時，因為需要更多的指針指向操作。雙鏈表的結(jié)構(gòu)圖如下：

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

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

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

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

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

package com.zejian.structures.LinkedList.doubleLinked;

/**
 * Created by zejian on 2016/10/23.
 * 雙鏈表結(jié)點
 */
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();
  }
}

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

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

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

在java項目中怎么設(shè)計雙鏈表

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

/**
 * 插入結(jié)點
 * @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é)點位置的前一個結(jié)點
    while (front.next != null && j < index) {
      j++;
      front = front.next;
    }

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

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

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

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

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

在java項目中怎么設(shè)計雙鏈表

/**
 * 根據(jù)下標(biāo)刪除結(jié)點
 * 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é)點(要刪除的當(dāng)前結(jié)點因此i<=index)
   while (p!=null&&j<=index){
     p=p.next;
     j++;
   }
   //當(dāng)雙鏈表只有一個結(jié)點時或尾部刪除時,無需此步
   if(p.next!=null){
     p.next.prev=p.prev;
   }
   p.prev.next=p.next;
   //如果是尾結(jié)點
   if (p==this.tail) {
     this.tail = p.prev;//更新未結(jié)點的指向
   }
   temp=p.data;

   return temp;
 }

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

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

在java項目中怎么設(shè)計雙鏈表

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

@Override
public T get(int index) {
  if (index>=0)
  {
    int j=0;
    //注意起始結(jié)點為this.head.next
    //如果起始點為this.head時，j的判斷為j<=index，
    //因為需要尋找的是當(dāng)前結(jié)點而不是前一個結(jié)點。
    DNode<T> pre=this.head.next;
    while (pre!=null && j<index)
    {
      j++;
      pre=pre.next;
    }
    if (pre!=null)
      return pre.data;
  }
  return null;
}

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

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

@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~，到此雙鏈表的主要操作實現(xiàn)已分析完，下面給出雙鏈表的實現(xiàn)源碼：

package com.zejian.structures.LinkedList.doubleLinked;

import com.zejian.structures.LinkedList.ILinkedList;

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

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

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


 /**
 * 傳入一個數(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é)點
 * @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é)點位置的前一個結(jié)點
     while (front.next != null && j < index) {
       j++;
       front = front.next;
     }

     //創(chuàng)建需要插入的結(jié)點,并讓其前繼指針指向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;

     //在尾部插入時需要注意更新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é)點,并把其前繼指針指向tail
   DNode<T> q = new DNode<T>(data, tail, null);
   tail.next=q;
   //更新尾部結(jié)點
   this.tail=q;
   return true;
 }

 /**
 * 根據(jù)下標(biāo)刪除結(jié)點
 * 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é)點(要刪除的當(dāng)前結(jié)點因此i<=index)
   while (p!=null&&j<=index){
     p=p.next;
     j++;
   }
   //當(dāng)鏈表只要一個結(jié)點時,無需此步
   if(p.next!=null){
     p.next.prev=p.prev;
   }
   p.prev.next=p.next;
   //如果是尾結(jié)點
   if (p==this.tail) {
     this.tail = p.prev;//更新未結(jié)點的指向
   }
   temp=p.data;

   return temp;
 }

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

   boolean isRemove=false;

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

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

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

     if(data.equals(p.data)){
       if (p==this.tail){
         //如果是尾結(jié)點
         this.tail=p.prev;//更新未結(jié)點的指向
         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è)計與實現(xiàn)

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

在java項目中怎么設(shè)計雙鏈表

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

在java項目中怎么設(shè)計雙鏈表

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

/**
 * 根據(jù)index插入
 * 循環(huán)鏈表中無論是prev還是next都不存在空的情況,因此添加時
 * 無論是頭部還是尾部還是中,都視為一種情況對待
 * @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;
  //尋找插入點的位置
  while (p.next!=head&&j<index){
    p=p.next;
    j++;
  }

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

  return true;
}

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

在java項目中怎么設(shè)計雙鏈表

雙鏈表的刪除操作圖示

同樣地，從圖中我們也可以發(fā)現(xiàn)由于循環(huán)雙鏈表的特性，（a）（b）（c）三種情況都無需區(qū)分操作位置，其代碼實現(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)雙鏈表時，結(jié)束標(biāo)志不再是尾部結(jié)點是否為空，而是尾結(jié)點的next指針是否指向頭結(jié)點head。好~，下面我們給出循環(huán)雙鏈表的實現(xiàn)代碼：

package com.zejian.structures.LinkedList.doubleLinked;

import com.zejian.structures.LinkedList.ILinkedList;

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

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

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

 }

 

 /**
 * 傳入一個數(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)雙鏈表的后繼指針指向自己說明是空鏈表
 }

 @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é)點
     if(p!=head){
       T old = p.data;
       p.data=data;

       return old;
     }
   }

   return null;
 }

 /**
 * 根據(jù)index添加
 * 循環(huán)鏈表中無論是prev還是next都不存在空的情況,因此添加時
 * 無論是頭部還是尾部還是中,都視為一種情況對待
 * @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;
   //尋找插入點的位置
   while (p.next!=head&&j<index){
     p=p.next;
     j++;
   }

   //創(chuàng)建新結(jié)點,如果index=3,那么插入的位置就是第4個位置
   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é)點,讓前繼指針指向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)雙鏈表的實現(xiàn)

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

package com.zejian.structures.LinkedList.doubleLinked;

/**
* Created by zejian on 2016/11/6.
* 升序排序鏈表，繼承LoopHeadDILinkedList
*/
public class SortLoopHeadDIlinkedList<T extends Comparable<&#63; 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編輯器上檢驗不通過.

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

   DNode<T> p=this.head.next;
   //查找插入點
   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í)行效率分析

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

傳遞參數(shù)	鏈表	動態(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)
空間浪費	O(n)	O(n)

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

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

package com.zejian.structures.LinkedList.XORLinked;

/**
 * Created by zejian on 2016/11/6.
 * 異或結(jié)點
 */
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字段存儲了后繼結(jié)點與前驅(qū)結(jié)點的地址差，指針的差通過異或運行（對異或不熟悉的可以看博主的另一篇文章：java運算符）來實現(xiàn)的，我們這里使用⊕表示異或操作，則有如下計算：

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

在java項目中怎么設(shè)計雙鏈表

如上圖，我們采用異或差值來計算各個結(jié)點的位置：

A的next域為head⊕B
B的next域為A⊕C
C的next域為B⊕D
D的next域為C⊕NULL

那么為什么可以這么計算呢？我們先來了解一下異或的特性：

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

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

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

如果想從C結(jié)點移動到D結(jié)點，那么此時的計算如下：

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

關(guān)于在java項目中怎么設(shè)計雙鏈表就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，可以學(xué)到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。

當(dāng)前題目：在java項目中怎么設(shè)計雙鏈表
本文路徑：http://m.kartarina.com/article36/jedpsg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站策劃、小程序開發(fā)、、面包屑導(dǎo)航、App開發(fā)、網(wǎng)站收錄

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容