我的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"));}}

?

?

?

?