深入理解链表迭代器：原理、实现与应用

### 深入理解链表迭代器：原理、实现与应用 #### 1. 迭代器基本操作 在链表操作中，迭代器扮演着至关重要的角色。它提供了一系列方便的方法来对链表进行操作，主要的操作方法如下： - `insertAfter()`：在迭代器当前指向的链接之后插入一个新的链接。 - `insertBefore()`：在迭代器当前指向的链接之前插入一个新的链接。 - `deleteCurrent()`：删除迭代器当前指向的链接。 用户可以使用`reset()`方法将迭代器重置到链表的起始位置，使用`nextLink()`方法将迭代器移动到下一个链接。通过`atEnd()`方法，用户可以检查迭代器是否已经到达链表的末尾。 在设计迭代器和链表类的职责划分时，并不是一件容易的事情。例如，`insertBefore()`方法在迭代器类中实现效果较好，而`insertFirst()`方法，即总是在链表开头插入新链接的方法，放在链表类中实现可能更为合适。虽然我们在链表类中保留了`displayList()`方法，但实际上也可以通过迭代器的`getCurrent()`和`nextLink()`方法来实现相同的功能。 #### 2. interIterator.java 程序 `interIterator.java`程序提供了一个交互式界面，允许用户直接控制迭代器。程序启动后，用户可以通过输入相应的字母来执行以下操作： | 输入字母 | 操作说明 | | ---- | ---- | | s | 显示链表的内容 | | r | 将迭代器重置到链表的起始位置 | | n | 将迭代器移动到下一个链接 | | g | 获取当前链接的内容 | | b | 在当前链接之前插入一个新链接 | | a | 在当前链接之后插入一个新链接 | | d | 删除当前链接 | 以下是`interIterator.java`程序的完整代码： ```java // interIterator.java // demonstrates iterators on a linked listListIterator // to run this program: C>java InterIterApp import java.io.*; // for I/O //////////////////////////////////////////////////////////////// class Link { public long dData; // data item public Link next; // next link in list // ------------------------------------------------------------- public Link(long dd) // constructor { dData = dd; } // ------------------------------------------------------------- public void displayLink() // display ourself { System.out.print(dData + " "); } } // end class Link //////////////////////////////////////////////////////////////// class LinkList { private Link first; // ref to first item on list // ------------------------------------------------------------- public LinkList() // constructor { first = null; } // no items on list yet // ------------------------------------------------------------- public Link getFirst() // get value of first { return first; } // ------------------------------------------------------------- public void setFirst(Link f) // set first to new link { first = f; } // ------------------------------------------------------------- public boolean isEmpty() // true if list is empty { return first==null; } // ------------------------------------------------------------- public ListIterator getIterator() // return iterator { return new ListIterator(this); // initialized with } // this list // ------------------------------------------------------------- public void displayList() { Link current = first; // start at beginning of list while(current != null) // until end of list, { current.displayLink(); // print data current = current.next; // move to next link } System.out.println(""); } // ------------------------------------------------------------- } // end class LinkList //////////////////////////////////////////////////////////////// class ListIterator { private Link current; // current link private Link previous; // previous link private LinkList ourList; // our linked list //-------------------------------------------------------------- public ListIterator(LinkList list) // constructor { ourList = list; reset(); } //-------------------------------------------------------------- public void reset() // start at ‘first’ { current = ourList.getFirst(); previous = null; } //-------------------------------------------------------------- public boolean atEnd() // true if last link { return (current.next==null); } //-------------------------------------------------------------- public void nextLink() // go to next link { previous = current; current = current.next; } //-------------------------------------------------------------- public Link getCurrent() // get current link { return current; } //-------------------------------------------------------------- public void insertAfter(long dd) // insert after { // current link Link newLink = new Link(dd); if( ourList.isEmpty() ) // empty list { ourList.setFirst(newLink); current = newLink; } else // not empty { newLink.next = current.next; current.next = newLink; nextLink(); // point to new link } } //-------------------------------------------------------------- public void insertBefore(long dd) // insert before { // current link Link newLink = new Link(dd); if(previous == null) // beginning of list { // (or empty list) newLink.next = ourList.getFirst(); ourList.setFirst(newLink); reset(); } else // not beginning { newLink.next = previous.next; previous.next = newLink; current = newLink; } } //-------------------------------------------------------------- public long deleteCurrent() // delete item at current { long value = current.dData; if(previous == null) // beginning of list { ```