package com.表栈和队列;

import java.util.Iterator;

/**

 * 实现LinkedList

 * 60页

 * @author zj

 *

 * @param <T>

 */

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

private int theSize; //集合大小

private int modCount = 0;//代表自从构造以来对链表所做的改变次数

private Node<T> beginMarker;//头节点

private Node<T> endMarker;//尾节点

/**

* 

* 连接到前一个node和下一个Node

* @author Administrator

*

* @param <T>

*/

private static class Node<T>{

public T data;

public Node<T> prev;//上一个链

public Node<T> next;//下一个链

public Node(T d ,Node<T> p,Node<T> n){

data = d ;

prev = p ;

next = n;

}

}

public MyLinkedList(){

clear();

}

private void clear() {

// TODO Auto-generated method stub

beginMarker = new Node<T>(null, null, null);

endMarker = new Node<T>(null, beginMarker, null);

beginMarker.next = endMarker;

theSize = 0;

modCount++;

}

private int size(){

return theSize;

}

public boolean isEmpty(){

return size() == 0;

}

public boolean add(T t){

add(size(),t);

return true;

}

private void add(int idx, T t) {

// TODO Auto-generated method stub

addBefore( getNode( idx ), t );

}

private T get(int idx){

return getNode(idx).data;

}

private 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) {

// TODO Auto-generated method stub

p.next.prev = p.prev;

p.prev.next = p.next;

theSize--;

modCount++;

return p.data;

}

/**

* 从下标0開始计算

* 通过获取一个新节点，然后改变指针完毕一个双链表的插入操作

* @param p

* @param t

*/

private void addBefore(Node<T> p, T t) {

// TODO Auto-generated method stub

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) {

// TODO Auto-generated method stub

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;

}

@Override

public Iterator<T> iterator() {

// TODO Auto-generated method stub

return new LinkedListIterator();

}

private class LinkedListIterator implements java.util.Iterator<T>{

private Node<T> current = beginMarker.next; //当前节点

private int expectedModCount = modCount;

private boolean okToRemove = false;

@Override

public boolean hasNext() {

// TODO Auto-generated method stub

return current!= endMarker;//当前节点是否等于最后节点

}

@Override

public T next() {

// TODO Auto-generated method stub

if(modCount != expectedModCount)

throw new java.util.ConcurrentModificationException();

if(!hasNext())

throw new java.util.NoSuchElementException();

T nextItem = current.data;

current = current.next;

okToRemove = true;

return nextItem;

}

@Override

public void remove() {

// TODO Auto-generated method stub

if(modCount != expectedModCount)

throw new java.util.ConcurrentModificationException();

if(!okToRemove)

throw new IllegalStateException();

MyLinkedList.this.remove(current.prev);

okToRemove = false;

expectedModCount++;

}

}

public static void main(String[] args) {

MyLinkedList<Integer> ml = new MyLinkedList<Integer>();

ml.add(1);

ml.add(2);

ml.add(3);

ml.add(1, 10);

for(Integer i :ml){

System.out.println(i);

}

}

}