午夜国产狂喷潮在线观看|国产AⅤ精品一区二区久久|中文字幕AV中文字幕|国产看片高清在线

代碼如下:

package com.xlst.util;

import java.util.HashMap;

import java.util.Map;

import java.util.UUID;

/**

* 雙向循環(huán)鏈表

* 完成時間：2012.9.28

* 版本1.0

* @author xlst

*

*/

public class BothwayLoopLinked {

/**

* 存放鏈表長度的 map

*

* 如果簡單使用 static int 型的 size 基本類型變量，則只能維護一個雙向循環(huán)鏈表。

* 同時存在兩個及以上雙向循環(huán)鏈表時，數(shù)據(jù)會錯亂

*/

private static final Map<String, Integer> sizeMap = new HashMap<String, Integer>();

/**

* 雙向鏈表的 id

* 一個雙向一個唯一的 id

* 根據(jù)這個id可以從 sizeMap 中取出當前鏈表的長度

*/

private String linkedId = null;

/**

* 節(jié)點中的數(shù)據(jù)

*/

private Object data = null;

/**

* 前一個節(jié)點（初始化時是自身）

*/

private BothwayLoopLinked prev = this;

/**

* 后一個節(jié)點（初始化時是自身）

*/

private BothwayLoopLinked next = this;

public BothwayLoopLinked(){}

/**

* 在節(jié)點之后插入新節(jié)點

* @param newLinked 新插入的節(jié)點

*/

public void insertAfter(BothwayLoopLinked newLinked){

// 原來的前節(jié)點與后節(jié)點

BothwayLoopLinked oldBefore = this;

BothwayLoopLinked oldAfter = this.next;

// 設置 newLinked 與原前節(jié)點的關系

oldBefore.next = newLinked;

newLinked.prev = oldBefore;

// 設置 newLinked 與原后節(jié)點的關系

oldAfter.prev = newLinked;

newLinked.next = oldAfter;

// 鏈表長度加一

changeSize(+1);

// 綁定新節(jié)點的 linkedId

newLinked.linkedId = this.linkedId;

}

/**

* 在節(jié)點之前插入新節(jié)點

* @param newLinked 新插入的節(jié)點

*/

public void insertBefore(BothwayLoopLinked newLinked){

// 原來的前節(jié)點與后節(jié)點

BothwayLoopLinked oldBefore = this.prev;

BothwayLoopLinked oldAfter = this;

// 設置 newLinked 與原前節(jié)點的關系

oldBefore.next = newLinked;

newLinked.prev = oldBefore;

// 設置 newLinked 與原后節(jié)點的關系

oldAfter.prev = newLinked;

newLinked.next = oldAfter;

// 鏈表長度加一

changeSize(+1);

// 綁定新節(jié)點的 linkedId

newLinked.linkedId = this.linkedId;

}

/**

* 從鏈表結構中刪除自身

* @return 被刪除的節(jié)點

*/

public BothwayLoopLinked remove(){

return remove(this);

}

/**

* 從鏈表結構中刪除指定節(jié)點

* @param linked 要刪除的節(jié)點

* @return 被刪除的節(jié)點

*/

public BothwayLoopLinked remove(BothwayLoopLinked linked){

linked.prev.next = linked.next;

linked.next.prev = linked.prev;

linked.prev = linked;

linked.next = linked;

// 鏈表長度減一

changeSize(-1);

// 取消該節(jié)點的 linkedId

this.linkedId = null;

// 返回被刪除的節(jié)點

return linked;

}

/**

* 改變鏈表長度（默認長度加1），私有方法

*/

private void changeSize(){

changeSize(1);

}

/**

* 改變鏈表長度（根據(jù)參數(shù)），私有方法

* @param value 改變的長度值（可以為負數(shù)）

*/

private void changeSize(int value){

if(this.linkedId == null){

this.linkedId = UUID.randomUUID().toString();

sizeMap.put(linkedId, 1 + value); // sizeMap.put(linkedId, 2);

}else{

Integer size = sizeMap.get(this.linkedId);

// Integer 是引用類型，更新值之后不必再 put 回 sizeMap 里

size += value;

}

}

public Object getData() {

return data;

}

public void setData(Object data) {

this.data = data;

}

/**

* 獲取鏈表的長度

* 如果是新生的節(jié)點 或 從鏈表中刪除的節(jié)點，則作為獨立鏈表，長度是 1

* @return 鏈表的長度

*/

public int getSize() {

return (linkedId == null) ? 1 : sizeMap.get(this.linkedId);

}

public BothwayLoopLinked getPrev() {

return prev;

}

public BothwayLoopLinked getNext() {

return next;

}

}

