我的LinkedList的实现类

这个类实现了java List接口，底层完全由链表来实现。（非常好的单链表的例子）

package datasturct;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
/**
 * 我自己实现List 接口的MyLinkList类
 * @author newapps
 *  2009-12-9
 */
public class MyLinkList<T>{
	/**
	 * 节点内部类
	 * @author newapps
	 * @param <T> 表示泛型
	 */
	private  class Node<T>{
		T value;
		Node<T> next;
		
		Node(T value){
			this.value=value;
			this.next=null;
		}
	}
	/**定义链表的头结点*/
	private Node<T> head=null;
	/**
	 * 链表中节点数
	 */
	public int size() {
		Node<T> p;
		int size=0;
		for(p=head;p!=null;p=p.next){
			size++;
		}
		return size;
	}
	/**
	 * 判断该链表的节点数是否为零
	 */
	public boolean isEmpty() {
		if(size()==0){
			return true;
		}
		return false;
	}
	/**
	 * 查找链表中是否含有某个指定节点值的节点
	 * @param o 节点值
	 * @return 是否含有
	 */
	public boolean contains(T o) {
		if(isEmpty()){
			return false;
		}
		Node<T> p;
		for(p=head;p!=null;p=p.next){
			if(p.value.equals(o)){
				return true;
			}
		}
		return false;
	}
	/**
	 * 迭代器方法
	 * @return
	 */
	public Iterator iterator() {
		return new Itor();
	}
	/**
	 * 迭代器的实现类
	 * @author newapps
	 * 2009-12-9
	 */
	private class Itor implements Iterator{
		/**位置*/
		private int index=0;
	//	private int cursor=0;
		public boolean hasNext() {
			
			if(index<size()){
				return true;
			}
			return false;
		}

		public T next(){
			T o = get(index++);
			return o;
		}

		public void remove() {
			MyLinkList.this.remove(size()-1);
		}
		
	}
	/**
	 * 将集合中所有元素作为一个Object[]数组返回
	 * @return
	 */
	public Object[] toArray() {
		if(isEmpty()){
			return null;
		}
		int length=size(),i=0;
		Object[] a=new Object[length];
		Node<T> p;
		for(p=head;p!=null;p=p.next){
			a[i]=p.value;
			i++;
		}
		return a;
	}

	/**
	 * 由于list接口是有序
	 * 所以链表中添加节点数
	 * 应当在最后一个节点位置后添加
	 * @param o 节点值
	 * @return 添加是否成功
	 */
	public void add(T o){
		if(isEmpty()){
			head=new Node<T>(o);	
		}else{
			Node<T> p=head;
			Node<T> node=new Node<T>(o);
			while(p.next!=null){
				p=p.next;
			}
			p.next=node;
			node.next=null;
		}
	}
	/**
	 * 要删除链表中某个节点的值
	 * 首先要找到该节点
	 * 最后才删除
	 * @param o
	 * @return
	 */
	public boolean remove(T o){
		Node<T> p=head,p1=null;
		boolean have=false;
		if(isEmpty()){
			return false;
		}
		while(p!=null){
			if(p.value.equals(o)){
				if(p1==null){
					head=head.next;
				}else{
					p1.next=p.next;
				}
				have=true;
			}
			p1=p;
			p=p.next;
		}
		return have;
	}
	/**
	 * 查找集合中所有元素在该链表中是否也存在
	 * @param c
	 * @return
	 */
	public boolean containsAll(Collection c) {
		if(isEmpty()){
			return false;
		}
		if(c.size()==0){
			return false;
		}
		if(c==null||c.size()>size()){
			return false;
		}
		Iterator it=c.iterator();
		while(it.hasNext()){
			T o=(T)it.next();
			if(!contains(o)){
				return false;
			}
		}
		return true;
	}
	/**
	 * 将集合所有的元素添加到链表中
	 * @param c
	 * @return
	 */
	public boolean addAll(Collection c){
		if(c==null||c.size()==0){
			return false;
		}
		Iterator it=c.iterator();
		while(it.hasNext()){
			T o=(T)it.next();
			add(o);
		}
		return true;
	}
	/**
	 * 从指定的下标位置将集合中所有的元素添加到链表中
	 * @param index
	 * @param c
	 * @return
	 */
	public boolean addAll(int index, Collection c) {
		if(c==null||c.size()==0){
			return false;
		}
		if(isEmpty()){
			addAll(c);
			return true;
		}
		if(index<-1){
			return true;
		}else if(index>=size()){
			addAll(c);
		}else{
			int i=index;
			Iterator it=c.iterator();
			while(it.hasNext()){
				T o=(T)it.next();
				add(i,o);
				i++;
			}
		}
		// 将集合中
		return false;
	}
	/**
	 * 在链表中删除包含集合中的所有元素
	 * @param c
	 * @return
	 */
	public boolean removeAll(Collection c){
		if(c==null||c.size()==0){
			return false;
		}
		if(isEmpty()){
			return false;
		}
		Node<T> p;
		Iterator it=c.iterator();
		while(it.hasNext()){
			T o=(T)it.next();
			remove(o);
		}
		
		return true;
	}
	/**
	 * 在链表中仅保留集合中的元素其余的全部删除
	 * @param c
	 * @return
	 */
	public boolean retainAll(Collection c) {
		if(isEmpty()){
			return false;
		}
		if(c==null||c.size()==0){
			return false;
		}
		
		Node<T> p;
	  for(p=head;p!=null;p=p.next){
		T m=p.value;
		boolean have=false;
		Iterator it=c.iterator();
		 while(it.hasNext()){
			T o=(T)it.next(); 
			if(m.equals(o)){
				have=true;
			}
		   }
		 if(!have){
			 this.remove(m);
		 }
		}
		return true;
	}

