首页 > 代码库 > 单向链表模拟
单向链表模拟
为什么出这个真理文档呢？方面以后我们的视频不断跟进，高级部分关于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 = http://www.mamicode.com/data;
this.next = next;
}
public Object getData() {
return data;
}
public void setData(Object data) {
this.data = http://www.mamicode.com/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();// 换行
}
}
小结:是否带头指针主要是头部链表的操作要单独处理.
注意：在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 = http://www.mamicode.com/data;
this.next = next;
}
public Object getData() {
return data;
}
public void setData(Object data) {
this.data = http://www.mamicode.com/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();// 换行
}
}
小结:是否带头指针主要是头部链表的操作要单独处理.
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。