展会信息港展会大全

java双向循环链表 android软件开发教程
来源:互联网   发布日期:2016-03-01 10:41:32   浏览:2558次  

导读:代码如下 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 * * 如...

代码如下

packagecom.xlst.util;

import java.util.HashMap;

importjava.util.Map;

import java.util.UUID;

/**

* 双向循环链表

*完成时间:2012.9.28

* 版本1.0

* @author xlst

*

*/

public classBothwayLoopLinked {

/**

* 存放链表长度的 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;

/**

* 后一个节点(初始化时是自身)

*/

privateBothwayLoopLinked next = this;

publicBothwayLoopLinked(){}

/**

* 在节点之后插入新节点

* @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 voidinsertBefore(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 BothwayLoopLinkedremove(){

return remove(this);

}

/**

*从链表结构中删除指定节点

* @param linked 要删除的节点

* @return 被删除的节点

*/

public BothwayLoopLinked remove(BothwayLoopLinkedlinked){

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(intvalue){

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() {

returndata;

}

public void setData(Object data) {

this.data = data;

}

/**

* 获取链表的长度

*如果是新生的节点 或 从链表中删除的节点,则作为独立链表,长度是 1

* @return 链表的长度

*/

public int getSize() {

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

}

public BothwayLoopLinkedgetPrev() {

return prev;

}

publicBothwayLoopLinked getNext() {

return next;

}

}

例2

代码如下

/**

*双向循环链表测试

* @author GKT

* @param <E>

*/

public classNode<E>

{

private Eelement;//结点数据

private Node<E> next;//上结点

private Node<E> previous;//下结点

private static intsize=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 voidaddAfter(E e)

{

//定义新结点,next-->头结点;previous-->头结点.previous(尾结点)

Node<E>newNode=newNode<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 newIndexOutOfBoundsException("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=newNode<E>(e,temp,temp.previous);

temp.previous.next=newNode;

temp.previous=newNode;

}

else

{

Node<E> temp=this;

for(inti=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 newIndexOutOfBoundsException("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 newIndexOutOfBoundsException("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 intsize()

{

return size;

}

public static void main(Stringa[])

{

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循环,这里要特别注意

赞助本站

人工智能实验室

相关热词: 开发 编程 android

相关内容
AiLab云推荐
展开

热门栏目HotCates

Copyright © 2010-2024 AiLab Team. 人工智能实验室 版权所有    关于我们 | 联系我们 | 广告服务 | 公司动态 | 免责声明 | 隐私条款 | 工作机会 | 展会港