	public void clear() {
		head=null;
	}
	/**
	 * 依据指定的下标，找出链表中的元素的值
	 * @param index
	 * @return
	 */
	public T get(int index) {
		int i=-1;
		if(isEmpty()){
			return null;
		}
		if(index<0||index>size()){
			return null;
		}
		Node<T> p=head;
		while(p!=null){
			i++;
			if(i==index){
				return p.value;
			}
			p=p.next;
		}
		return null;
	}
	/**
	 *  替换链表指定位置的元素
	 *  并返回替换前的元素
	 * @param index
	 * @param element
	 * @return
	 */
	public T set(int index, T element) {
		int i=-1;
		if(isEmpty()){
		add(element);
			return null;
		}
		if(index<0||index>size()){
			return null;
		}
		Node<T> p=head;
		T o=null;
		while(p!=null){
			i++;
			if(i==index){
				o=p.value;
				p.value=element;
				return o;
			}
			p=p.next;
		}
		return null;
	}
	/**
	 * 在链表的指定位置添加一个元素
	 * @param index
	 * @param element
	 */
	public void add(int index, T element) {
		int i=-1;
		if(isEmpty()){
			this.add(element);
			return;
		}
		if(index<0||index>size()){
			return;
		}
		Node<T> p=head,p1=null;
		while(p!=null){
			i++;
			if(i==index){
				Node<T> newNode=new Node<T>(element);
				if(p1==null){
					newNode.next=head;
					head=newNode;
				}else{
					p1.next=newNode;
					newNode.next=p;
				}
			}
			p1=p;
			p=p.next;
		}
	}
	/**
	 * 在链表中删除指定位置的元素
	 * @param index
	 * @return
	 */
	public T remove(int index) {
		if(isEmpty()){
			return null;
		}
		if(index<0||index>size()){
			return null;
		}
		Node<T> p=head,p1=null;
		int i=-1;
		while(p!=null){
			i++;
			if(i==index){
				if(p1==null){
					head=head.next;
				}else{
					p1.next=p.next;
				}
				return p.value;
			}
			p1=p;
			p=p.next;
		}
		return null;
	}
	/**
	 * 在链表中返回包含指定元素的下标，如果没有找到则返回-1;
	 * @param o
	 * @return
	 */
	public int indexOf(T o) {
		int i=-1;
		if(isEmpty()){
			return -1;
		}
		Node<T> p=head;
		while(p!=null){
			i++;
			if(p.value.equals(o)){
				return i;
			}
			p=p.next;
		}
		return -1;
	}
	/**
	 * 在链表中找出指定元素最后一次出现的下标
	 * 如果没有找到则返回-1;
	 * @param o
	 * @return
	 */
	public int lastIndexOf(T o) {
		if(isEmpty()){
			return -1;
		}
		Node<T> p=head;
		int i=-1,index=-1;
		while(p!=null){
			i++;
			if(p.value.equals(o)){
				index=i;
			}
			p=p.next;
		}
		return index;
	}
	/**
	 * 链表的打印方法
	 *
	 */
	public void printLinkList(){
		Node<T> p;
		for(p=head;p!=null;p=p.next){
			System.out.print(p.value+"--->");
		}
		System.out.println();
	}
	public static void main(String args[]){
		MyLinkList<String> list=new MyLinkList<String>();
		//System.out.println(list.isEmpty());
		int [] s=new int[5];
		list.add("5");
		list.add("6");
		list.add("7");
		list.add("8");
		Collection c=new ArrayList();
		c.add("9");
		c.add("10");
		c.add("11");
		c.add("8");
		//list.remove("8");
		//list.add(0,"50");
		//list.remove(2);
		//System.out.println(list.set(2,"100"));
		//System.out.println(list.get(2));
		//list.addAll(c);
		//list.printLinkList();
		//list.retainAll(c);
		list.addAll(2,c);
		list.printLinkList();
		Iterator it=list.iterator();
		while(it.hasNext()){
			System.out.print(it.next()+"---");
		}
//		it.remove();
//		it.remove();
//		it.remove();
//		it.remove();
		list.clear();
		list.printLinkList();
		//System.out.println(list.indexOf("9"));
		//System.out.println(list.lastIndexOf("8"));
		//System.out.println(list.contains("10"));
	}
}