Связанный список реализации в Java

В компьютерной науке, связанный список является одной из основных структур данных, используемых в программировании. Он состоит из последовательности узлов, каждый из которых содержит произвольные поля данных и одну или две ссылки ( "Links"), указывающие на следующий и / или предыдущих узлах. Связанный список является самостоятельным ссылочных типов данных, поскольку она содержит указатель или ссылку на другой данные того же типа. Связные списки разрешение вставки и удаления узлов в любом месте в списке на постоянное время, но не допускает произвольного доступа. Несколько различных типов связанном списке существует: однократно связанных списков, двусвязные спискам, и циркулярно-связанных списков.

Связные списки могут быть реализованы в самое Языки. Языки таких как Лисп и схемы, структуры данных, встроенная, наряду с операциями доступа к связанному списку. Процедурный Языки таких как C, C, Java, и как правило, полагаются на изменяемые ссылки для создания связанных списков.

Следующий код показывает, как осуществлять связный список в Java:


// LinkedList class

//

// CONSTRUCTION: with no initializer

// Access is via LinkedListIterator class

//

// ******************PUBLIC OPERATIONS*********************

// boolean isEmpty( )     --> Return true if empty; else false

// void makeEmpty( )      --> Remove all items

// LinkedListIterator zeroth( )

//                        --> Return position to prior to first

// LinkedListIterator first( )

//                        --> Return first position

// void insert( x, p )    --> Insert x after current iterator position p

// void remove( x )       --> Remove x

// LinkedListIterator find( x )

//                        --> Return position that views x

// LinkedListIterator findPrevious( x )

//                        --> Return position prior to x

// ******************ERRORS********************************

// No special errors



/**

 * Linked list implementation of the list

 *    using a header node.

 * Access to the list is via LinkedListIterator.

 @author Mark Allen Weiss

 @see LinkedListIterator

 */

public class LinkedList {

    /**

     * Construct the list

     */

    public LinkedList( ) {

        header = new ListNodenull );

    }

    

    /**

     * Test if the list is logically empty.

     @return true if empty, false otherwise.

     */

    public boolean isEmpty( ) {

        return header.next == null;

    }

    

    /**

     * Make the list logically empty.

     */

    public void makeEmpty( ) {

        header.next = null;

    }

    

    /**

     * Return an iterator representing the header node.

     */

    public LinkedListIterator zeroth( ) {

        return new LinkedListIteratorheader );

    }

    

    /**

     * Return an iterator representing the first node in the list.

     * This operation is valid for empty lists.

     */

    public LinkedListIterator first( ) {

        return new LinkedListIteratorheader.next );

    }

    

    /**

     * Insert after p.

     @param x the item to insert.

     @param p the position prior to the newly inserted item.

     */

    public void insertObject x, LinkedListIterator p ) {

        ifp != null && p.current != null )

            p.current.next = new ListNodex, p.current.next );

    }

    

    /**

     * Return iterator corresponding to the first node containing an item.

     @param x the item to search for.

     @return an iterator; iterator is not valid if item is not found.

     */

    public LinkedListIterator findObject x ) {

        ListNode itr = header.next;

        

        whileitr != null && !itr.element.equals) )

            itr = itr.next;

        

        return new LinkedListIteratoritr );

    }

    

    /**

     * 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 LinkedListIterator findPreviousObject x ) {

        ListNode itr = header;

        

        whileitr.next != null && !itr.next.element.equals) )

            itr = itr.next;

        

        return new LinkedListIteratoritr );

    }

    

    /**

     * Remove the first occurrence of an item.

     @param x the item to remove.

     */

    public void removeObject x ) {

        LinkedListIterator p = findPrevious);

        

        ifp.current.next != null )

            p.current.next = p.current.next.next;  // Bypass deleted node

    }

    

    // Simple print method

    public static void printListLinkedList theList ) {

        iftheList.isEmpty( ) )

            System.out.print"Empty list" );

        else {

            LinkedListIterator itr = theList.first( );

            for; itr.isValid( ); itr.advance( ) )

                System.out.printitr.retrieve( ) " " );

        }

        

        System.out.println( );

    }

    

    private ListNode header;

    

    // In this routine, LinkedList and LinkedListIterator are the

    // classes written in Section 17.2.

    public static int listSizeLinkedList theList ) {

        LinkedListIterator itr;

        int size = 0;

        

        foritr = theList.first(); itr.isValid(); itr.advance() )

            size++;

        

        return size;

    }

    

    public static void mainString [ ] args ) {

        LinkedList         theList = new LinkedList( );

        LinkedListIterator theItr;

        int i;

        

        theItr = theList.zeroth( );

        printListtheList );

        

        fori = 0; i < 10; i++ ) {

            theList.insertnew Integer), theItr );

            printListtheList );

            theItr.advance( );

        }

        System.out.println"Size was: " + listSizetheList ) );

        

        fori = 0; i < 10; i += )

            theList.removenew Integer) );

        

        fori = 0; i < 10; i++ )

            if( ( i % == == theList.findnew Integer) ).isValid( ) ) )

                System.out.println"Find fails!" );

        

        System.out.println"Finished deletions" );

        printListtheList );

    }

    

}





// LinkedListIterator class; maintains "current position"

//

// CONSTRUCTION: Package visible only, with a ListNode

//

// ******************PUBLIC OPERATIONS*********************

// void advance( )        --> Advance

// boolean isValid( )     --> True if at valid position in list

// Object retrieve        --> Return item in current position



/**

 * Linked list implementation of the list iterator

 *    using a header node.

 @author Mark Allen Weiss

 @see LinkedList

 */

public class LinkedListIterator {

    /**

     * Construct the list iterator

     @param theNode any node in the linked list.

     */

    LinkedListIteratorListNode theNode ) {

        current = theNode;

    }

    

    /**

     * Test if the current position is a valid position in the list.

     @return true if the current position is valid.

     */

    public boolean isValid( ) {

        return current != null;

    }

    

    /**

     * Return the item stored in the current position.

     @return the stored item or null if the current position

     * is not in the list.

     */

    public Object retrieve( ) {

        return isValid( ) ? current.element : null;

    }

    

    /**

     * Advance the current position to the next node in the list.

     * If the current position is null, then do nothing.

     */

    public void advance( ) {

        ifisValid( ) )

            current = current.next;

    }

    

    ListNode current;    // Current position

}





// Basic node stored in a linked list

// Note that this class is not accessible outside

// of package weiss.nonstandard



class ListNode {

    // Constructors

    public ListNodeObject theElement ) {

        thistheElement, null );

    }

    

    public ListNodeObject theElement, ListNode n ) {

        element = theElement;

        next    = n;

    }

    

    public Object   element;

    public ListNode next;

}

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>