找回密码
 立即注册

QQ登录

只需一步,快速开始

搜索

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

2014-10-12 16:03| 发布者: zhouy | 查看: 1313 | 收藏

摘要: 为什么出这个真理文档呢?方面以后我们的视频不断跟进,高级部分关于JDK源码的学习,所以有些基本的思维要叙述一下,包括AQS,常用数据结构,线程等等。这一个帖子主要是我以前写的模拟常用数据结构的代码,可能有些bug ...

为什么出这个真理文档呢?方面以后我们的视频不断跟进,高级部分关于JDK源码的学习,所以有些基本的思维要叙述一下,包括AQS,常用数据结构,线程等等。这一个帖子主要是我以前写的模拟常用数据结构的代码,可能有些bug 并且不规范,但是重在学习思维.并没有JDK源码部分考虑多,只是简单的写了一点.分享给大家,关于线程同步器的学习我觉得先会用  然后看源码,接着模拟.好开始数据结构了.


注意:在java数据结构中模拟的话 通过数组和引用可以模拟几乎所有的结构.

链表结构的模拟


1.单向链表

a.基础结构对象:

public class Node {
private Object data;// 存放值
private Node next;// 下一个节点

public   Node(){}


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


b.单向链表接口操作

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();// 输出线性表中的数据元素

}


c. 带头指针的单向链表

