| 标题 | 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循环，这里要特别注意 |
| 随便看 |
|
在线学习网考试资料包含高考、自考、专升本考试、人事考试、公务员考试、大学生村官考试、特岗教师招聘考试、事业单位招聘考试、企业人才招聘、银行招聘、教师招聘、农村信用社招聘、各类资格证书考试等各类考试资料。