(Java)单链表Java语言顺序结构实现(数据结构三)

墨蓝 2022-09-17 10:20 158阅读 0赞

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 LinearList<E> implements List<E> {
    
    	final static int INITIAL_CAPACITY=100;
    	
    	final static int INCREMENT_SIZE=10;
    	
    	transient Object [] item;
    	
    	transient int capacity=0;
    	
    	transient int length=0;
    	
    	LinearList(){
    			this.item=new Object[INITIAL_CAPACITY];
    			this.capacity=INITIAL_CAPACITY;
    	}
    	LinearList(List<E>list){
    		this.length=list.size();
    		this.capacity=this.length;
    		this.item=list.toArray();
    	}
    	
    	@Override
    	public int size() {
    		// TODO Auto-generated method stub
    		return this.length;
    	}
    
    	@Override
    	public boolean isEmpty() {
    		// TODO Auto-generated method stub
    		return this.length==0;
    	}
    
    	
    	@Override
    	public boolean contains(Object o) {
    		// TODO Auto-generated method stub
    		return indexOf(o)!=-1;
    	}
    
    	@Override
    	public Iterator<E> iterator() {
    		// TODO Auto-generated method stub
    		return new LinearIterator();
    	}
    	private class LinearIterator implements Iterator<E>{
    		private int nowIndex;
    		
    		public LinearIterator() {
    			// 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=(E) item[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
    			item[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];
    		for(int i=0;i<length;i++)
    			obj[i]=item[i];
    		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(item, length, a.getClass());
    	        System.arraycopy(item, 0, a, 0, length);
    	        if (a.length > length)
    	            a[length] = null;
    	        return a;
    	}
    
    	@Override
    	public boolean add(E e) {
    		// TODO Auto-generated method stub
    		addLast(e);
    		return true;
    	}
    
    	@Override
    	public boolean remove(Object o) {
    		// TODO Auto-generated method stub
    		while(contains(o)){
    			remove(contains(o));
    		}
    		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
    		this.item=new Object[INITIAL_CAPACITY];
    		this.capacity=INITIAL_CAPACITY;
    	}
    
    	@Override
    	public E get(int index) {
    		// TODO Auto-generated method stub
    		checkIndex(index);
    		return (E) item[index];
    	}
    
    	@Override
    	public E set(int index, E element) {
    		// TODO Auto-generated method stub
    		checkIndex(index);
    		item[index]=element;
    		return element;
    	}
    
    	@Override
    	public void add(int index, E element) {
    		// TODO Auto-generated method stub
    		checkIndex(index);
    		checkCapacity();
    	    System.arraycopy(item, index, item, index+1,length-index);
    		item[index]=element;
    		length++;
    	}
    	
    
    	@Override
    	public E remove(int index) {
    		// TODO Auto-generated method stub
    		checkRomoveIndex(index);
    		E e=(E) item[index];
    		System.arraycopy(item, index+1, item, index,length-index-1);
    		length--;
    		return e;
    	}
    
    	@Override
    	public int indexOf(Object o) {
    		// TODO Auto-generated method stub
    		E e=(E)o;
    		int index=-1;
    		if(o!=null){
    			for(int i=0;i<length;i++){
    				if(item[i].equals(e))
    					index=i;
    			}
    				
    		}else{
    			for(int i=0;i<length;i++){
    				if(item[i]==null)
    					index=i;
    			}
    		}
    		return index;
    	}
    
    	@Override
    	public int lastIndexOf(Object o) {
    		// TODO Auto-generated method stub
    		E e=(E)o;
    		int index=-1;
    		if(o!=null){
    			for(int i=length-1;i>0;--i){
    				if(item[i].equals(e))
    					index=i;
    			}
    				
    		}else{
    			for(int i=length-1;i>0;--i){
    				if(item[i]==null)
    					index=i;
    			}
    		}
    		return index;
    	}
    
    	@Override
    	public List<E> subList(int fromIndex, int toIndex) {
    		// TODO Auto-generated method stub
    		checkRomoveIndex(fromIndex);
    		checkRomoveIndex(toIndex);
    		List<E> ll=new LinearList<E>();
    		for(int i=fromIndex;i<=toIndex;i++)
    			ll.add(get(i));
    		return ll;
    	}
    	
    	private void addLast(E e){
    		checkCapacity();
    		item[length]=e;
    		length++;
    	}
    	private void checkCapacity(){
    		if(length>=capacity){
    			Object []obj=new Object[capacity+INCREMENT_SIZE];
    			obj=Arrays.copyOfRange(item,0, length-1);
    			item=obj;
    			capacity+=INCREMENT_SIZE;
    		}
    	}
    	private void checkRomoveIndex(int index){
    		if(index<0||index>=length){
    			throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    		}
    	}
    	private void checkIndex(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 LinearList<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