链表与迭代器

女爷i 2022-07-18 06:18 306阅读 0赞

## 链表的使用中find操作是常见的，很多时候也需要对链表进行遍历。如果使用迭代器遍历每一个对象，这样就会使数据结构与遍历对象（迭代器）区分开，java中的Iterator作为轻量级对象，创建代价比较小。至少在使用迭代器可以有一下几点好处： ##

### 1 迭代器可以提供统一的迭代方式，也就是说对于链表、队列、数组、叉树都可以使用迭代器来时实现迭代。 ###

### 2 迭代器可以在客户端透明的情况下提供各种不同的迭代方式，迭代器可以实现对数据结构“一个不漏”的迭代。 ###

### 这里以链表为例，使用迭代器对链表进行迭代操作。首先需要创建一个链表，之后需要创建一个和链表相关联的迭代器对象。 ###

### 首先创建一个链表Node。 ###

class Link6
    {
       public long dData;             
       public Link6 next;              
       public Link6(long dd)          
       { 
           dData = dd; 
       }
    
       public void displayLink()      
       { 
           System.out.print(dData + " "); 
       }
    }

### 创建链表包括一些数据添加等操作。 ###

class LinkListA
    {
    private Link6 first;            
    
    public LinkListA()             
       { 
        first = null; 
        }
    //获取第一个Node
    public Link6 getFirst()       
       { 
        return first; 
        }
    //设置第一个Node
    public void setFirst(Link6 f)   
       { 
        first = f; 
        }
    //判断链表是否为null
    public boolean isEmpty()       
       { return first==null; }
    //返回当前迭代器Node
    public ListIterator getIterator() 
       {
       return new ListIterator(this);  
       }                               
    //显示链表节点
    public void displayList()
       {
       Link6 current = first;      
       while(current != null)    
          {
          current.displayLink();   
          current = current.next;  
          }
       System.out.println("");
       }
    }

### 以上与常见的链表操作大同小异。创建好了链表类之后就可以创建基于链表的迭代器类了。 ###

//创建迭代器类
    class ListIterator
    {
    private Link6 current;          
    private Link6 previous;
    //当前迭代得到的Node
    private LinkListA ourList;      
    //--------------------------------------------------------------
    public ListIterator(LinkListA list) 
       {
       ourList = list;
       //创建迭代器就开始从first处开始迭代
       reset();
       }
    //--------------------------------------------------------------
    public void reset()            
       {
       current = ourList.getFirst();//从first处开始迭代
       previous = null;
       }
    //--------------------------------------------------------------
    //判断是否已经迭代了最后一个Node
    public boolean atEnd()         
       { return (current.next==null); }
    //--------------------------------------------------------------
    //迭代器指向下一个结点
    public void nextLink()        
       {
       previous = current;
       current = current.next;
       }
    //--------------------------------------------------------------
    //获取当前迭代到的Node
    public Link6 getCurrent()       
       { return current; }
    //--------------------------------------------------------------
    //在一个Node点后面再添加一个结点
    public void insertAfter(long dd)     
       {                                 
       Link6 newLink = new Link6(dd);
    
       if( ourList.isEmpty() )     
          {
           //判断是都为空，如链表为空则从链表头部开始插入数据项
          ourList.setFirst(newLink);
          current = newLink;
          }
       else                        
          {
          newLink.next = current.next;
          current.next = newLink;
          nextLink();              
          }
       }
    //在一个结点插入一个结点
    public void insertBefore(long dd)   
       {                                
       Link6 newLink = new Link6(dd);
    
       if(previous == null)        
          {                        
          newLink.next = ourList.getFirst();
          ourList.setFirst(newLink);
          reset();
          }
       else                        
          {
          newLink.next = previous.next;
          previous.next = newLink;
          current = newLink;
          }
       }
    //删除当前节点
    public long deleteCurrent()    
       {
       long value = current.dData;
       if(previous == null)        
          {
          ourList.setFirst(current.next);
          reset();
          }
       else                        
          {
          previous.next = current.next;
          if( atEnd() )
             reset();
          else
             current = current.next;
          }
       return value;
       }
    }

