package DataStructures; class CursorNode { // Friently data;accessible by other package routines Object element; int next; // Constructers CursorNode(Object theElement) { this(theElement, 0); } CursorNode(Object theElement, int n) { element = theElement; next = n; } }
迭代器
package DataStructures; publicclass CursorListItr { int current; // Current position CursorListItr(int theNode) { current = theNode; } publicboolean IsPastEnd() { return current == 0; } public Object Retrieve() { return IsPastEnd() ? null : CursorList.cursorSpace[current].element; } publicvoid Advance() { if (!IsPastEnd()) { current = CursorList.cursorSpace[current].next; } } }
主类
package DataStructures; publicclass CursorList { privateint header; static CursorNode[] cursorSpace; privatestaticfinalint SPACE_SIZE = 100; static{ cursorSpace = new CursorNode[SPACE_SIZE]; for (int i = 0; i < SPACE_SIZE; i++) { cursorSpace[i] = new CursorNode(null, i + 1); } cursorSpace[SPACE_SIZE - 1].next = 0; } privatestaticint alloc() { int p = cursorSpace[0].next; cursorSpace[0].next = cursorSpace[p].next; if (p == 0) thrownew OutOfMemoryError(); return p; } privatestaticvoid free(int p) { cursorSpace[p].element = null; cursorSpace[p].next = cursorSpace[0].next; cursorSpace[0].next = p; } public CursorList() { header = alloc(); cursorSpace[header].next = 0; } publicboolean IsEmpty() { return cursorSpace[header].next == 0; } /** * Make the list logically empty. */ publicvoid MakeEmpty() { while (!IsEmpty()) Remove(First().Retrieve()); } public CursorListItr Zeroth() { returnnew CursorListItr(header); } public CursorListItr First() { returnnew CursorListItr(cursorSpace[header].next); } /** * Return iterator corresponding to the first node containing an tiem. * * @param x * the item to search for * @return an iterator;iterator IsPastEnd if item is not found. */ public CursorListItr Find(Object x) { int itr = cursorSpace[header].next; while (itr != 0 && cursorSpace[itr].element.equals(x)) itr = cursorSpace[itr].next; returnnew CursorListItr(itr); } /** * Insert after p. * * @param x * the item to insert. * @param p * the position prior to the newly inserted item. */ publicvoid Insert(Object x, CursorListItr p) { if (p != null && p.current != 0) { int pos = p.current; int tmp = alloc(); cursorSpace[tmp].element = x; cursorSpace[tmp].next = cursorSpace[pos].next; cursorSpace[pos].next = tmp; } } /** * Remove the first occurence of an item. * * @param x * the item to remove. */ publicvoid Remove(Object x) { CursorListItr p = FindPrevious(x); int pos = p.current; if (cursorSpace[pos].next != 0) { int tmp = cursorSpace[pos].next; cursorSpace[pos].next = cursorSpace[tmp].next; free(tmp); } } /** * Return iterator prior to the first node containing an item. * * @param x * the item to search for. * @return appropriate iterator if the item is found. Otherwise, the * iterator corresponding to the last element in the list is * returned. */ public CursorListItr FindPrevious(Object x) { int itr = header; while (cursorSpace[itr].next != 0 && !cursorSpace[cursorSpace[itr].next].element.equals(x)) itr = cursorSpace[itr].next; returnnew CursorListItr(itr); } }
