JAVA链表中迭代器的实现

　　注：本文代码出自《java数据结构和算法》一书。

　　PS：本文中类的名字定义存在问题，Link9应改为Link、LinkList9应该为LinkList。由于在同包下存在该名称，所以在后面接了数字。

迭代器：

　　加入我们需要遍历一个链表，并在某些特定的链接点上执行一些操作。比如，你要搜索链表存储的员工表，所有员工工资为最低的员工，并为其加薪1000元。在数组中，由于数组下标可以跟踪所在位置，这种操作就很容易，然而在链表中，没有固定的下标，我们如何实现？且看下文：

迭代器类：

　　迭代器类包含对数据结构中数据项的引用，用来遍历这些结构的对象，定义如下代码中的class ListIterator。current字段包含迭代器当前指向的链接点的一个引用。为了使用这样的迭代器用户可以创建一个链表，然后创建一个和链表相关联的迭代器对象。创建迭代器对象后，就可以通过它存取它指向的链接点，或者递增它以指向下一个链接点。

迭代器的方法：

　　reset()------------------>把迭代器设在表头

　　nextLink()--------------->把迭代器移动到下一个链接点

　　getCurrent()------------->返回迭代器所指的链接点

　　atEnd()------------------>如果迭代器达到表尾，返回true

　　insertAfter()------------->在迭代器后面插入一个新的链接点

　　insertBefore()----------->在迭代器前面插入一个新的链接点

　　deleteCurrent()---------->删除迭代器所指的链接点

不多说，直接上代码：　　

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import test_4_19.system;

/**
 * java链表中迭代器的实现
 * 2017年5月2号17:25
 * @author zcj
 *
 */

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

class LinkList9
{
    private Link9 first;
    
    public LinkList9()
    {
        first = null;
    }
    
    public Link9 getFirst()//获取链表的first
    {
        return first;
    }
    public void setFirst(Link9 f)//由于在迭代器里面first可能会改变，所以需要LinkList中提供first改变的方法
    {
        first = f;
    }
    public boolean isEmpty()
    {
        return first==null;
    }
    public ListIterator getIterator()
    {
        return new ListIterator(this);
    }
    
    public void dispalyList()
    {
        Link9 current = first;
        while(current != null)
        {
            current.displayLink();
            current = current.next;
        }
        System.out.println("");
    }
}

class ListIterator
{
    private Link9 current;
    private Link9 previous;
    private LinkList9 ourList;
    
    public ListIterator(LinkList9 list)
    {
        ourList = list;
        reset();
    }
    
    public void reset()//把迭代器复位，并放在表头
    {
        current = ourList.getFirst();
        previous = null;
    }
    public boolean atEnd()//判断当前节点是否为最后一个链节点
    {
        return (current.next == null);
    }
    public void nextLink()//到下一个链接点
    {
        previous = current;
        current = current.next;
    }
    public Link9 getCurrent()//得到当前链接点的内容
    {
        return current;
    }
    
    public void insertAfter(long dd)//在当前链接点后插入新的链节点
    {
        Link9 newLink = new Link9(dd);
        
        if(ourList.isEmpty())
        {
            ourList.setFirst(newLink);
            current = newLink;
        }
        else {
            newLink.next = current.next;
            current.next = newLink;
            nextLink();
        }
    }
    public void insertBefore(long dd)//在当前链接点前插入新的链节点
    {
        Link9 newLink = new Link9(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;
    }
}
public class interIterator5_9 {

    /**
     * @param args
     * @throws IOException 
     */
    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        LinkList9 theList = new LinkList9();
        ListIterator iter1 = theList.getIterator();
        long value;
        
        iter1.insertAfter(20);
        iter1.insertAfter(40);
        iter1.insertAfter(80);
        iter1.insertBefore(60);
        
        while(true)
        {
            System.out.println("Enter first letter of ");
            System.out.print("show,reset,next,get,before,after,delete: ");
            System.out.flush();
            int choice = getChar();
            switch (choice) {
            case 's':
                if(!theList.isEmpty())
                    theList.dispalyList();
                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 nextLink");
                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.println("Enter value to insert: ");
                System.out.flush();
                value = getInt();
                iter1.insertBefore(value);
                break;
            case 'a':
                System.out.println("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);
    }

}

　　如有问题，欢迎留言。

JAVA链表中迭代器的实现

相关推荐