java双向循环链表的实现代码
例1：
package com.xlst.util;
import java.util.hashmap;
import java.util.map;
import java.util.uuid;
/**
* 双向循环链表
* 完成时间：2012.9.28
* 版本1.0
* @author xlst
*
*/
public class bothwaylooplinked {
/**
* 存放链表长度的 map
*
* 如果简单使用 static int 型的 size 基本类型变量，则只能维护一个双向循环链表。
* 同时存在两个及以上双向循环链表时，数据会错乱
*/
private static final map<string, integer> sizemap = new hashmap<string, integer>();
/**
* 双向链表的 id
* 一个双向一个唯一的 id
* 根据这个id可以从 sizemap 中取出当前链表的长度
*/
private string linkedid = null;
/**
* 节点中的数据
*/
private object data = null;
/**
* 前一个节点（初始化时是自身）
*/
private bothwaylooplinked prev = this;
/**
* 后一个节点（初始化时是自身）
*/
private bothwaylooplinked next = this;
public bothwaylooplinked(){}
/**
* 在节点之后插入新节点
* @param newlinked 新插入的节点
*/
public void insertafter(bothwaylooplinked newlinked){
// 原来的前节点与后节点
bothwaylooplinked oldbefore = this;
bothwaylooplinked oldafter = this.next;
// 设置 newlinked 与原前节点的关系
oldbefore.next = newlinked;
newlinked.prev = oldbefore;
// 设置 newlinked 与原后节点的关系
oldafter.prev = newlinked;
newlinked.next = oldafter;
// 链表长度加一
changesize(+1);
// 绑定新节点的 linkedid
newlinked.linkedid = this.linkedid;
}
/**
* 在节点之前插入新节点
* @param newlinked 新插入的节点
*/
public void insertbefore(bothwaylooplinked newlinked){
// 原来的前节点与后节点
bothwaylooplinked oldbefore = this.prev;
bothwaylooplinked oldafter = this;
// 设置 newlinked 与原前节点的关系
oldbefore.next = newlinked;
newlinked.prev = oldbefore;
// 设置 newlinked 与原后节点的关系
oldafter.prev = newlinked;
newlinked.next = oldafter;
// 链表长度加一
changesize(+1);
// 绑定新节点的 linkedid
newlinked.linkedid = this.linkedid;
}
/**
* 从链表结构中删除自身
* @return 被删除的节点
*/
public bothwaylooplinked remove(){
return remove(this);
}
/**
* 从链表结构中删除指定节点
* @param linked 要删除的节点
* @return 被删除的节点
*/
public bothwaylooplinked remove(bothwaylooplinked linked){
linked.prev.next = linked.next;
linked.next.prev = linked.prev;
linked.prev = linked;
linked.next = linked;
// 链表长度减一
changesize(-1);
// 取消该节点的 linkedid
this.linkedid = null;
// 返回被删除的节点
return linked;
}
/**
* 改变链表长度（默认长度加1），私有方法
*/
private void changesize(){
changesize(1);
}
/**
* 改变链表长度（根据参数），私有方法
* @param value 改变的长度值（可以为负数）
*/
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;
}
/**
* 获取链表的长度
* 如果是新生的节点 或 从链表中删除的节点，则作为独立链表，长度是 1
* @return 链表的长度
*/
public int getsize() {
return (linkedid == null) ? 1 : sizemap.get(this.linkedid);
}
public bothwaylooplinked getprev() {
return prev;
}
public bothwaylooplinked getnext() {
return next;
}
}
例2：
/**
* 双向循环链表测试
* @author gkt
* @param <e>
*/
public class node<e>
{
private e element; //结点数据
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函数)的时候for循环变量i的不同：
双向循环链表(和java.util包的设计一样)：由于head是哑元，因此取元素从head的下一个结点取
单向链表：head不是哑元，第一次必须取head头结点的元素，因此循环上和双向循环链表不同。也就是第一次get并没有进入for循环，直接返回了头结点，从第二次才开始进入for循环，这里要特别注意