hanyujianke 2019-11-07
这是书上的一道练习题,要求创建一个双向链表数据结构Ring,它是一个环形的结构,Ring必须支持从当前位置单步地前进或回退。
add方法在当前元素之后添加元素,支持使用for-each。任何因环空而导致的无效操作,Ring类支持抛出适当的异常。
此外,不能继承LinkedList,也就是说只能自己单写一个。
解题的思路很简单,既然LinkedList就满意要求,那么再做一个LinkedList就可以了。
直接拿LinkedList源码来分析。
首先LinkedList创建了一个内部结点类:Node<E>。
public boolean add(E e){
linkLast(e);
return true;
}
void linkLast(E e){
//将末尾的结点赋给l
final Node<E> l = last;
//通过将参数设置为(之前最后的元素,元素本身,null)创建一个位于末尾的新结点
final Node<E> newNode = new Node<E>(l, e, null);
//使last指向新结点
last = newNode;
//如果l为空指向
if(l == null){
//那么使first指向新结点。这句一眼看上去可能不太好明白,为什么当末尾指向为空的时候,要把新结点赋给首。
//我的理解是这样的,一上来的话first和last都是指向null,那么程序发现之后将first指向新结点就是OK的,因为这就等于原本为空的集合给添加了一个头部。
first = newNode;
}
else
//否则使l的下一元素指向新结点。进行这一操作的目的是为了之前为空的last.next连接到新的结点。
l.next = newNode;
//大小增加1
size++;
}
这只是一个双向链表的add方法,我要的是环形链表,该修改哪里呢?
环形,顾名思义,就是首尾相连。
在首尾之外的部分,双向链表的实现就已经满足了我们的需求,所以主要的问题是首与尾的衔接。
说到首尾衔接,那么主要考虑以下三种情况就可以覆盖到所有的数据情况了。
一,集合中只有一个元素,那么它同时是首也是尾。
二,集合中有两个元素,那么首的尾部元素是尾的首部元素,同时尾的尾部元素也是首的首部元素。形像点的表示:结点1(A,B,C)结点2(C,D,A)
三,集合中有三个元素,与二很相似,只不过结点1和3之间由2连接。例如:结点1(A,B,C)结点2(C,D,E)结点3(E,F,A)
那么就可以相对于双向链表进行提炼总结一下,其实就是,首结点的首,是尾结点的尾。
在双向链接表中,首结点的首为null,尾结点的尾同样也null,那么在环形中,只要将这两处的null,改变为引用彼此就对了。
咱们可以这样做,在向尾部添加新的结点时,默认的第三个参数不填null,填first。(l, e, first)
这样就可以把尾位结点的尾位元素连接到首位。
然后可以在l.next = newNode;后面加上一句,first.prev = newNode,这样就可以把首位结点的首位连接到最新加入的末尾元素中,构成环形。
这样一来,比如说一上来,newNode1的三个参数(l, e, first)其中,l和first都为null。
创建完这个结点之后,将结点赋给last。
last = newNode1;此时的last结点为(null, e, null)
然后l为空,那么first = newNode;那么first的结点为(null, e, null)
之后继续向尾添加新结点。
那么此时last的三个参数就变成(newNode1,e,newNode1)
而它前面的newNode1就变成(null, e, newNode2)
(1,2,3)(2,4,1) (1,2,3)(2,4,5) first.prev = newNode;
(6,1,3)(3,4,5)(5,6,1) (1,2,3)(3,4,5)(5,6,7)
可以成功add之后,我们还需要使这个类可以进行for each遍历。
一个类,若想让它可以进行for each遍历,就需要将这个类实现Iterable,for each就是通过Iterable接口在序列中进行移动。
public interface Iterable
{
public abstract Iterator iterator();
}
这个接口中定义了一个需要返回Iterator迭代器的方法;
那么我们再看看Iterator接口:
public interface Iterator
{
public abstract boolean hasNext();
public abstract Object next();
public abstract void remove();
}
一共需要实现这三个方法。