Java数据结构 LinkedList实现及详解

import java.util.Iterator; import java.util.ConcurrentModificationException; import java.util.NoSuchElementException; /** * 如果对正在迭代的集合进行结构上的改变（增删），那么这个迭代器就不再合法，而使用迭代器的remove方法时，这个迭代器仍然是合法的。 * * * @param size length of the list */ //Collection接口扩展了Iterable，LinkedList是Collection的一个实例。 public class MyLinkedList<T> implements Iterable<T>{ private int size; //记录该链表的改动次数。当使用迭代器时，迭代器的modCount和集合的modCount不符时， //表明集合做了修改，迭代器不合法，抛出ConcurrentModificationException异常 private int modCount=0; //额外节点.优点：排除特殊情形进而简化了编码 private Node<T> beginMarker; //标记节点，头节点的引用 private Node<T> endMarker; //标记节点，尾节点的引用 //嵌套类Node，定义单个节点 private static class Node<T>{ public T data; public Node<T> prev; public Node<T> next; //构造函数 Node(T d,Node<T> p,Node<T> n ){ data=d; prev=p; next=n; } } //构造函数，初始化LinkedList public MyLinkedList(){ doClear(); } //清除LinkedList的内容 public void clear(){ doClear(); } private void doClear(){ beginMarker=new Node<T> (null,null,null); endMarker=new Node<T> (null,beginMarker,null); //将endMarker连接到beginMarker beginMarker.next=endMarker; //将beginMarker连接到endMarker size=0; //记录每一次的修改 modCount++; } //返回当前LinkedList的大小 public int size(){ return size; } //判断当前LinkedList是否为空表 public boolean isEmpty(){ return size() == 0; } //得到索引为idx的节点的引用 private Node<T> getNode(int idx,int lower,int upper){ Node<T> p; //检查idx合法性 if (idx < lower || idx > upper) throw new IndexOutOfBoundsException(); //一分为二，节约时间 //idx在链表的前半部分，则从头结点向后查找 if (idx < size()/2){ p=beginMarker.next; for (int i=0;i < idx;i++) p=p.next; } else{ //idx在链表的后半部分，从尾节点向前查找 p=endMarker; for(int i = size();i > idx;i--) p=p.prev; } return p; } //得到索引为idx的节点的引用 private Node<T> getNode(int idx){ return getNode(idx,0,size()-1); } //两个add函数，方法重载 //在尾部添加新节点，节点的data为x public boolean add(T x){ add(size(),x); return true; } //在下标为idx的节点前添加新节点。在此体现标记节点的好处。 public void add(int idx,T x){ addBefore(getNode(idx,0,size()),x); } /** * add a item to this collection, at special position p. * Items at or after that position are slid one position higher * @param p Node to add before * @param x T object * @throws IndexOutOfBoundsException if idx is not between 0 and size() * */ private void addBefore(Node<T> p,T x){ //构造新节点newNode，同时把newNode的prev指向p的前一个节点(p.prev)把newNode的next指向p Node<T> newNode = new Node<>(x,p.prev,p); //让P节点的前面一个节点的next链指向newNode，锦衣完成连接 newNode.prev.next = newNode; //让p的prev链指向newNode。连接完成！ p.prev=newNode; //记录改动后链表的状态 size++; modCount++; } //得到下标为idx的节点的data public T get (int idx){ return getNode(idx).data; } //设置下标为idx的节点的值为newVal public T set(int idx,T newVal){ Node<T> p=getNode(idx); T oldVal=p.data; //存储当前值 p.data=newVal; //更新为newVal return oldVal; } //删除链表中下标为idx的节点 public T remove(int idx){ return remove(getNode(idx)); //返回删除节点的data } private T remove(Node<T> p){ p.next.prev=p.prev; //把p节点的后继节点的prev链指向p的前驱节点 p.prev.next=p.next; //把p的前驱节点的next链指向p的后继节点 //记录修改状态并返回删除的data size--; modCount++; return p.data; } //返回迭代器的实例 public Iterator<T> iterator(){ return new LinkedListIterator(); } //私有内部类 private class LinkedListIterator implements Iterator<T>{ // 创建一个新的引用current指向链表的第一个节点 private Node<T> current=beginMarker.next; //expectedModCount参见5、15、16行 private int expectedModCount=modCount; //节点只有在被存储好了状态信息之后才能被删除，不然会导致链断裂 private boolean okToRemove=false; //当前节点非尾节点时，就任然有下一项 public boolean hasNext(){ return current != endMarker; } public T next(){ //expectedModCount参见5、15、16行 if (modCount != expectedModCount) throw new ConcurrentModificationException(); //当前节点的信息未被存储 if (!okToRemove) throw new NoSuchElementException(); //存储当前节点的信息 T nextItem = current.data; current=current.next; //节点信息存储完，当前节点可以删除。 okToRemove=true; return nextItem; } public void remove(){ if (modCount != expectedModCount) throw new ConcurrentModificationException(); if (!okToRemove) throw new IllegalStateException(); //next链已经指向当前节点的后继，current.prev删除当前节点 MyLinkedList.this.remove(current.prev); //记录修改信息 expectedModCount++; okToRemove=false; } } }