例2

代碼如下:

/**

* 雙向循環(huán)鏈表測試

* @author GKT

* @param <E>

*/

public class Node<E>

{

private E element; //結點數(shù)據(jù)

private Node<E> next; //上結點

private Node<E> previous; //下結點

private static int size=0; //鏈表長

//默認關結點next previous都是空，

public Node()

{

this.element=null;

this.next=null;

this.previous=null;

}

private Node(E element,Node<E> next,Node<E> previous)

{

this.element=element;

this.next=next;

this.previous=previous;

}

/**

* 尾部添加元素 e

* @param e

*/

public void addAfter(E e)

{

//定義新結點，next-->頭結點；previous-->頭結點.previous（尾結點）

Node<E> newNode=new Node<E>(e,this,this.previous==null?this:this.previous);

//頭結點next為空則讓它指向newNode

if(this.next==null)

{

this.next=newNode;

}

//頭結點previous為空則讓它指向newNode

if(this.previous==null)

{

this.previous=newNode;

}

this.previous.next=newNode;

this.previous=newNode;

size++;

}

/**

* 頭部添加元素 e

* @param e

*/

public void addBefor(E e)

{

Node<E> newNode=new Node<E>(e,this.next==null?this:this.next,this);

if(this.next==null)

{

this.next=newNode;

}

if(this.previous==null)

{

this.previous=newNode;

}

this.next.previous=newNode;

this.next=newNode;

size++;

}

/**

* 在index處添加元素e

* @param e

* @param index

*/

public void add(E e,int index)

{

//索引越界

if(index>=size || index<0)

{

throw new IndexOutOfBoundsException("Node.get():"+index);

}

else

{

//index>size/2,反向遍歷

if(index>size>>1)

{

Node<E> temp=this;

for(int i=size;i>index;i--)

{

temp=temp.previous;

}

Node<E> newNode=new Node<E>(e,temp,temp.previous);

temp.previous.next=newNode;

temp.previous=newNode;

}

else

{

Node<E> temp=this;

for(int i=0;i<=index;i++)

{

temp=temp.next;

}

Node<E> newNode=new Node<E>(e,temp,temp.previous);

temp.previous.next=newNode;

temp.previous=newNode;

}

size++;

}

}

/**

* 刪除第index個元素

* @param index

*/

public void remove(int index)

{

//索引越界

if(index>=size || index<0)

{

throw new IndexOutOfBoundsException("Node.get():"+index);

}

else

{

//index>size/2,反向遍歷

if(index>size>>1)

{

Node<E> temp=this;

for(int i=size;i>index;i--)

{

temp=temp.previous;

}

temp.previous.next=temp.next;

temp.next.previous=temp.previous;

}

else

{

Node<E> temp=this;

for(int i=0;i<=index;i++)

{

temp=temp.next;

}

temp.previous.next=temp.next;

temp.next.previous=temp.previous;

}

size--;

}

}

/**

* 取得第index個元素

* @param index

* @return

*/

public E get(int index)

{

//索引越界

if(index>=size || index<0)

{

throw new IndexOutOfBoundsException("Node.get():"+index);

}

else

{

//index>size/2,反向遍歷

if(index>size>>1)

{

Node<E> temp=this;

for(int i=size;i>index;i--)

{

temp=temp.previous;

}

return temp.element;

}

else

{

Node<E> temp=this;

for(int i=0;i<=index;i++)

{

temp=temp.next;

}

return temp.element;

}

}

}

public int size()

{

return size;

}

public static void main(String a[])

{

Node node=new Node();

node.addAfter("1");

node.addAfter("2");

node.addAfter("3");

node.addBefor("0");

node.add("7", 0);

System.out.println(node.get(0) );

System.out.println(node.get(1) );

System.out.println(node.get(2) );

System.out.println(node.get(3) );

System.out.println(node.get(4) );

}

}

這兩個鏈表最大的不同就是頭結點是否是啞元，以及取出元素(get函數(shù))的時候for循環(huán)變量i的不同：

雙向循環(huán)鏈表(和java.util包的設計一樣)：由于head是啞元，因此取元素從head的下一個結點取

單向鏈表：head不是啞元，第一次必須取head頭結點的元素，因此循環(huán)上和雙向循環(huán)鏈表不同。也就是第一次get并沒有進入for循環(huán)，直接返回了頭結點，從第二次才開始進入for循環(huán)，這里要特別注意

更多信息請查看IT技術專欄