Java中LinkedList类的实

在考虑设计方面呢，这里需要提供三个类

1.MyLinkedList本身，它包含到两端的链，表的大小以及一些方法

2.Node类，他可能是一个私有的嵌套类，一个节点包含数据以及到前一个节点的链和到下一个节点的链，还有一些适当的构造方法

3.LinkedListIterator类，该类抽象了位置的概念，是一个私有类，并且实现了接口Iterator，他提供了next,hasNext,和remove的实现

今天写这个类实现的原因：网上的资料，太少，我这也算是补充吧，仅供参考

package com.zdw.MyLinkList;

import java.nio.channels.IllegalSelectorException;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;

public class MyLinkList<T> implements Iterable<T> {

	private static class Node<T>{
		public Node(T t,Node<T> p,Node<T> n){
			data = t;
			prev = p;
			next = n;
		}
		public T data;
		public Node<T> prev;
		public Node<T> next;
		
	}
	public void clear(){
		beginMarker = new Node<T>(null,null,null);
		endMarker = new Node<T>(null,beginMarker,null);
		beginMarker.next = endMarker;
		theSize = 0;
		modCount ++;
	}
	public int size(){
		return theSize;
	}
	
	public boolean add(T x){
		add(size(),x);
		return true;
	}
	
	public void add(int idx,T x){
		addBefore(getNode(idx), x);
	}
	
	public T get(int idx){
		return getNode(idx).data;
	}
	
	public T set(int idx,T newVal){
		Node<T> p = getNode(idx);
		T oldVal = p.data;
		p.data = newVal;
		return oldVal;
	}
	
	public T remove(int idx){
		return remove(getNode(idx));
	}
	
	private T remove(Node<T> p){
		p.next.prev = p.prev;
		p.prev.next = p.next;
		theSize--;
		modCount++;
		return p.data;
	}
	private void addBefore(Node<T> p,T t){
		Node<T> newNode = new Node<T>(t,p.prev,p);
		newNode.prev.next = newNode;
		p.prev = newNode;
		theSize++;
		modCount++;
	}
	
	private Node<T> getNode(int idx){
		Node<T> p;
		if(idx <0 || idx>size()){
			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;
	}
	private int theSize;
	private int modCount = 0;
	private Node<T> beginMarker;
	private Node<T> endMarker;
	@Override
	public Iterator<T> iterator() {
		return new LinkedListIterator();
	}
	
	private class LinkedListIterator implements Iterator<T>{

		private Node<T> current = beginMarker.next;
		private int expectedModeCount = modCount;
		private boolean okToRemove = false;
		@Override
		public boolean hasNext() {
			return current !=endMarker;
		}

		@Override
		public T next() {
			if(modCount !=expectedModeCount){
				throw new ConcurrentModificationException();
			}
			if(!hasNext()){
				throw new NoSuchElementException();
			}
			T nextItem = current.data;
			current  = current.next;
			okToRemove = true;
			return nextItem;
		}

		@Override
		public void remove() {
			if(modCount != expectedModeCount){
				throw new ConcurrentModificationException();
			}
			if(!okToRemove){
				throw new IllegalSelectorException();
			}
			MyLinkList.this.remove(current.prev);
			okToRemove = false;
			expectedModeCount++;	
		}	
	}
}

参考资料：数据结构与算法分析(java语言描述)