找回密码
 立即注册

QQ登录

只需一步,快速开始

搜索

[ JAVA开发技术 ] 【守望者 j2se】双向链表模拟

2014-10-12 15:56| 发布者: zhouy | 查看: 4575 | 收藏

摘要: 我们熟悉了java单向链表的模拟,现在我就必须开始双向链表的模拟的.1.基础结构对象DuLNodepublic class DuLNode {private Object data;// 存放结点值private DuLNode prior; // 前驱结点的引用private DuLNode next; ...

我们熟悉了java单向链表的模拟,现在我就必须开始双向链表的模拟的.


1.基础结构对象DuLNode

public class DuLNode {

private Object data;// 存放结点值
private DuLNode prior; // 前驱结点的引用
private DuLNode next; // 后继结点的引用
public DuLNode() {// 无参数时的构造函数
this(null);

}
public DuLNode(Object data) {// 构造值为data的结点
  this.data = data;
  this.prior = null;
  this.next = null;
}
public Object getData() {
  return data;
}
public DuLNode getNext() {
  return next;
}
public DuLNode getPrior() {
  return prior;
}
public void setData(Object data) {
  this.data = data;
}
public void setNext(DuLNode next) {
  this.next = next;
}
public void setPrior(DuLNode prior) {
  this.prior = prior;
}
}


2.双向链表操作接口类


public interface IList {

public void clear(); // 将一个已经存在的线性表置成空表
public boolean isEmpty(); // 判断当前线性表中的数据元素个数是否为0,若为0则函数返回true,否则返回false
public int length(); // 求线性表中的数据元素个数并由函数返回其值
public Object get(int i) throws Exception;// 读取到线性表中的第i个数据元素并由函数返回其值。其中i取值范围为:0≤i≤length()-1,如果i值不在此范围则抛出异常
public void insert(int i, Object x) throws Exception;// 在线性表的第i个数据元素之前插入一个值为x的数据元素。其中i取值范围为:0≤i≤length()。如果i值不在此范围则抛出异常,当i=0时表示在表头插入一个数据元素x,当i=length()时表示在表尾插入一个数据元素x
public void remove(int i) throws Exception;// 将线性表中第i个数据元素删除。其中i取值范围为:0≤i≤length()- 1,如果i值不在此范围则抛出异常
public int indexOf(Object x);// 返回线性表中首次出现指定元素的索引,如果列表不包含此元素,则返回 -1
public void display();// 输出线性表中的数据元素

}




3. 双向循环链表及其基本操作
public class DuLinkList  implements  IList{
  
private DuLNode head;// 双向循环链表的头结点
// 双向链表的构造函数
public DuLinkList() {
  head = new DuLNode(); //初始化头结点
  head.setPrior(head);//初始化头结点的前驱和后继
  head.setNext(head);
}
//n为该双向链表的元素个数
public DuLinkList(int n) throws Exception {
  this();
  Scanner sc=new Scanner(System.in);// 构造用于输入的对象
  for (int j = 0; j < n; j++)
   insert(j,sc.next());//生成新结点,插入到表头
}


// 在双向循环链表的第i个数据元素之前插入一个值为x的数据元素,i等于表长时,p指向头结点;i大于表长时,p=NULL。
// 其中i取值范围为:0≤i≤length()。当i=0时表示在表头插入一个数据元素x,当i=length()时表示在表尾插入一个数据元素x
public void insert(int i, Object x) throws Exception {
  
  DuLNode p = head.getNext();// 初始化,p指向首结点,j为计数器
  int j = 0;
  while (p!=null && j < i) {// 寻找插入位置i
   p = p.getNext();// 指向后继结点
   j++;// 计数器的值增1
  }
  if (j>i && p==null)// i小于0或者大于表长
  {
   throw new Exception("插入位置不合理");
  }
  
        //生成新结点
  DuLNode s = new DuLNode(x);
  //i位置之前
  s.setNext(p);
  s.setPrior(p.getPrior());
  p.getPrior().setNext(s);
  p.setPrior(s);
  
}



// 将双向循环链表中第i个数据元素删除。其中i 取值范围为:0≤i≤ength()-1
public void remove(int i) throws Exception {
  
  DuLNode p = head.getNext();// 初始化,p指向首节点结点,j为计数器
  int j = 0;
  while (p!=head && j < i) {// 寻找删除位置i
   p = p.getNext();// 指向后继结点
   j++;// 计数器的值增1
  }
  if (j>i) // i小于0或者大于表长减1
   throw new Exception("删除位置不合理");// 输出异常
  
      p.getPrior().setNext(p.getNext());
   p.getNext().setPrior(p.getPrior());
}
// 将一个已经存在的双向循环链表置成空表
public void clear() {
  
  head.setPrior(head);
  head.setNext(head);
}


// 判断当前双向循环链表是否为空
public boolean isEmpty() {
  return head==head.getNext();
}


// 读取双向循环链表中的第i个数据元素
public Object get(int i) throws Exception {
  
  DuLNode p = head.getNext();// 初始化,p指向首结点,j为计数器
  int j = 0;
  while (p!=head && j < i) {// 从首结点向后查找,直到p指向第i个元素或p指向头结点
   p = p.getNext();// 指向后继结点
   ++j;// 计数器的值增1
  }
  if (j > i || p==head) { // i小于0或者大于表长减1
   throw new Exception("第" + i + "个元素不存在");// 输出异常
  }
  return p.getData();// 返回元素p
}


// 求双向循环链表中的数据元素个数并由函数返回其值
public int length() {
  DuLNode p = head.getNext();// 初始化,p指向首结点,length为计数器
  int length = 0;
  while (p!=head) {// 从首结点向后查找,直到p指向头结点
   p = p.getNext();// 指向后继结点
   length++;// 长度增1
  }
  return length;
}


// 在双向循环链表中查找值为x的元素,如果找到,则函数返回该元素在线性表中的位置,否则返回-1
public int indexOf(Object x) {
  DuLNode p = head.getNext();// 初始化,p指向首结点,j为计数器
  int j = 0;
  while (p!=head && !p.getData().equals(x)) {// 从链表中的首结点元素开始查找,直到p.getData()指向元素x或到达链表的表尾
   p = p.getNext();// 指向下一个元素
   j++;// 计数器的值增1
  }
  if (p!=head)// 如果p指向表中的某一元素
   return j;// 返回x元素在顺序表中的位置
  else
   return -1;// x元素不在顺序表中
}
//双向链表输出
public  void  reverse()
{
  DuLNode  p=head.getNext();
  head.setNext(null);
  DuLNode  q=null;
  while(p!=head)
  {
   //保存下一个值
   q=p.getNext();
      p.setNext(head.getNext());
      p.setPrior(head);
      head.setNext(p);
      p=q;
  }
}

public void display() {
  DuLNode node = head.getNext();// 取出带头结点的双向链表中的首结点
  while (node!=head &&  node!=null) {
   System.out.print(node.getData() + " ");// 输出数据元素的值
   node = node.getNext();
   
  }
  System.out.println();
}
public DuLNode getHead() {
  return head;
}
public void setHead(DuLNode head) {
  this.head = head;
}
}


小结:假如是循环链表呢?大家不妨自己写写,我这里提供一个带头的循环链表的代码如下:


public class CircleLinkList implements IList{
    
//头节点
public Node head;
// 自连接的循环链表
public CircleLinkList() {
  
  head = new Node();
  head.setNext(head);
  
}

public Node getHead() {
  return head;
}
public void setHead(Node head) {
  this.head = head;
}
    
public   CircleLinkList(int n,boolean  order)
{  
   this();//初始化
      if(order)
      {
         create1(n);//用尾插入法插入链表
      }
      else
      {
         create2(n);//用头插法逆位序建立单链表
      }
}

//用尾插入法插入链表
public  void  create1(int  n)
{   
  //输入数据
  Scanner  sc=new  Scanner(System.in);
  for(int i=0;i<n;i++)
  {
   try {
    
    this.insert(this.length(),sc.next());
    
   } catch (Exception e) {
    e.printStackTrace();
   }
  }
}


//用头插法逆位序建立单链表
public   void   create2(int  n)
{   
        //输入数据
  Scanner  sc=new   Scanner(System.in);
  for(int i=0;i<n;i++)
  {
    try {
    this.insert(0,sc.next());// 生成新结点,插入到表头
   } catch (Exception e) {
   
    e.printStackTrace();
   }
  }
}
  

// 将一个已经存在的带头结点的循环单链表置成空表
public void clear() {
  head.setNext(head);//清空链表
}


// 判断当前带头结点的循环单链表是否为空
public boolean isEmpty() {
  return head.getNext().equals(head);
}


// 求带头结点的循环单链表中的数据元素个数并由函数返回其值
public int length() {
     //取得首节点
  Node p=head.getNext();
     int  length=0;
     while(p!=head)
     {
      p=p.getNext();
      length++; 
     }
     return  length;
}



// 读取带头结点的循环单链表中的第i个数据元素
public Object get(int i) throws Exception {
  Node p = head.getNext();// 初始化,p指向首结点,j为计数器
  int j = 0;
  while (p!=head && j < i) {// 从首结点向后查找,直到p指向第i个元素或p指向头结点
   p = p.getNext();// 指向后继结点
   ++j;// 计数器的值增1
  }
  if (j > i || p==head) { // i小于0或者大于表长减1
   throw new Exception("第" + i + "个元素不存在");// 输出异常
  }
  return p.getData();// 返回元素p
}


//在带头结点的循环单链表中第i个数据元素之前插入一个值为x的数据元素
public void insert(int i, Object x) throws Exception {
  
  Node p = head;// 初始化p为头结点,j为计数器
  int j = -1; // 第i个结点前驱的位置
  while ((p!=head || j == -1) && j < i - 1) {// 寻找i个结点的前驱
   
   p = p.getNext();
   j++;// 计数器的值增1
   
  }
  if (j > i - 1 || (p==head  && j != -1)) // i不合法
   
   throw new Exception("插入位置不合理");// 输出异常
  Node s = new Node(x); // 生成新结点
  s.setNext(p.getNext());// 插入单链表中
  p.setNext(s);
  
}



// 将循环单链表中第i个数据元素删除。其中i取值范围为:0≤i≤length()- 1,如果i值不在此范围则抛出异常
public void remove(int i) throws Exception {
  
  Node p = head.getNext();// p指向要删除结点的前驱结点
  int j = -1;
  while((p!=head || j == -1) && j < i - 1) {// 寻找i个结点的前驱
   p=p.getNext();
   ++j;// 计数器的值增1
  }
  if(j > i - 1 || p==head) { // i小于0或者大于表长减1
   
   throw new Exception("删除位置不合理");// 输出异常
  }
  
  p.setNext(p.getNext().getNext());// 删除结点
}


// 在带头结点的循环单链表中查找值为x的元素,如果找到,则函数返回该元素在线性表中的位置,否则返回-1
public int indexOf(Object x) {
  Node p = head.getNext();// 初始化,p指向首结点,j为计数器
  int j = 0;
  while (p!=head && !p.getData().equals(x)) {// 从单链表中的首结点元素开始查找,直到p.getData()指向元素x或到达单链表的表尾
   p = p.getNext();// 指向下一个元素
   j++;// 计数器的值增1
  }
  if (!p.equals(head))// 如果p指向表中的某一元素
   return j;// 返回x元素在顺序表中的位置
  else
   return -1;// x元素不在顺序表中
}


// 输出循环链表中的数据元素
public void display() {
  Node node = head.getNext();// 取出带头结点的单链表中的首结点元素
  while (!node.equals(head)) {
   System.out.print(node.getData() + " ");// 输出数据元素的值
   node = node.getNext();// 取下一个结点
  }
  System.out.println();// 换行
}
}

推荐阅读

【守望者  j2se】ConcurrentHashMap原理分析
【守望者 j2se】ConcurrentHashMap原
集合是编程中最常用的数据结构。而谈到并发,几乎总是离不开集合这类高级数据
【守望者  j2se】双向链表模拟
【守望者 j2se】双向链表模拟
我们熟悉了java单向链表的模拟,现在我就必须开始双向链表的模拟的.1.基础结构
【守望者 高并发】现有高并发WEB服务器 lighttpd Apache Nginx比较
【守望者 高并发】现有高并发WEB服务器
lighttpd网络服务器基于的Lighttpd的网络服务器具有这样的特点:占用内存资源
【守望者 高并发】C10K/C500K与I/O框架
【守望者 高并发】C10K/C500K与I/O框架
C10K、C/500K问题C10K 的意思是10000并发请求,C500K意思是500 000并发请求,
【守望者  JMM】理解volatile内存语义
【守望者 JMM】理解volatile内存语义
理解volatile变量对写多线程程序还是很有帮助的,这样就会避免一上来就是syn这
【守望者  j2se】虚拟机各部分内存溢出情况
【守望者 j2se】虚拟机各部分内存溢出
通过简单的小例子程序,演示java虚拟机各部分内存溢出情况:(1).java堆溢出:
【守望者 高并发】使用CAS实现高效并发处理
【守望者 高并发】使用CAS实现高效并发
守望者:在并发处理应用中,一般使用锁的方式来解决竞争问题,但锁的效率比较
【守望者  j2se】吃透 java I/O 工作机制-1
【守望者 j2se】吃透 java I/O 工作机
I/O 问题可以说是当今互联网 Web 应用中所面临的主要问题之一,因为当前在这
【守望者 大数据】Mahout学习路线图
【守望者 大数据】Mahout学习路线图
Hadoop家族产品,常用的项目包括Hadoop, Hive, Pig, HBase, Sqoop, Mahout, Z
【守望者 j2se】ConcurrentMap之putIfAbsent(key,value)用法讨论
【守望者 j2se】ConcurrentMap之putIfA
先看一段代码:public class Locale { private final static MapString, Lo
【守望者  javascript】判断IE浏览器世界上最短的代码
【守望者 javascript】判断IE浏览器世
最短的IE判定var ie=!-分析以前最短的IE判定借助于IE不支持垂直制表符的特性
【守望者 大数据】机器学习已成为大数据的基石
【守望者 大数据】机器学习已成为大数
机器学习(Machine Learning, ML)是一门多领域交叉学科,涉及概率论、统计学、
【守望者  j2se】多线程与并发知识点总结
【守望者 j2se】多线程与并发知识点总
对于多线程和并发编程这个比较大的技术模块,我们会整理一些帖子方便知识点的
【守望者  j2se】二叉树模拟
【守望者 j2se】二叉树模拟
接着我们就要写一个比较复杂的数据结构的,但是这个数据结构是很重要的,假如
【守望者 SRS  】SRS 源代码分析笔记(0.9.194)-分析服务器对端口的监听 ...
【守望者 SRS 】SRS 源代码分析笔记(
第一部分 分析服务器对端口的监听 端口监听与初始化(一)全局变量_srs_confi

行业聚焦  面试交流  职位推荐  开发视频   技术交流  腾讯微博  新浪微博

友情链接:课课家教育  阿里云  鲜果  W3Cfuns前端网  中国企业家  环球企业家  投资界  传媒梦工场  MSN中文网  Android开发者社区  cnbeta  投资中国网  又拍云存储  美通说传播  IT茶馆  网商在线  商业评论网  TechOrange  IT时代周刊  3W创新传媒  开源中国社区  二维工坊  Iconfans  推酷  智能电视网  FreeBuf黑客与极客  财经网  DoNews  凤凰财经  新财富  eoe移动开发者社区  i黑马  网易科技  新浪科技  搜狐IT  创业家  创业邦  腾讯财经  福布斯中文网  天下网商  TechWeb  雷锋网  新浪创业  和讯科技  品途O2O  极客公园  艾瑞网  抽屉新热榜  卖家网  人民网通信频道  拉勾网  创新派  简单云主机  

手机版|黑名单|守望者在线 在线教育 linux 高级程序设计 C/C++ 大数据 ( 蜀ICP备14029946号

成都守望者科技有限公司 © 2013-2016 All Rights Reserved