(Java)单链表Java语言链式结构实现(数据结构四)

1.迭代器接口实现

package com.zhaochao;

public interface Iterator<E> {
	 boolean  hasNext();
	 E        next();
	 boolean  delete();
	 boolean  modify(E e);
	 int      index();
}

2.List接口实现

package com.zhaochao;





public interface List<E> {
	
    //链表大小
	int size();
	
	//链表是否为空	
	boolean isEmpty();
	
	boolean contains(Object o);

    Iterator<E> iterator();

    Object[] toArray();

    <T> T[] toArray(T[] a);

    boolean add(E e);

    boolean remove(Object o);

    boolean containsAll(List<?> c);
 
    boolean addAll(List<? extends E> c);

    boolean addAll(int index, List<? extends E> c);

    boolean removeAll(List<?> c);

    boolean retainAll(List<?> c);

    void clear();

    boolean equals(Object o);

    int hashCode();

    E get(int index);

    E set(int index, E element);

    void add(int index, E element) ;

    E remove(int index);

    int indexOf(E o);

    int lastIndexOf(E o);

    List<E> subList(int fromIndex, int toIndex);

}

3.异常类实现

package com.zhaochao;

public class IndexOutOfBoundsException extends RuntimeException {
	 private static final long serialVersionUID = 234122996006267687L;

	    /**
	     * Constructs an <code>IndexOutOfBoundsException</code> with no
	     * detail message.
	     */
	    public IndexOutOfBoundsException() {
	        super();
	    }

	    /**
	     * Constructs an <code>IndexOutOfBoundsException</code> with the
	     * specified detail message.
	     *
	     * @param   s   the detail message.
	     */
	    public IndexOutOfBoundsException(String s) {
	        super(s);
	    }
}

4.链式结构单链表实现

package com.zhaochao;

import java.util.Arrays;

public class LinkList<E> implements List<E> {

	transient int length=0;
	transient Node<E> head;
	transient Node<E> last;
	
	public LinkList(){
		
	}
	public LinkList(List<E> list){
		Iterator<E> it=list.iterator();
		while(it.hasNext()){
			add(it.next());
		}
	}
	
	private static class Node<E>{
		E data;
		Node<E> next;
		Node(E e){
			this.data=e;
			this.next=null;
		}
		Node(Node<E> pre,E e){
			this.data=e;
			pre.next=next;
		}
	}
	
	
	@Override
	public int size() {
		// TODO Auto-generated method stub
		return length;
	}

	@Override
	public boolean isEmpty() {
		// TODO Auto-generated method stub
		return length==0;
	}

	@Override
	public boolean contains(Object o) {
		// TODO Auto-generated method stub
		E e=(E)o;
		return indexOf(e)!=-1;
	}

	@Override
	public Iterator<E> iterator() {
		// TODO Auto-generated method stub
		return new LinkIterator();
	}
	private class LinkIterator implements Iterator<E>{
		private int nowIndex;
		
		public LinkIterator() {
			// TODO Auto-generated constructor stub
			this.nowIndex=0;
		}
		@Override
		public boolean hasNext() {
			// TODO Auto-generated method stub
			return this.nowIndex<length;
		}

		@Override
		public E next() {
			// TODO Auto-generated method stub
			E e=get(nowIndex);
			nowIndex++;
			return e;
		}

		@Override
		public boolean delete() {
			// TODO Auto-generated method stub
			remove(nowIndex);
			return true;
		}

		@Override
		public boolean modify(E e) {
			// TODO Auto-generated method stub
			set(nowIndex, e);
			return true;
		}
		@Override
		public int index() {
			// TODO Auto-generated method stub
			return nowIndex;
		}
	}
	
	

	@Override
	public Object[] toArray() {
		// TODO Auto-generated method stub
		Object[] obj=new Object[length-1];
		Iterator it=this.iterator();
		int i=0;
		while(it.hasNext()){
			obj[i++]=it.next();
		}
		return obj;
	}

	@Override
	public <T> T[] toArray(T[] a) {
		// TODO Auto-generated method stub
	     if (a.length < length)
	            // Make a new array of a's runtime type, but my contents:
	            return (T[]) Arrays.copyOf(a, length, a.getClass());
	        a=(T[])toArray();
	        if (a.length > length)
	            a[length] = null;
	        return a;
	}

	@Override
	public boolean add(E e) {
		// TODO Auto-generated method stub
		addLast(e);
		return false;
	}

	@Override
	public boolean remove(Object o) {
		// TODO Auto-generated method stub
		while(contains(o)){
			E e=(E)o;
			remove(indexOf(e));
		}
		
		return true;
	}

