详解java数据结构与算法之双链表设计与实现

在单链表分析中，我们可以知道每个结点只有一个指向后继结点的next域，倘若此时已知当前结点p，需要查找其前驱结点，那么就必须从head头指针遍历至p的前驱结点，操作的效率很低，因此如果p有一个指向前驱结点的next域，那效率就高多了，对于这种一个结点中分别包含了前驱结点域pre和后继结点域next的链表，称之为双链表。本篇我们将从以下结点来分析双链表

双链表的设计与实现

双链表的主要优点是对于任意给的结点，都可以很轻易的获取其前驱结点或者后继结点，而主要缺点是每个结点需要添加额外的next域，因此需要更多的空间开销，同时结点的插入与删除操作也将更加耗时，因为需要更多的指针指向操作。双链表的结构图如下： 

创建HeadDoubleILinkedList类并实现IlinekedList接口(和上篇博文的接口一样)

/**
 * Created by zejian on 2016/10/23.
 * 双链表的实现,带头结点(不带数据)的双链表,为了更高的效率该类包含指向尾部的指针tail
 */
public class HeadDoubleILinkedList<T> implements ILinkedList<T> {

  protected DNode<T> head; //不带数据的头结点
  protected DNode<T> tail; //指向尾部的指针

  public HeadDoubleILinkedList(){
    //初始化头结点
    this.head =this.tail= new DNode<>();     
  }
  //先省略其他代码
  ........
}

结点类结构如下：

package com.zejian.structures.LinkedList.doubleLinked;

/**
 * Created by zejian on 2016/10/23.
 * 双链表结点
 */
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);
  }

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

通过上篇的分析，我们对链表的插入、删除、查找、替换等操作也比较熟悉了，因此针对双链表的实现，主要分析其插入、删除、查找、替换等方法，其他没有分析的看实现源码即可（最后会给出双链表的实现代码）

双链表的插入操作分析与实现

我们先来看看双链表的插入，虽然有不带数据的头结点，但是由于是双向链表，所以在插入双链表时需分两种情况，一种是在插入空双链表和尾部插入，另一种是双链表的中间插入，如下图在空双链表插入值x： 

从图可以看出（a）和（b）属于同种情况，需要注意front.next != null的情况，否则就会抛空指针，而（c）的情况属于中间插入无需无需理会front.next != null的条件，因为中间插入时无论如何其后继结点时不会为null的，插入方法的实现代码如下：

/**
 * 插入结点
 * @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;
    //查找要插入结点位置的前一个结点
    while (front.next != null && j < index) {
      j++;
      front = front.next;
    }

    //创建需要插入的结点,并让其前继指针指向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;
}

双链表的删除操作分析与实现

双链表的删除操作与插入操作原理上是相似的，我们可以看出（a）（b）是属于同种情况，需要防止 p.next.prev抛空指针的情况，而对于（c）情况则无需关系 p.next.prev的值，删除的具体实现如下：

/**
 * 根据下标删除结点
 * 1.头删除
 * 2.中间删除
 * 3.尾部删除,更新tail指向
 * @param index 下标起始值为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;
   //头删除/尾删除/中间删除,查找需要删除的结点(要删除的当前结点因此i<=index)
   while (p!=null&&j<=index){
     p=p.next;
     j++;
   }
   //当双链表只有一个结点时或尾部删除时,无需此步
   if(p.next!=null){
     p.next.prev=p.prev;
   }
   p.prev.next=p.next;
   //如果是尾结点
   if (p==this.tail) {
     this.tail = p.prev;//更新未结点的指向
   }
   temp=p.data;

   return temp;
 }

双链表的查值操作分析与实现

双链表的查找值的操作与单链表并没有什么区别，只要找到需要查找的当前结点获取其值即可，如下： 

代码实现如下：

@Override
public T get(int index) {
  if (index>=0)
  {
    int j=0;
    //注意起始结点为this.head.next
    //如果起始点为this.head时，j的判断为j<=index，
    //因为需要寻找的是当前结点而不是前一个结点。
    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;
      //替换数据
      pre.data=data;
    }
  }
  return old;
}

ok~，到此双链表的主要操作实现已分析完，下面给出双链表的实现源码：

package com.zejian.structures.LinkedList.doubleLinked;

import com.zejian.structures.LinkedList.ILinkedList;

/**
* Created by zejian on 2016/10/23.
* 双链表的实现,为了更高的效率该类包含指向尾部的指针tail
*/
public class HeadDoubleILinkedList<T> implements ILinkedList<T> {

 protected DNode<T> head; //不带数据的头结点
 protected DNode<T> tail; //指向尾部的指针

 public HeadDoubleILinkedList(){
   this.head =this.tail= new DNode<>();     //初始化头结点
 }


 /**
 * 传入一个数组,转换成链表
 * @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;
       //替换数据
       pre.data=data;
     }
   }
   return old;
 }

 /**
 * 插入结点
 * @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;
     //查找要插入结点位置的前一个结点
     while (front.next != null && j < index) {
       j++;
       front = front.next;
     }

     //创建需要插入的结点,后继指针指向front.next
     DNode<T> q = new DNode<T>(data,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;
   //创建新结点,并把其前继指针指向tail
   DNode<T> q = new DNode<T>(data,tail,null);
   tail.next=q;
   //更新尾部结点
   this.tail=q;
   return true;
 }

 /**
 * 根据下标删除结点
 * 1.头删除
 * 2.中间删除
 * 3.尾部删除,查找需要删除的结点(要删除的当前结点因此i<=index)
   while (p!=null&&j<=index){
     p=p.next;
     j++;
   }
   //当链表只要一个结点时,无需此步
   if(p.next!=null){
     p.next.prev=p.prev;
   }
   p.prev.next=p.next;
   //如果是尾结点
   if (p==this.tail) {
     this.tail = p.prev;//更新未结点的指向
   }
   temp=p.data;

   return temp;
 }

 /**
 * 根据data删除结点,无需像单向链表那样去存储要删除结点的前一个结点
 * 1.头删除
 * 2.中间删除
 * 3.尾部删除,更新tail指向
 * @param data
 * @return
 */
 @Override
 public boolean removeAll(T data) {

   boolean isRemove=false;

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

   //注意这里的起点,如果起点为this.head,那么情况区别如同前面的根据index的删除实现
   DNode<T> p=this.head.next;

   //头删除/尾删除/中间删除(size>1),查找所有需要删除的结点
   while (p!=null){

     if(data.equals(p.data)){
       if (p==this.tail){
         //如果是尾结点
         this.tail=p.prev;//更新未结点的指向
         p.prev=null;
         this.tail.next=null;
       }else {
         //如果是在中间删除,更新前继和后继指针指向
         p.prev.next=p.next;
         p.next.prev=p.prev;
       }
       isRemove=true;
       p=p.next;//继续查找
     }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());
 }
}

循环双链表的设计与实现

如果双链表的最后一个结点的next指针域指向头结点，而头结点的prev指针指向头最后一个结点，则构成了双链表（Circular Doubly LinkedList），其结构如下图示： 

（编辑：安卓应用网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!