引言
上一次我们实现了泛型栈，并在最后粗略带过栈的迭代器的功能的实现。然而我们注意到我们是用数列去存储数据，但我们实现不定容的栈其实是和数组定容的特性是不搭的，导致我们就被迫建立方法resize,并在resize中使用大规模的数组遍历复制。这明显是比较消耗性能的。所以我们今天采用另外一种方式代替数组来存储数据，这就是链表
链表的介绍
链表你可以想象作一根线上有一颗颗珠子，老实说不是一根线是一段段线，连接相邻的两颗珠子。这样就能将一个个离散的珠子（离散的数据）联系在一起。是的，珠子应该是存储数据的实体，但珠子应该知道它相邻的珠子是谁，否则线没法将他们联系起来，所以就还必须存储这个相邻珠子的具体身份或地址（由于我这里是构建单向链表，所以珠子只需要知道它前一个珠子就行（当然你也可以构建双向的））
由于我觉得珠子其实就是一个个离散的点，所以我们这里将珠子叫作point
综上，可以归结出链表的实现必须依靠一个个point，而point的实现有两点要求
1.存储数据
2.存储上一个point的身份标识（地址）
具体实现
public class Listforstack<T> {
private point first;
private int n;
private class point{
T data;
point last; //存储上一个point的地址
}
public boolean isempty(){
return n==0;
}
public int size(){
return n;
}
public void push(T d){
point oldpoint=first;
first=new point();
first.data=d;
first.last=oldpoint;
n++;
}
public T pop(){
T d=first.data;
first=first.last;
n--;
return d;
}
}
这里point中的point last本来我是想着弄指针的，后来想起这是java不是c++，本身就是指针操作。
其实倘若想实现双向列表的话，只需要在point的定义中添加一个point next存下一个point的地址就行
队列和背包
下面实现队列，简单介绍一下
栈我们知道是数据先进后出
队列和栈差不多不过是先进先出，就好像排队一样，先排的肯定是最先受到服务之类的
下面是利用单向链表的队列的实现
public class Listforqueue<T> {
private point last;
private point first;
private int n;
private class point{
T data;
point next; //存储下一个point的地址
public point(T d) {
data=d;
}
}
public boolean isempty(){
return n==0;
}
public int size(){
return n;
}
public void add(T d){
if(n==0){ //对n=0时特判
last=new point(d);
last.next=null;
first=last;
n++;
}
else{
point oldlast=last;
last=new point(d);
oldlast.next=last;
last.next=null;
n++;
}
}
public T pop(){ //这是清除并返回第一个元素
if(isempty()){
return null ;
}
T d=first.data;
first=first.next; //不怕越界出错，最多是变成null而已
n--;
return d;
}
}
注意这个pop是弹出第一个元素
对了别忘了我们之前的迭代器的实现，其实和我们之前的数组实现栈的方式差不多，下面我就写一个队列的迭代器版本吧
import java.util.Iterator;
public class ListforqueueIter<T> implements Iterable<T>{
private point last;
private point first;
private int n;
private class point{
T data;
point next; //存储下一个point的地址
public point(T d) {
data=d;
}
}
public boolean isempty(){
return n==0;
}
public int size(){
return n;
}
public void add(T d){
if(n==0){ //对n=0时特判
last=new point(d);
last.next=null;
first=last;
n++;
}
else{
point oldlast=last;
last=new point(d);
oldlast.next=last;
last.next=null;
n++;
}
}
public T pop(){ //这是清除并返回第一个元素
if(isempty()){
return null ;
}
T d=first.data;
first=first.next; //不怕越界出错，最多是变成null而已
n--;
return d;
}
//直到为止现在和上面的实现没有任何区别
public Iterator<T> iterator() {
return new Iter();
}
private class Iter implements Iterator<T>{
private point cur=first; //cur表示迭代器当前位置
public boolean hasNext(){
return cur.next!=null;
}
public void remove(){ //这个是删除当前位置的下一个元素
point newnext=cur.next.next;
cur.next.next=null;
cur.next=newnext;
}
public T next(){ //返回当前迭代器元素，迭代器往下移动*1
T d =cur.data;
cur=cur.next;
return d;
}
}
}
注意这里的remove是删除当前迭代器位置的下一个元素，要删除迭代器位置的元素需要依靠双向链表。
网友评论