### 测试类。 ###

class IteratorListApp
    {
    public static void main(String[] args) throws IOException
       {
       LinkListA theList = new LinkListA();           
       ListIterator iter1 = theList.getIterator();  
       long value;
    
       iter1.insertAfter(20);             
       iter1.insertAfter(40);
       iter1.insertAfter(80);
       iter1.insertBefore(60);
    
       while(true)
          {
          System.out.print("Enter first letter of show, reset, ");
          System.out.print("next, get, before, after, delete: ");
          System.out.flush();
          int choice = getChar();        
          switch(choice)
             {
             case 's':                  
                if( !theList.isEmpty() )
                   theList.displayList();
                else
                   System.out.println("List is empty");
                break;
             case 'r':                    
                iter1.reset();
                break;
             case 'n':                   
                if( !theList.isEmpty() && !iter1.atEnd() )
                   iter1.nextLink();
                else
                   System.out.println("Can't go to next link");
                break;
             case 'g':                    
                if( !theList.isEmpty() )
                   {
                   value = iter1.getCurrent().dData;
                   System.out.println("Returned " + value);
                   }
                else
                   System.out.println("List is empty");
                break;
             case 'b':                    
                System.out.print("Enter value to insert: ");
                System.out.flush();
                value = getInt();
                iter1.insertBefore(value);
                break;
             case 'a':                    
                System.out.print("Enter value to insert: ");
                System.out.flush();
                value = getInt();
                iter1.insertAfter(value);
                break;
             case 'd':                    
                if( !theList.isEmpty() )
                   {
                   value = iter1.deleteCurrent();
                   System.out.println("Deleted " + value);
                   }
                else
                   System.out.println("Can't delete");
                break;
             default:
                System.out.println("Invalid entry");
             }  
          } 
       }  
    //--------------------------------------------------------------
    public static String getString() throws IOException//从键盘输入字符串
       {
       InputStreamReader isr = new InputStreamReader(System.in);
       BufferedReader br = new BufferedReader(isr);
       String s = br.readLine();
       return s;
       }
    //-------------------------------------------------------------
    public static char getChar() throws IOException
       {
       String s = getString();
       return s.charAt(0);
       }
    
    //-------------------------------------------------------------
    public static int getInt() throws IOException
       {
       String s = getString();
       return Integer.parseInt(s);
       }
    //-------------------------------------------------------------
    }

### 以下是一种测试结果： ###

Enter first letter of show, reset, next, get, before, after, delete: s
    20 40 60 80 
    Enter first letter of show, reset, next, get, before, after, delete: r
    Enter first letter of show, reset, next, get, before, after, delete: n
    Enter first letter of show, reset, next, get, before, after, delete: n
    Enter first letter of show, reset, next, get, before, after, delete: n
    Enter first letter of show, reset, next, get, before, after, delete: n
    Can't go to next link
    Enter first letter of show, reset, next, get, before, after, delete: g
    Returned 80
    Enter first letter of show, reset, next, get, before, after, delete: b
    Enter value to insert: 333
    Enter first letter of show, reset, next, get, before, after, delete: s
    20 40 60 333 80 
    Enter first letter of show, reset, next, get, before, after, delete: d
    Deleted 333
    Enter first letter of show, reset, next, get, before, after, delete: s
    20 40 60 80 
    Enter first letter of show, reset, next, get, before, after, delete:

### 代码参考《java数据结构与算法》。 ###

### 以上是通过基于链表的迭代器对链表进行相关操作。其实java提供了数据结构迭代器统一接口，不仅仅针对链表，也包括数组等数据结构。在java中有Iterable接口，实现该接口可以产生Iterator对象，除了数据结构，foreach循环也是在迭代器的基础上实现的，foreach语法后面可以有两种类型：一是数组，另外一个是实现了Iterator接口的类。 ###