(Java)Java双向链表实现(数据结构七)

朱雀 2022-09-17 10:23 153阅读 0赞

1.迭代器接口实现

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

2.异常类实现

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);
    	    }
    }

3.双向链表实现

package com.zhaochao;
    
    import java.util.LinkedList;
    
    public class DLinkList<E> {
    	
    	transient int length;
    	Node<E> head;
    	Node<E> tail;
    	
    	public DLinkList(){
    		
    	}
    	public Iterator<E> iterator(){
    		return new DLinkIterator();
    	}
    	public int size(){
    		return length;
    	}
    	private class DLinkIterator implements Iterator  {
    		
    		transient int nowIndex=0;
    		public DLinkIterator(){
    			
    		}
    		@Override
    		public boolean hasNext() {
    			// TODO Auto-generated method stub
    			return nowIndex<length;
    		}
    
    		@Override
    		public E next() {
    			// TODO Auto-generated method stub
    			Node<E> node=getNode(nowIndex);
    			nowIndex++;
    			return node.date;
    		}
    
    		@Override
    		public boolean delete() {
    			// TODO Auto-generated method stub
    			deleteIndex(nowIndex);
    			return false;
    		}
    
    		@Override
    		public boolean modify(Object e) {
    			// TODO Auto-generated method stub
    			Node<E> node=getNode(nowIndex);
    			node.date=(E) e;
    			return true;
    		}
    
    		@Override
    		public int index() {
    			// TODO Auto-generated method stub
    			return nowIndex;
    		}
    		
    		
    	}
    	public void add(E e){
    		addLast(e);
    	}
    	
    	public void add(int index, E e){
    		checkIndex(index);
    		if(index==0){
    			addFrist(e);
    		}else if(index==length-1){
    			addLast(e);
    		}else{
    			Node<E> tempPre=getNode(index-1);
    			Node<E> tempNext=getNode(index);
    			Node<E> node=new Node(tempPre,e,tempNext);
    			tempPre.next=node;
    			tempNext.pre=node;
    			length++;
    		}
    		
    	}
    	
    	
    	public void deleteIndex(int index){
    		checkIndex(index);
    		if(index==0){
    			deleteFirst();
    		}else if(index==length-1){
    			deleteLast();
    		}else{
    			Node<E> tempPre=getNode(index-1);
    			Node<E> tempNext=getNode(index+1);
    			tempPre.next=tempNext;
    			tempNext.pre=tempPre;
    			length--;
    		}
    	}
    	private boolean deleteFirst(){
    		head=head.next;
    		length--;
    		return true;
    	}
    	private boolean deleteLast(){
    		tail=tail.pre;
    		length--;
    		return true;
    	}
    	
    	
    	private Node<E> getNode(int index){
    		checkIndex(index);
    		Node<E> node;
    		if(index<length>>1){
    			node=head;
    			for(int i=0;i<index;i++)
    				node=node.next;
    		}else{
    			node=tail;
    			for(int i=length-1;i>index;i--)
    				node=node.pre;
    		}
    		return node;
    	}
    	
    	private void checkIndex(int index){
    		if(index<0 ||index>=length)
    			throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    	}
    	
    	private String outOfBoundsMsg(int index){
    		return "index:"+index+" length:"+size();
    	}
    	private boolean addFrist(E e){
    		Node<E> h=head;
    		Node<E> node=new Node(null,e,h);
    		head=node;
    		if(h==null){
    			tail=node;
    		}else{
    			h.pre=node;
    		}
    		length++;
    		return true;
    	}
    	
    	private boolean addLast(E e){
    		Node<E> l=tail;
    		Node<E> node=new Node(l,e,null);
    		tail=node;
    		if(l==null){
    			head=node;
    		}else{
    			l.next=node;
    		}
    		length++;
    		return true;
    	}
    	
    	private static class Node<E>{
    		E date;
    		Node<E> pre;
    		Node<E> next;
    		Node(E e){
    			this.date=e;
    		}
    		Node(Node<E> pre,E e,Node<E> next){
    			this.pre=pre;
    			this.date=e;
    			this.next=next;
    		}
    	}
    	
    	
    }

4.测试

package com.zhaochao;
    
    
    public class main {
    
    
    	public static void main(String[] args) throws Exception {
    		// TODO Auto-generated method stub
    		
    		DLinkList<Test> dl=new DLinkList<Test>();
    		Test t=new Test();
    		for(int i=0;i<10;i++)
    			dl.add(t);
    		
    		Iterator it=dl.iterator();
    		while(it.hasNext())
    			System.out.println(it.next());
    	}
    
    }
    
    
    class Test{
    	public static int a=0;
    	public String toString(){
    		return String.valueOf(a++);
    	}
    }

5.测试结果

0
    1
    2
    3
    4
    5
    6
    7
    8
    9