My集合框架第一弹 LinkedList篇

package com.wpr.collection;

import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;

public class MyLinkedList<AnyType> implements Iterable<AnyType> {
	private Node<AnyType> begin;
	private Node<AnyType> end;
	private int size;
	private int modCount;
	
	private static class Node<AnyType>{
		public AnyType data;
		public Node<AnyType> pre;
		public Node<AnyType> next;
		public Node(AnyType data, Node<AnyType> pre, Node<AnyType> next) {
			super();
			this.data = data;
			this.pre = pre;
			this.next = next;
		}
	}
	
	public MyLinkedList(){
		clear();
	}

	private void clear() {
		begin = new Node<AnyType>(null,null, null);
		end = new Node<AnyType>(null,begin,null);
		size = 0;
		modCount++;
		begin.next = end;
	}
	
	public int size(){
		return this.size;
	}
	public boolean isEmpty() {
		return size==0;
	}
	
	public boolean add(AnyType x){
		add(size(),x);
		return true;
	}

	public AnyType find(int idx){
		return getNode(idx).data;
	}
	
	public AnyType remove(int idx){
		return remove(getNode(idx));
	}
	/**
	 * 根据下标修改节点的值
	 * @param idx  具体下标
	 * @param p	   新的值
	 * @return  原来节点的值
 	 */ 
	public AnyType set(int idx,AnyType p){
		Node<AnyType> temp = getNode(idx);
		AnyType old = temp.data;
		temp.data = p;
		return old;
	}
	private AnyType remove(Node<AnyType> node) {
		node.pre.next = node.next;
		node.next.pre = node.pre;
		size--;
		modCount++;
		return node.data;
	}
	public Iterator<AnyType> iterator(){
		return new LinkedListIterator();
	}
	//内部类
	private class LinkedListIterator implements Iterator<AnyType>{
		private Node<AnyType> current = begin.next;
		private int expectedModCount = modCount;
		private boolean okToRemove = false;
		
		@Override
		public boolean hasNext() {
			return current != end;
		}

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

		@Override
		public void remove() {
			if(modCount!=expectedModCount){
				throw new ConcurrentModificationException();
			}
			if(!okToRemove){
				throw new IllegalStateException();
			}
			
			MyLinkedList.this.remove(current.pre);
			okToRemove = false;
			expectedModCount ++;
		}
		
	}
	public void add(int idx, AnyType x) {
		addBefore(getNode(idx),x);
	}
	/**
	 * 在当前节点之前加入一个一节点
	 * @param node 当前节点
	 * @param x	要加入的节点
	 */
	private void addBefore(Node<AnyType> node, AnyType x) {
		Node<AnyType> newNode = new Node<AnyType>(x, node.pre,node);
		newNode.pre.next = newNode;
		newNode.next.pre = newNode;
		size++;
		modCount++;
	}

	public Node<AnyType> getNode(int idx) {
		Node<AnyType> p;
		if(idx<0||idx>size)
			throw new IndexOutOfBoundsException();
		
		if(idx<size/2){
			p = begin.next;
			for(int i=0;i<idx;i++){
				p = p.next;
			}
		}else{
			p = end;
			for(int i=size;i>idx;i--){
				p = p.pre;
			}
		}
		return p;
	}
}

在以上的链表结构基础上，讨论链表的其他操作 1.链表的反转 　　提供一种方法：就地反转 　　begin-->1-->2-->3-->end 　　begin-->2-->1-->3-->end 　　begin-->3-->2-->1-->end 　　代码如下：　　

	/**
	 * 反转链表
	 * @return
	 */
	public MyLinkedList reverse(){
		Node<AnyType> cur = begin.next;
		if(cur==end)
			return this;
		Node<AnyType> curNext;
		
		while(cur.next!=end){
			curNext = cur.next;
			curNext.next.pre = cur;
			cur.next =curNext.next;
			curNext.next = begin.next;
			curNext.pre = begin;
			begin.next = curNext;
			curNext.next.pre = curNext;
		}
		return this;
	}
	
	public static void main(String[] args) {
		MyLinkedList<Integer> l = new MyLinkedList<>();
		for(int i=0;i<10;i++){
			l.add(i);
		}
		l = l.reverse();
		for(Integer i:l){
			System.out.print(i+"	");
		}
	}