欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

java数据结构之实现双向链表的示例

程序员文章站 2024-02-24 14:10:28
复制代码 代码如下:/** * 双向链表的实现 * @author skip * @version 1.0 */public cla...

复制代码 代码如下:

/**
 * 双向链表的实现
 * @author skip
 * @version 1.0
 */
public class doublenodelist<t> {
 //节点类
 private static class node<t>{
  node<t> perv;  //前节点
  node<t> next;  //后节点
  t data;    //数据

  public node(t t){
   this.data = t;
  }
 }
 private node<t> head;  //头节点
 private node<t> last;  //尾节点
 private node<t> other;  //备用节点存放临时操作
 private int length;  //链表长度

 /**
  * 无参构造
  */
 public doublenodelist(){
  head = new node<t>(null);
  last = head;
  length = 0;
 }

 /**
  * 初始化时创建一个节点
  * @param data 数据
  */
 public doublenodelist(t data){
  head = new node<t>(data);
  last = head;
  length = 1;
 }

 /**
  * 添加一个节点
  * @param data 添加的数据
  */
 public void add(t data){
  if(isempty()){
   head = new node<t>(data);
   last = head;
   length++;
  }else{
   //尾插法
   other = new node<t>(data);
   other.perv = last;
   last.next = other;
   last = other;
   length++;
  }
 }

 /**
  * 在指定数据后插入一个节点
  * @param data 指定的数据
  * @param insertdata 插入的数据
  * @return 插入成功返回true,不成功返回false
  */
 public boolean addafert(t data , t insertdata){
  other = head;
  while(other != null){
   if(other.data.equals(data)){
    node<t> t = new node<t>(insertdata);
    t.perv = other;
    t.next = other.next;
    other.next = t;
    //判断是否在最后一个节点后添加节点
    if(t.next==null){
     last = t;
    }
    length++;
    return true;
   }
   other = other.next;
  }
  return false;
 }

 /**
  * 在指定数据前插入一个节点
  * @param data 指定的数据
  * @param insertdata 插入的数据
  * @return 插入成功返回true,不成功返回false
  */
 public boolean addbefore(t data, t insertdata){
  other = head;
  while(other != null){
   if(other.data.equals(data)){
    node<t> t = new node<t>(insertdata);
    t.perv = other.perv;
    t.next = other;
    other.perv.next = t;
    length++;
    return true;
   }
   other = other.next;
  }
  return false;
 }

 /**
  * 获得索引处的数据
  * @param index 索引
  * @return 数据
  */
 public t get(int index){
  if(index>length || index<0){
   throw new indexoutofboundsexception("索引越界:"+index);
  }
  other = head;
  for(int i=0;i<index;i++){
   other = other.next;
  }
  return other.data;
 }

 /**
  * 新值替换旧值
  * @return 成功为true,未找到为false
  */
 public boolean set(t oldvalue,t newvalue){
  other = head;
  while(other!=null){
   if(other.data.equals(oldvalue)){
    other.data = newvalue;
    return true;
   }
   other = other.next;
  }
  return false;
 }

 /**
  * 移除指定的元素
  * @param data 需要移除的元素
  * @return 不存在为false,成功为true
  */
 public boolean remove(t data){
  other = head;
  while(other != null){
   if(other.data.equals(data)){
    other.perv.next = other.next;
    length--;
    return true;
   }
   other = other.next;
  }
  return false;
 }

 /**
  * 链表中是否包含此元素
  * @return 包含为true,不包含为false
  */
 public boolean contains(t data){
  other = head;
  while(other != null){
   if(other.data.equals(data)){
    return true;
   }
   other = other.next;
  }
  return false;
 }

 /**
  * 获得最后一个节点的数据
  * @return 最后一个节点的数据
  */
 public t getlast(){
  return last.data;
 }

 /**
  * 获得第一个节点的数据
  * @return 第一个节点的数据
  */
 public t getfirst(){
  return head.data;
 }

 /**
  * 获得链表的长度
  * @return 长度
  */
 public int getsize(){
  return length;
 }

 /**
  * 是否为空链表
  * @return 空链表为true,非空链表为false
  */
 public boolean isempty(){
  return length==0;
 }

 /**
  * 清空链表
  */
 public void clear(){
  head = null;
  length = 0;
 }

 /**
  * 输出链表内所有节点
  */
 public void printlist(){
  if(isempty()){
   system.out.println("空链表");
  }else{
   other = head;
   for(int i=0;i<length;i++){
    system.out.print(other.data+" ");
    other = other.next;
   }
   system.out.println();
  }
 }
}