单链表_JAVA描述《数据结构与算法分析》

节点

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;

}

迭代器

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;

链表类

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.

     *            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.

     * @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))

     * Insert after p.

     *            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，如需转载请自行联系原作者