这个类实现了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")); } }
相关资源：敏捷开发V1.0.pptx
