节点
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;
public
class LinkedListItr
{
ListNode current; // Current position
LinkedListItr(ListNode theNode) {
current = theNode;
}
public boolean IsPastEnd() {
return current == null;
}
public Object Retrive() {
return IsPastEnd() ? null : current.element;
}
public void Advance() {
if (!IsPastEnd())
current = current.next;
}
}
链表类
package DataStructures;
public
class LinkedList
{
private ListNode header;
public LinkedList() {
header = new ListNode(null);
}
public boolean IsEmpty() {
return header.next == null;
}
public void makeEmpty() {
header.next = null;
}
public LinkedListItr Zeroth() {
return new LinkedListItr(header);
}
public LinkedListItr First() {
return new 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;
return new LinkedListItr(itr);
}
/**
* Remove th first occurrence of an item.
*
* @param x
* the item to remove.
*/
public void 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;
return new LinkedListItr(itr);
}
/**
* Insert after p.
*
* @param x
* the item to insear.
* @param p
* the position prior to the newly inserted item.
*/
public void Insert(Object x, LinkedListItr p) {
if (p != null && p.current != null)
p.current.next = new ListNode(x, p.current.next);
}
// Simple print method
public static void 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();
}
}
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;
public
class LinkedListItr
{ ListNode current; // Current position LinkedListItr(ListNode theNode) { current = theNode; } public boolean IsPastEnd() { return current == null; } public Object Retrive() { return IsPastEnd() ? null : current.element; } public void Advance() { if (!IsPastEnd()) current = current.next; }}
链表类
package DataStructures;
public
class LinkedList
{ private ListNode header; public LinkedList() { header = new ListNode(null); } public boolean IsEmpty() { return header.next == null; } public void makeEmpty() { header.next = null; } public LinkedListItr Zeroth() { return new LinkedListItr(header); } public LinkedListItr First() { return new 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; return new LinkedListItr(itr); } /** * Remove th first occurrence of an item. * * @param x * the item to remove. */ public void 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; return new LinkedListItr(itr); } /** * Insert after p. * * @param x * the item to insear. * @param p * the position prior to the newly inserted item. */ public void Insert(Object x, LinkedListItr p) { if (p != null && p.current != null) p.current.next = new ListNode(x, p.current.next); } // Simple print method public static void 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(); }}
本文转自冬冬博客园博客，原文链接：http://www.cnblogs.com/yuandong/archive/2006/08/19/481154.html
，如需转载请自行联系原作者
