package DataStructures; class ListNode { //Frientdly data;accessible by other package routines Object element; ListNode next; // Constructers ListNode(Object theElement) { this(theElement, null); } ListNode(Object theElement, ListNode n) { element = theElement; next = n; } }
迭代器
package DataStructures; publicclass LinkedListItr { ListNode current; // Current position LinkedListItr(ListNode theNode) { current = theNode; } publicboolean IsPastEnd() { return current == null; } public Object Retrive() { return IsPastEnd() ? null : current.element; } publicvoid Advance() { if (!IsPastEnd()) current = current.next; } }
链表类
package DataStructures; publicclass LinkedList { private ListNode header; public LinkedList() { header = new ListNode(null); } publicboolean IsEmpty() { return header.next == null; } publicvoid makeEmpty() { header.next = null; } public LinkedListItr Zeroth() { returnnew LinkedListItr(header); } public LinkedListItr First() { returnnew LinkedListItr(header.next); } /** * Return iterator corresponding to the first node containing an item. * * @param x * the item to search for. * @return an iterator; iterator IsPastEnd if item is not found. */ public LinkedListItr Find(Object x) { ListNode itr = header.next; while (itr != null && !itr.element.equals(x)) itr = itr.next; returnnew LinkedListItr(itr); } /** * Remove th first occurrence of an item. * * @param x * the item to remove. */ publicvoid Remove(Object x) { LinkedListItr p = FindPrevious(x); if (p.current.next != null) p.current.next = p.current.next.next; // Bypass deleted node } /** * Return itreator 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 lis is returned. */ public LinkedListItr FindPrevious(Object x) { ListNode itr = header; while (itr.next != null && !itr.next.element.equals(x)) itr = itr.next; returnnew LinkedListItr(itr); } /** * Insert after p. * * @param x * the item to insear. * @param p * the position prior to the newly inserted item. */ publicvoid Insert(Object x, LinkedListItr p) { if (p != null && p.current != null) p.current.next = new ListNode(x, p.current.next); } // Simple print method publicstaticvoid PrintLinkedList(LinkedList theList) { if (theList.IsEmpty()) System.out.print("Empty list"); else{ LinkedListItr itr = theList.First(); for (; !itr.IsPastEnd(); itr.Advance()) System.out.print(itr.Retrive() + " "); } System.out.println(); } }
