本文是按照《数据结构与算法分析》一书实现的双向链表的内容，个人认为链表的难点在于插入和删除的操作，但这点也是链表的优势之处。
package DataStructures; import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException; public class MyLinkedList<AnyType> implements Iterable<AnyType> {
/*
* data当前节点的值
* prev当前节点的前缀节点
* next当前节点的后缀节点
* */
private static class Node<AnyType>{
public Node(AnyType d,Node<AnyType> p,Node<AnyType> n){
data=d;
prev=p;
next=n;
}
public AnyType data;
public Node<AnyType> prev;
public Node<AnyType> next;
}
public MyLinkedList() {
doClear();
// TODO Auto-generated constructor stub
}
public void clear(){
doClear();
}
/* doClear()
* 将头结点置空
* 尾节点的前缀置为头节点
* 头结点的后缀为尾节点
* */
private void doClear(){
beginMarker=new Node<AnyType>(null, null, null);
endMarker=new Node<AnyType>(null, beginMarker, null);
beginMarker.next=endMarker;
theSize=0;
modCount++;
} public int size(){
return theSize;
}
public boolean isEmpty(){
return size()==0;
}
/*
* 在链表尾部插入新节点
* */
public boolean add(AnyType x){
add(size(), x);
return true;
}
/*
* 在链表中插入新节点
* */
public void add(int idx,AnyType x){
addBefore(getNode(idx,0,size()),x);
}
public AnyType get(int idx){
return getNode(idx).data;
}
/*
* 修改某个节点的值
* */
public AnyType set(int idx,AnyType newVal){
Node<AnyType> p=getNode(idx);//p为需要修改的节点
AnyType oldVal=p.data;
p.data=newVal;
return oldVal;
}
public AnyType remove(int idx){
return remove(getNode(idx));
} /*
* 在p节点前插入新的节点
* */
private void addBefore(Node<AnyType> p,AnyType x){
Node<AnyType> newNode=new Node<>(x, p.prev, p);//新节点的前缀为p的前缀，后缀为p
newNode.prev.next=newNode;//新节点的前缀的后缀为新节点
p.prev=newNode;//p节点的前缀为p
theSize++;
modCount++;
}
private AnyType remove(Node<AnyType> p){
p.next.prev=p.prev;
p.prev.next=p.next;
theSize--;
modCount++;
return p.data;
}
private Node<AnyType> getNode(int idx){
return getNode(idx,0,size()-1);
}
/*
* 获得某个节点
* */
private Node<AnyType> getNode(int idx,int lower,int upper){
Node<AnyType> p;
if(idx<lower||idx>upper)
throw new IndexOutOfBoundsException();
if(idx<size()/2){//如果节点在前半部分，将从头结点向后开始遍历
p=beginMarker.next;
for(int i=0;i<idx;i++)
p=p.next;
}
else {//如果节点在后半部分，将从尾节点向前遍历
p=endMarker;
for(int i=size();i>idx;i--)
p=p.prev;
}
return p;
}
@Override
public Iterator<AnyType> iterator() {
// TODO Auto-generated method stub
return new LinkedListIterator();
}
private class LinkedListIterator implements Iterator<AnyType>{
private Node<AnyType> current=beginMarker;
private int expectedModCount=modCount;
private boolean okToRemove=false;
public boolean hasNext(){
return current!=endMarker;
}
public AnyType next(){
if(modCount!=expectedModCount)
throw new ConcurrentModificationException();
if(!hasNext())
throw new NoSuchElementException();
AnyType nextItem=current.data;
current=current.next;
okToRemove=true;
return nextItem;
}
public void remove(){
if(modCount!=expectedModCount)
throw new ConcurrentModificationException();
if(!okToRemove)
throw new IllegalStateException();
MyLinkedList.this.remove(current.prev);
expectedModCount++;
okToRemove=false;
}
} private int theSize;//链表的长度
private int modCount;//链表改动的次数
private Node<AnyType> beginMarker;//头结点
private Node<AnyType> endMarker;//尾节点
}