1. 首页
  2. 编程与技术

java双向循环链表的实现代码

发布于 2016-07-21 12:38:08 | 152 次阅读 | 评论: 0 | 来源: 网友投递

这里有新鲜出炉的Java并发编程示例，程序狗速度看过来！

Java程序设计语言

java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言，是由Sun Microsystems公司于1995年5月推出的Java程序设计语言和Java平台（即JavaEE(j2ee), JavaME(j2me), JavaSE(j2se)）的总称。

这篇文章介绍了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循环，这里要特别注意



最新网友评论  共有(0)条评论 发布评论 返回顶部
推荐阅读
  • 终极炫富——2016 年 iOS 开发者收入调查报告
  • 年度大片：Stack Overflow 2017 开发者调查报告发布！
  • 开发者需要大学学位吗？
  • 程序员多大年纪算高龄，届时该何去何从？
  • 2017 年高薪编程语言排行榜，你的语言上榜没？
  • 各编程语言开发者最常使用的按键，中了没?
  • 伤不起的三十岁，干不动的程序员要何去何从？
  • 2016年中国加班最狠IT公司排行
  • 一句话"面试"漫画：黑了苹果、谷歌、三星
  • 拿代码量算 KPI ……跟程序员们来这套？
  • 程序员遇到 Bug 时的 30 个反应，你是哪一种？
  • 2016年收入最高的5个编程语言 Java和C没在前五?
  • 为什么很少见人傻钱多的程序员炫富？
  • 阿里月薪两万是什么体验？
  • 代码缩进时 程序员更喜欢空格键还是Tab键？
    • 最新资讯
  • Python获取系统所有进程PID及进程名称的方法示例
  • Python简单获取网卡名称及其IP地址的方法【基于psutil模块】
  • Python实现的根据IP地址计算子网掩码位数功能示例
  • 好的Python培训机构应该具备哪些条件
  • 详解Pytorch 使用Pytorch拟合多项式(多项式回归)
  • Python加载带有注释的Json文件实例
  • 对python的文件内注释 help注释方法
  • Python实现判断一行代码是否为注释的方法
  • Oracle数据库表中字段顺序的修改方法
  • ASP.NET MVC 4使用PagedList.Mvc分页的实现代码
  • Oracle实例启动时报错：ORA-32004的解决方法
  • 解读ASP.NET 5 & MVC6系列教程（7）：依赖注入
  • 详解IDEA用maven创建springMVC项目和配置
  • ASP.NET MVC5网站开发之展示层架构（五）
  • SpringBoot创建maven多模块项目实战代码
    • 后端技术
    前端技术
    数据库
    热门框架
    常用IDE
    其他
    Copyright © 2007-2017 PHPERZ.COM All Rights Reserved   冀ICP备14009818号  版权声明  广告服务