	@Override
	public boolean containsAll(List<?> c) {
		// TODO Auto-generated method stub
		boolean flag=true;
		Iterator it=c.iterator();
		while(it.hasNext()){
			flag=flag&&contains(it.next());
		}
		return flag;
	}

	@Override
	public boolean addAll(List<? extends E> c) {
		// TODO Auto-generated method stub
		Iterator it=c.iterator();
		while(it.hasNext()){
			add((E)it.next());
		}
		return true;
	}

	@Override
	public boolean addAll(int index, List<? extends E> c)  {
		// TODO Auto-generated method stub
		Iterator it=c.iterator();
		while(it.hasNext()){
			add(index++,(E)it.next());
		}
		return true;
	}

	@Override
	public boolean removeAll(List<?> c) {
		// TODO Auto-generated method stub
		Iterator it=c.iterator();
		while(it.hasNext()){
			if(contains(it.next()))
				remove(it.next());
		}
		return true;
	}

	@Override
	public boolean retainAll(List<?> c) {
		// TODO Auto-generated method stub
		Iterator it=this.iterator();
		while(it.hasNext()){
			E e=(E) it.next();
			if(!c.contains(e))
				remove(e);
		}
		return true;
	}

	@Override
	public void clear() {
		// TODO Auto-generated method stub
		head=null;
		last=null;
		length=0;
	}

	@Override
	public E get(int index) {
		// TODO Auto-generated method stub
		checkRomoveIndex(index);
		Node<E> node=head;
		for(int i=0;i<index;i++){
			node=node.next;
		}
		return node.data;
	}

	@Override
	public E set(int index, E element) {
		// TODO Auto-generated method stub
		Node<E> node=getNode(index);
		node.data=element;
		return element;
	}

	@Override
	public void add(int index, E element)  {
		// TODO Auto-generated method stub
		checkAddIndex(index);
		if(index==0){
			Node<E> h=head;
			Node<E> node=new Node<E>(element);
			head=node;
			head.next=h;
			
		}else{
			Node<E> node=getNode(index-1);
			Node<E> newNode=new Node<E>(element);
			newNode.next=node.next;
			node.next=newNode;
		}
		length++;
	}

	@Override
	public E remove(int index) {
		// TODO Auto-generated method stub
		checkRomoveIndex(index);
		E e;
		if(index==0){
			 e=head.data;
			head=head.next;
		}else{
			Node<E> node=getNode(index-1);
			e=node.next.data;
			node.next=node.next.next;
		}
		length--;
		return e;
	}

	@Override
	public int indexOf(E o) {
		// TODO Auto-generated method stub
		
		for(int i=0;i<length;i++){
			if(get(i).equals(o))
				return i;
		}
		return -1;
	}

	@Override
	public int lastIndexOf(E o) {
		// TODO Auto-generated method stub
		List ll=new LinkList();
		for(int i=0;i<length;i++){
			if(get(i).equals(o))
				ll.add(i);
		}
		return (int) ll.get(ll.size()-1);
	}

	@Override
	public List<E> subList(int fromIndex, int toIndex) {
		// TODO Auto-generated method stub
		checkRomoveIndex(fromIndex);
		checkRomoveIndex(toIndex);
		List<E> ll=new LinkList<E>();
		for(int i=fromIndex;i<=toIndex;i++)
			ll.add(get(i));
		return ll;
	}
	
	private void addLast(E e){
		if(head==null){
			Node<E> node=new Node<E>(e);
			head=node;
			last=node;
		}else{
			Node<E> l=last;
			Node<E> node=new Node<E>(l,e);
			last=node;
			l.next=last;
		}
		length++;
	}
	private Node<E> getNode(int index){
		checkRomoveIndex(index);
		Node<E> node=head;
		for(int i=0;i<index;i++){
			node=node.next;
		}
		return node;
	}
		
	private void checkRomoveIndex(int index){
		if(index<0||index>=length){
			throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
		}
	}
	private void checkAddIndex(int index)  {
		if(index<0||index>length){
			throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
		}
	}
	private String outOfBoundsMsg(int index){
		return "index:"+index+" length:"+length;
	}
	
}

5.测试

package com.zhaochao;


public class main {


	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		List<Test> ls=new LinkList<Test>();
		Test t=new Test();
		for(int i=0;i<10;i++)
			ls.add(t);
		Iterator it=ls.iterator();
		while(it.hasNext()){
			System.out.println(it.next());
		}
	
	}

}


class Test{
	public static int a=0;
	public String toString(){
		return String.valueOf(a++);
	}
}

6.测试结果

0
1
2
3
4
5
6
7
8
9