SimpleLinkList.java

package BaseType;

import java.util.Iterator;

public class SimpleLinkList<T> {

	class Node{
		public Node(T t){
			this.data = t;
		}
		public T data=null;
		public Node pre=null;
		public Node next=null;
	}

	private Node first = null;
	private Node last = null;
	private Node current = null;
	private int count = 0;

	public void add(T t){
		Node node = new Node(t);
		if(this.count==0){
			this.first = this.last = node;
		}else{
			node.pre = this.last;
			this.last.next = node;
			this.last = node;
		}
		this.count++;
	}
	
	public void addFirst(T t){
		Node node = new Node(t);
		if(this.count==0){
			this.add(t);
		}else{
			node.next = this.first;
			this.first.pre = node;
			this.first = node;
			this.count++;
		}
	}
	
	public void add(int index, T t) throws Exception  {
		if(index < 0 || index > this.count){
			throw new Exception("Invalid index");
		}
		if(index == 0){
			this.addFirst(t);
			return;
		}else if(index == this.count){
			this.add(t);
		}else{
			this.current = this.first;
			for(int i=0; i<index; ++i){
				this.current = this.current.next;
			}
			Node node = new Node(t);
			node.pre = this.current;
			node.next = this.current.next;
			if(this.current.next != null){
				this.current.next.pre = node;
			}
			this.current.next = node;
			this.count++;
		}
	}
	
	public T indexOf(int index) throws Exception{
		if(index < 0 || index >= this.count){
			throw new Exception("Invalid index");
		}
		this.current = this.first;
		for(int i=0; i<index; ++i){
			this.current = this.current.next;
		}
		return this.current.data;
	}
	
	public T remove(int index) throws Exception{
		if(index < 0 || index >= this.count){
			throw new Exception("Invalid index");
		}
		
		T t = null;
		if(this.count == 1 && index == 0){
			//only one node
			t = this.first.data;
			this.first = null;
			this.last = null;
		} else if(index == this.count-1){
			// remove last one
			t = this.last.data;
			this.last = this.last.pre;
			this.last.next = null;
		}else if(index == 0){
			// remove first one
			t = this.first.data;
			this.first = this.first.next;
		} else{
			// remove node between first and last
			this.current = this.first;
			for(int i=0; i<index; ++i){
				this.current = this.current.next;
			}
			t = this.current.data;
			this.current.next.pre = this.current.pre;
			this.current.pre.next = this.current.next;
		}
		this.count--;
		return t;
	}
	
	public int size(){
		return this.count;
	}
	
	public void clear(){
		this.first = null;
		this.last = null;
		this.count = 0;
	}
	
	// for test
	private static void print_list(SimpleLinkList mylist, String msg) throws Exception{
		System.out.println("======= " + msg + " =====" + mylist.size());
		for(int i=0; i<mylist.size(); ++i){
			System.out.println(mylist.indexOf(i));
		}
	}
	
	/**
	 * @param args
	 * @throws Exception 
	 */
	public static void main(String[] args) throws Exception {

		SimpleLinkList<String> mylist = new SimpleLinkList<String>();
		mylist.add(new String("1"));
		mylist.add(new String("2"));
		mylist.add(new String("3"));
		mylist.add(new String("4"));
		print_list(mylist, "初始值");
		// 头插
		mylist.add(0, new String("first"));    
		print_list(mylist, "头插");
		// 尾巴插
		mylist.add(mylist.size(), new String("last"));  
		print_list(mylist, "尾巴插");
		// 中间插
		mylist.add(3, new String("mid"));  
		print_list(mylist, "中间插");
		// 去头
		print_list(mylist, "去头:" + mylist.remove(0));
		// 去尾
		print_list(mylist, "去尾:" + mylist.remove(mylist.size()-1));
		// 去中间
		print_list(mylist, "去中间:" + mylist.remove(3));
		// clear
		mylist.clear(); print_list(mylist, "clear");
	}

}