java left logo
java middle logo
java right logo
 

Home arrow Java SE Tips
 
 
Main Menu
Home
Java Tutorials
Book Reviews
Java SE Tips
Java ME Tips
Java EE Tips
Other API Tips
Java Applications
Java Libraries
Java Games
Java Network
Java Forums
Java Blog




Most Visited Tips
Java SE Tips
Java ME Tips
Java EE Tips
Other API Tips
Java Applications
Java Libraries
Java Games
Book Reviews
Top Rated Tips
Java SE Tips
Java ME Tips
Java EE Tips
Other API Tips
Java Applications
Java Libraries
Java Games
Book Reviews


Statistics
Registered Users: 4084
Java SE Tips: 614
Java ME Tips: 202
Java EE Tips: 183
Other API Tips: 779
Java Applications: 298
Java Libraries: 209
Java Games: 16
Book Reviews:
 
 
 
Linked List Implementation in Java E-mail
User Rating: / 591
PoorBest 

In computer science, a linked list is one of the fundamental data structures used in computer programming. It consists of a sequence of nodes, each containing arbitrary data fields and one or two references ("links") pointing to the next and/or previous nodes. A linked list is a self-referential datatype because it contains a pointer or link to another data of the same type. Linked lists permit insertion and removal of nodes at any point in the list in constant time, but do not allow random access. Several different types of linked list exist: singly-linked lists, doubly-linked lists, and circularly-linked lists.

Linked lists can be implemented in most languages. Languages such as Lisp and Scheme have the data structure built in, along with operations to access the linked list. Procedural languages such as C, C++, and Java typically rely on mutable references to create linked lists.

Following code shows how to implement a linked list in 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;
}

 Related Tips

 
< Prev   Next >

Page 1 of 0 ( 0 comments )

You can share your information about this topic using the form below!

Please do not post your questions with this form! Thanks.


Name (required)


E-Mail (required)

Your email will not be displayed on the site - only to our administrator
Homepage(optional)



Comment Enable HTML code : Yes No



 
       
         
     
 
 
 
   
 
 
java bottom left
java bottom middle
java bottom right
RSS 0.91 FeedRSS 1.0 FeedRSS 2.0 FeedATOM FeedOPML Feed

Home - About Us - Privacy Policy
Copyright 2005 - 2008 www.java-tips.org
Java is a trademark of Sun Microsystems, Inc.