Java单链表顺序和链式实现(数据结构五)

- 日理万妓 2022-09-17 10:21 137阅读 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;
    
    public abstract class abstrctList<E> implements List<E> {
    
    
    	@Override
    	public boolean isEmpty() {
    		// TODO Auto-generated method stub
    		return size()==0;
    	}
    
    	
    	@Override
    	public boolean contains(Object o) {
    		// TODO Auto-generated method stub
    		E e=(E)o;
    		return indexOf(e)!=-1;
    	}
    	
    	@Override
    	public int indexOf(E o) {
    		// TODO Auto-generated method stub
    		
    		for(int i=0;i<size();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<size();i++){
    			if(get(i).equals(o))
    				ll.add(i);
    		}
    		return (int) ll.get(ll.size()-1);
    	}
    
    
    	
    	
    	@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;
    	}
    	
    	public void checkRomoveIndex(int index){
    		if(index<0||index>=size()){
    			throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    		}
    	}
    	public void checkIndex(int index)  {
    		if(index<0||index>size()){
    			throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    		}
    	}
    	public String outOfBoundsMsg(int index){
    		return "index:"+index+" length:"+size();
    	}
    
    
    }

5.单链表顺序实现

package com.zhaochao;
    
    import java.util.Arrays;
    
    
    public class LinearList<E> extends abstrctList<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 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 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 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;
    		}
    	}
    
    
    }

6.单链表链式实现

package com.zhaochao;
    
    import java.util.Arrays;
    
    public class LinkList<E>extends abstrctList<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 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 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
    		checkIndex(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 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;
    	}
    		
    
    	
    }

7.测试

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>();
    		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());
    		}
    		List<Test> ll=ls.subList(2, 5);
    		it=ll.iterator();
    		while(it.hasNext()){
    			System.out.println(it.next());
    		}
    	
    	}
    
    }
    
    
    class Test{
    	public static int a=0;
    	public String toString(){
    		return String.valueOf(a++);
    	}
    }

8.测试结果

0
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13