詳解java數(shù)據(jù)結(jié)構(gòu)與算法之雙鏈表設(shè)計(jì)與實(shí)現(xiàn)
在單鏈表分析中，我們可以知道每個(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域，那效率就高多了，對于這種一個(gè)結(jié)點(diǎn)中分別包含了前驅(qū)結(jié)點(diǎn)域pre和后繼結(jié)點(diǎn)域next的鏈表，稱之為雙鏈表。本篇我們將從以下結(jié)點(diǎn)來分析雙鏈表
雙鏈表的設(shè)計(jì)與實(shí)現(xiàn)
雙鏈表的主要優(yōu)點(diǎn)是對于任意給的結(jié)點(diǎn)，都可以很輕易的獲取其前驅(qū)結(jié)點(diǎn)或者后繼結(jié)點(diǎn)，而主要缺點(diǎn)是每個(gè)結(jié)點(diǎn)需要添加額外的next域，因此需要更多的空間開銷，同時(shí)結(jié)點(diǎn)的插入與刪除操作也將更加耗時(shí)，因?yàn)樾枰嗟闹羔樦赶虿僮鳌ｋp鏈表的結(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();
}
}
通過上篇的分析，我們對鏈表的插入、刪除、查找、替換等操作也比較熟悉了，因此針對雙鏈表的實(shí)現(xiàn)，主要分析其插入、刪除、查找、替換等方法，其他沒有分析的看實(shí)現(xiàn)源碼即可（最后會(huì)給出雙鏈表的實(shí)現(xiàn)代碼）
雙鏈表的插入操作分析與實(shí)現(xiàn)
我們先來看看雙鏈表的插入，雖然有不帶數(shù)據(jù)的頭結(jié)點(diǎn)，但是由于是雙向鏈表，所以在插入雙鏈表時(shí)需分兩種情況，一種是在插入空雙鏈表和尾部插入，另一種是雙鏈表的中間插入，如下圖在空雙鏈表插入值x：
從圖可以看出（a）和（b）屬于同種情況，需要注意front.next != null的情況，否則就會(huì)拋空指針，而（c）的情況屬于中間插入無需無需理會(huì)front.next != null的條件，因?yàn)橹虚g插入時(shí)無論如何其后繼結(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);
//空雙鏈表插入和尾部插入，無需此操作
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拋空指針的情況，而對于（c）情況則無需關(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í),無需此步
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)
雙鏈表的替換值過程，需要先查找到需要替換的結(jié)點(diǎn)，這個(gè)過程跟獲取值的過程是一樣的，找到結(jié)點(diǎ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í),無需此步
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),無需像單向鏈表那樣去存儲(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)的位置。對于循環(huán)雙鏈表的插入、刪除操作也無需區(qū)分位置操作的情況，這是由于循環(huán)雙鏈表的本身的特殊性，使p.next.pre永遠(yuǎn)不可能為null，因此我們在插入和刪除時(shí)代碼實(shí)現(xiàn)相對簡單些。下面我們先分析一下循環(huán)雙鏈表的插入操作，圖示如下：
我們可以看出（a）（b）（c）三種情況都無需關(guān)系位置插入的區(qū)別，其代碼實(shí)現(xiàn)如下：
/**
* 根據(jù)index插入
* 循環(huán)鏈表中無論是prev還是next都不存在空的情況,因此添加時(shí)
* 無論是頭部還是尾部還是中,都視為一種情況對待
* @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）三種情況都無需區(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)雙鏈表的后繼指針指向自己說明是空鏈表
}
@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)鏈表中無論是prev還是next都不存在空的情況,因此添加時(shí)
* 無論是頭部還是尾部還是中,都視為一種情況對待
* @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)比較簡單，我們只需繼承前面的循環(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)不通過.
//如果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í)上一篇已分析得差不多了，這里再簡單說明一下，鏈表在插入和刪除元素時(shí)執(zhí)行效率比較高，從插入操作來看，我們假設(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)的效率比單鏈表有所改善，無需從頭結(jié)點(diǎn)開始遍歷，但是上述都是從已知雙向鏈表中front結(jié)點(diǎn)的情況下討論的。如果從實(shí)現(xiàn)代碼的操作上看，無論是插入還是刪除，都需要查找插入結(jié)點(diǎn)或刪除結(jié)點(diǎn)，而這個(gè)過程訪問結(jié)點(diǎn)所花費(fèi)的時(shí)間的是O(n)，因此雙鏈表的插入或刪除操作或是查值操作，其時(shí)間復(fù)雜度都為O(n),至于為什么說鏈表更適合插入刪除，這點(diǎn)上一篇我們已討論過，這里就不重復(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è)指針域來設(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)的地址差，指針的差通過異或運(yùn)行（對異或不熟悉的可以看博主的另一篇文章：java運(yùn)算符）來實(shí)現(xiàn)的，我們這里使用⊕表示異或操作，則有如下計(jì)算：
pridiff=后繼結(jié)點(diǎn)的地址⊕前驅(qū)結(jié)點(diǎn)的地址
如上圖，我們采用異或差值來計(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ì)算呢？我們先來了解一下異或的特性：
- X⊕X=0
- X⊕0=X
- X⊕Y=Y⊕X
- (X⊕Y)⊕Z=X⊕(Y⊕Z)
所以我們可以很容易利用上述的異或特性找到結(jié)點(diǎn)的對象，比如指向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ì)算過程如下：
(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í)可以通過一個(gè)next的指針域來實(shí)現(xiàn)雙向鏈表的移動(dòng)，而且這種存儲(chǔ)高效的雙向鏈表還可以節(jié)省空間開銷。實(shí)際上，存儲(chǔ)高效的雙鏈表介紹來自《數(shù)據(jù)結(jié)構(gòu)與算法經(jīng)典問題分析》一書，不過博主發(fā)現(xiàn)，這種存儲(chǔ)高效的鏈表，使用C語言比較容易實(shí)現(xiàn)，因?yàn)閏語言可以通過指針(地址)獲取到對象直接操作，但在Java語言中，博主并沒有想到如何實(shí)現(xiàn)這種存儲(chǔ)高效的鏈表，至少目前還沒想到可行的方案，google了一把實(shí)現(xiàn)語言都是C，沒找到j(luò)ava的實(shí)現(xiàn)，不過博主想來想去都感覺這種存儲(chǔ)高效的鏈表不太適合java來實(shí)現(xiàn)（僅個(gè)人觀點(diǎn)），若有實(shí)現(xiàn)方案的還望留言告知，感謝呢。不過這樣算法設(shè)計(jì)思想方式還是蠻有不錯(cuò)的。ok~，關(guān)于雙向鏈表，我們暫且聊到這里。
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
Java數(shù)據(jù)結(jié)構(gòu)之哈夫曼樹概述及實(shí)現(xiàn)
文中詳細(xì)講了關(guān)于Java哈夫曼樹的概述以及用Java實(shí)現(xiàn)的方法,對各位正在學(xué)習(xí)java數(shù)據(jù)結(jié)構(gòu)的小伙伴們有很大的幫助喲,需要的朋友可以參考下2021-05-05
Java ArrayList如何實(shí)現(xiàn)生成不重復(fù)隨機(jī)數(shù)
這篇文章主要介紹了Java ArrayList如何實(shí)現(xiàn)生成不重復(fù)隨機(jī)數(shù),文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-09-09
java POI解析Excel 之?dāng)?shù)據(jù)轉(zhuǎn)換公用方法(推薦)
下面小編就為大家?guī)硪黄猨ava POI解析Excel 之?dāng)?shù)據(jù)轉(zhuǎn)換公用方法(推薦)。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2016-08-08
這篇文章主要為大家介紹了Spring?refresh()源碼解析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-03-03
Java語言中的重載和重寫是實(shí)現(xiàn)多態(tài)的兩種方式,但他們的實(shí)現(xiàn)方式和規(guī)則有所不同,重載發(fā)生在一個(gè)類中,同名的方法如果有不同的參數(shù)列表,則視為重載,重寫則發(fā)生在子類和父類之間,要求子類重寫方法和父類被重寫方法有相同的返回類型2024-10-10
詳解Nacos中注冊中心和配置中心的實(shí)現(xiàn)
Spring?Cloud?Alibaba?是阿里巴巴提供的一站式微服務(wù)開發(fā)解決方案。而?Nacos?作為?Spring?Cloud?Alibaba?的核心組件之一，提供了兩個(gè)非常重要的功能：注冊中心和配置中心，我們今天來了解和實(shí)現(xiàn)一下二者2022-08-08
這篇文章主要介紹了Java數(shù)據(jù)類型的規(guī)則的相關(guān)資料,非常不錯(cuò)，具有參考借鑒價(jià)值，需要的朋友可以參考下2016-12-12
這篇文章主要介紹了解決springcloud-gateway限流遇到的問題，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-07-07
SpringBoot集成Memcached的項(xiàng)目實(shí)踐
Memcached是一個(gè)高性能的分布式內(nèi)存對象緩存系統(tǒng),用于動(dòng)態(tài)Web應(yīng)用以減輕數(shù)據(jù)庫負(fù)載,本文主要介紹了SpringBoot集成Memcached的項(xiàng)目實(shí)踐,具有一定的參考價(jià)值,感興趣的可以了解一下2024-01-01
設(shè)計(jì)模式（Design pattern）是一套被反復(fù)使用、多數(shù)人知曉的、經(jīng)過分類編目的、代碼設(shè)計(jì)經(jīng)驗(yàn)的總結(jié)。使用設(shè)計(jì)模式是為了可重用代碼、讓代碼更容易被他人理解、保證代碼可靠性2021-11-11