public class SLinkList  implements  IList {
private  Node   head;

//初始化一个链表
public   SLinkList()
{
     head=new Node();
}

public    SLinkList(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() {
  this.head.setData(null);
  this.head.setNext(null);
}


//输出链表数据
public void display() {
  
  Node node = head.getNext();// 取出带头结点的单链表中的首结点元素
  while (node != null) {
   System.out.print(node.getData() + " ");// 输出数据元素的值
   node = node.getNext();// 取下一个结点
  }
  System.out.println();// 换行
  
}
   
//得到i位置节点的值
public Object get(int i) throws Exception {
     
  Node  p=head.getNext();//指向首节点 
     int j=0;
     while(j<i && p!=null)//指向i位置节点
     {
       p=p.getNext();
       j++;
     }
     if(j>i)
     {
      throw new Exception("第" + i + "个元素不存在");// 输出异常
     }
  return p.getData();
  
}


//返回当前值的索引
public int indexOf(Object x) {
  
     Node  p=head.getNext();
  int  j=0;
     //遍历所有的节点
  for(int i=0;i<this.length();i++)
  {
    p=p.getNext();
    if(p.getData().equals(x))//找到值
    {
       break;
    }
    j++;
  }
  return j ;
}


//i位置之前插入节点x
public void insert(int i,Object x) throws Exception {
  
  //开始节点
  Node  p=head;
  //找到i位置的前驱节点
  int  j=-1;
  while(j<i-1 && p!=null)
  {
   p=p.getNext();
   j++;
  }
  if(j>i-1 || p==null)
  {
   throw new Exception("插入位置不合法!");
  }
     //创建一个Node节点
  Node   node=new Node(x);
  node.setNext(p.getNext());
  p.setNext(node);
  
}

//判断是否为空
public boolean isEmpty() {
  
  //只要头指针为空说明就是空链表
  return (this.head.getNext()==null);
}
   

//求链表的长度
public int length() {
  
  Node p = head.getNext();// 初始化,p指向首结点,length为计数器
  int length = 0;
  while (p != null) {// 从首结点向后查找,直到p为空
   p = p.getNext();// 指向后继结点
   length++;// 长度增1
  }
  return length;
}
  
//删除节点
public void remove(int i) throws Exception {
    
  //找到当前节点的前驱
  Node  p=head;
  //位置
  int  j=-1;
  while(j<i-1 && p!=null)
  {
   p=p.getNext();
   j++;
  }
  if(j>i-1 || p==null)
  {
    throw  new Exception("删除位置不对!!");
  }
  //设置为下一个节点
  p.setNext(p.getNext().getNext());
  

//删除所有值为x节点
public   void  removeAll(Object x)
{
    Node  p=head.getNext();//指向首节点
    for(int i=0;i<this.length();i++)
    {
      p=p.getNext();
      if(p.getData().equals(x))
      {
        try {
      this.remove(i);
     } catch (Exception e) {
      
      e.printStackTrace();
     }
      }
    }
}

//head->a->b->c->d  head->d->c->b->a  步骤是:head->a,head->b-a,head->c->b->a,head->d->c->b->a
public void reverse() {
   
   //得到首节点
   Node  p=head.getNext();
   head.setNext(null);
   //辅助节点
   Node  q=null;
   while(p!=null)
   {   
    //记录下一个节点
    q=p.getNext(); 
    p.setNext(head.getNext());
    head.setNext(p);
    p=q; 
   }
}

public Node getHead() {
  return head;
}
public void setHead(Node head) {
  this.head = head;
}
  }

e.不带头节点的链表

public class SLinkList2 implements IList {
private Node head;// 单链表的首结点指针
//构造函数
public SLinkList2() {
  //不带头指针
  head = null;
}
public    SLinkList2(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 = null;
}

// 判断当前单链表是否为空
public boolean isEmpty() {
  return head == null;
}


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


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


// 在单链表中第i个数据元素之前插入一个值为x的数据元素
public void insert(int i, Object x) throws Exception {
  
  Node  s=new  Node(x);
  //当插入的是head处插入的时候
  if(i==0)
  {
   s.setNext(head);
   head=s;
   return;
  }
  int  j=0;//计数器 从0开始
     Node p=head;
     while(j<i-1 && p!=null)
     {
       p=p.getNext();//遍历到i-1的位置
       j++;
     }
     if(j>i-1 &&  p==null)
     {
       throw  new  Exception("插入数据位置有问题!!");
     }
     s.setNext(p.getNext());
  p.setNext(s);
  
}


// 将线性表中第i个数据元素删除。其中i取值范围为:0≤i≤length()- 1,如果i值不在此范围则抛出异常
public void remove(int i) throws Exception {
  
  Node   p=head;
  Node   q=null;//记录p节点的前驱节点
  //计数器
  int  j=0;
  while(j<i && p !=null)
  {
      q=p;
      p=p.getNext();
      j++;
  }
  if(j>i && p==null)
  {
    throw new  Exception("删除的问题异常!!");
  }
  if(q==null)//说明只有首节点
  {   
    head=p.getNext();
  }
  else
  {
    q.setNext(p.getNext());
  }
}


// 实现删除单链表中数据域值等于x的第一个结点的操作。若删除成功,则返回被删除结点的位置;否则,返回-1。
public int remove(Object x) {
  
  Node p = head;// 初始化,p指向首结点
  Node q = null; // q用来记录p的前驱结点
  int j = 0; // j为计数器
  while (p != null && !p.getData().equals(x)) {// 从单链表中的首结点元素开始查找,直到p.getData()指向元素x或到达单链表的表尾
   q = p;
   p = p.getNext();// 指向下一个元素
   j++;// 计数器的值增1
  }
  if (p != null && q == null) // 删除的是单链表中的首结点
   head = p.getNext();
  else if (p != null) {// 删除的是单链表中的非首结点
   q.setNext(p.getNext());
  } else
   return -1;// 值为x的结点在单链表中不存在
  return j;
  
}


// 在带头结点的单链表中查找值为x的元素,如果找到,则函数返回该元素在线性表中的位置,否则返回-1
public int indexOf(Object x) {
  
  Node p = head;// 初始化,p指向首结点,j为计数器
  int j = 0;
  while (p != null && !p.getData().equals(x)) {// 从单链表中的首结点元素开始查找,直到p.getData()指向元素x或到达单链表的表尾
   p = p.getNext();// 指向下一个元素
   ++j;// 计数器的值增1
  }
  if (p != null)// 如果p指向表中的某一元素
   return j;// 返回x元素在顺序表中的位置
  else
   return -1;// x元素不在顺序表中
}
// 输出线性表中的数据元素
public void display() {
  
  Node node = head;// 取出带头结点的单链表中的首结点元素
  while (node != null) {
   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实现高效并发
守望者:在并发处理应用中,一般使用锁的方式来解决竞争问题,但锁的效率比较
【守望者 大数据】Mahout学习路线图
【守望者 大数据】Mahout学习路线图
Hadoop家族产品,常用的项目包括Hadoop, Hive, Pig, HBase, Sqoop, Mahout, Z
【守望者  j2se】吃透 java I/O 工作机制-1
【守望者 j2se】吃透 java I/O 工作机
I/O 问题可以说是当今互联网 Web 应用中所面临的主要问题之一,因为当前在这
【守望者 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