创建一个双向链表数据结构

hanyujianke 2019-11-07

这是书上的一道练习题,要求创建一个双向链表数据结构Ring,它是一个环形的结构,Ring必须支持从当前位置单步地前进或回退。

add方法在当前元素之后添加元素,支持使用for-each。任何因环空而导致的无效操作,Ring类支持抛出适当的异常。

此外,不能继承LinkedList,也就是说只能自己单写一个。

解题的思路很简单,既然LinkedList就满意要求,那么再做一个LinkedList就可以了。

直接拿LinkedList源码来分析。

首先LinkedList创建了一个内部结点类:Node<E>。

    private static class Node<E> {  
        E item;  
        Node<E> next;  
        Node<E> prev;  
  
        Node(Node<E> prev, E element, Node<E> next) {  
            this.item = element;  
            this.next = next;  
            this.prev = prev;  
        }  
    }  
  每个结点中都包含前一结点,当前结点和后一结点的信息。
 
   //定义大小的变量size
    transient int size = 0;  
      
    //定义一个指向头结点的变量first 
    transient Node<E> first;  
      
    //定义一个指向尾结点的变量last  
    transient Node<E> last;  
 
//然后是主要的add方法

public boolean add(E e){
linkLast(e);
return true;
}

//主要解释一下add方法中调用的linkLast方法
//这个方法的作用就是将一个新的元素加到集合的末尾

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();
}

 一共需要实现这三个方法。