+-------+ +-------+ +--------+ +--->| 3 | o---->| 1 | o---->| 5 |NULL| | +-------+ +-------+ +--------+ | head
+---------------+
| |
+-----|-+ +-------+ | +--------+
+--->| 3 | o | | 1 | o | +->| 5 |NULL|
| +-------+ +-------+ +--------+
|
head
+-------+ +-------+ +--------+
+--->| 3 | o---->| 1 | o | +->| 5 |NULL|
| +-------+ +-----|-+ | +--------+
| | +-------+ |
head +->| 2 | o---+
+-------+
package DataStructures;
class ListNode
{
// data: accessible by other classes in the package
Object element;
ListNode next;
// Constructors
ListNode (Object theElement)
{
this(theElement, null);
}
ListNode (Object theElement, ListNode n)
{
element = theElement;
next = n;
}
}
+---+---+ +---+---+ +---+---+ +---+----+
+-->| 3 | o--->| 1 | o--->| 2 | o--->| 5 |NULL|
| +---+---+ +---+---+ +---+---+ +---+----+
+-|-+ ^
header | o | |
+---+ +-----------|---+
| +-|-+ |
| current | o | |
| +---+ |
+---------------+
a LinkedListItr object
package DataStructures;
public class LinkedListItr
{
//data fields
ListNode current; // current position
LinkedListItr( ListNode theNode)
{
current = theNode;
}
public boolean isPastEnd()
{
return current == null;
}
public Object retrieve()
{
return isPastEnd() ? null : current.element;
}
public void advance()
{
if( !isPastEnd() )
current = current.next;
}
}
+---+---+ +---+---+ +---+----+
+---->| | o---->| 3 | o---->| 1 |NULL|
| +---+---+ +---+---+ +---+----+
+-|-+ dummy node real data
header | o | starts from here
+---+
Header node is useful for eliminating cumbersome
"special cases" when nodes are inserted/deleted
at the front.package DataStructures;
public class LinkedList
{
// data
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
* containning an item.
* @param x the item to search for
*/
public LinkedListItr find (Object x )
{
ListNode itr = header.next;
while(itr != null && !itr.element.equals( x ) )
itr = itr.next;
return new LinkedListItr (itr);
}
/**
* Remove the 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;
}
/**
* Return iterator prior to the first node containing an item.
* @param x the item to search for
* @return the appropriate iterator if the item is found.
* Otherwise the iterator corresponding th the last element in
* the list 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 insert
* @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 printLinst(LinkedList theList)
{
if (theList.isEmpty() )
System.out.print("Empty List");
else
{
LinkedListItr itr = theList.first();
for( ; !itr.isPastEnd(); itr.advance() )
System.out.print(itr.retrieve() + " ");
}
System.out.println();
}
public class Polynomial
{
public static final int MAX_DEGREE = 100;
private int coefArray[] = new int [MAX_DEGREE + 1];
private int highPower = 0;
public Polynomial()
{
zeroPolynomial();
}
public void insertTerm (int coef, int exp )
{
// ...
}
public void zeroPolynomial()
{
for (int i = 0; i <= MAX_DEGREE; i++ )
coeffArray[i];
highPower = 0;
}
public Polynomial add( Polynomial rhs)
{
Polynomial sum = new Polynomial();
sum.highPower = max(highPower, rhs.highPower);
for ( int i = sum.highPower; i >= 0; i-- )
sum.coeffArray[i] = coeffArray[i] + rhs.coeffArray[i];
return sum;
}
public Polynomial multiply( Polynomial rhs) throws Overflow
{
Polynomial product = new Polynomial();
product.highPower = highPower + rhs.highPower;
if (product.highPower > MAX_DEGREE )
throw new Overflow;
for (int i = 0; i <= highPower; i++ )
for (int j = 0; j <= rhs.highPower; j++ )
product.coeffArray[i+j] += coeffArray[i] * rhs.coeffArray[j];
return product;
}
}
public class Literal
{
Various constructors (not shown)
int coefficient;
int exponent;
}
public class Polynomial
{
private LinkedList terms;
public Polynomial()
{ ... }
public void insertTerm(int coed, int exp)
{ ... }
public void zeroPolynomial()
{ ... }
public Polynomial add(Polynomial rhs)
{ ... }
public Polynomial multiply ( Polynomial rhs )
{ ... }
public void print()
{ ... }
}
import java.util.*; // need to import
public class JLTest
{
public static void main(String[] args)
{
LinkedList lst = new LinkedList();
// addLast(obj)
lst.addLast(new Character('A'));
lst.addLast(new Character('B'));
lst.addLast(new Character('C'));
System.out.println(lst); // [A, B, C]
// add(index, obj)
lst.add(0, new Character('X')); // 0-based index, insert at/before
System.out.println(lst); // [X, A, B, C]
// remove(obj)
boolean result = lst.remove(new Character('B'));
System.out.println(result); // true
System.out.println(lst); // [X, A, C]
// remove(index)
Character c = (Character) lst.remove(2);
System.out.println(c); // C
System.out.println(lst); // [X, A]
// get(index)
Character c2 = (Character) lst.get(1);
System.out.println(c2); // A
}
}
ListIterator it = lst.listIterator(0); // 0-based index
while (it.hasNext())
System.out.println
("Element: " + it.next()); // advance it and returns element
// which used be pointed
Worst case complexity
Operation LinkedList ArrayList add(obj) O(1) O(1) add(0,obj) O(1) O(n) add(index,obj) O(n) O(n) remove(0,obj) O(1) O(n) remove(index,obj) O(n) O(n) remove() (iterator) O(1) O(n) contains O(n) O(n) get O(n) O(1) set O(n) O(1)
LinkedList lst = new LinkedList();
lst.addLast(new Character('A'));
lst.addLast(new Character('B'));
lst.addLast(new Character('C')); // lst is [A, B, C]
ListIterator it2 = lst.listIterator(0); // it points to A
it2.next(); // it points to B
it2.remove(); // call remove
System.out.println(lst);
Basic concepts
have node pool of all nodes, keep list of free ones
use pool indices in place of pointers; 0 == NULL
data stored as collection of nodes: data and next without dynamic memory allocation
// Basic node stored in a linked list -- cursor version
// Note that this class is not accessible outside
// of package DataStructures
class CursorNode
{
// Constructors
CursorNode( Object theElement )
{
this( theElement, 0 );
}
CursorNode( Object theElement, int n )
{
element = theElement;
next = n;
}
// Friendly data; accessible by other package routines
Object element;
int next;
}
// CursorList class
//
// CONSTRUCTION: with no initializer
// Access is via CursorListItr class
//
// ******************PUBLIC OPERATIONS*********************
// boolean isEmpty( ) --> Return true if empty; else false
// void makeEmpty( ) --> Remove all items
// CursorListItr zeroth( )--> Return position to prior to first
// CursorListItr first( ) --> Return first position
// void insert( x, p ) --> Insert x after current iterator position p
// void remove( x ) --> Remove x
// CursorListItr find( x )
// --> Return position that views x
// CursorListItr findPrevious( x )
// --> Return position prior to x
// ******************ERRORS********************************
// No special errors
/**
* Linked list implementation of the list
* using a header node; cursor version.
* Access to the list is via CursorListItr.
* @author Mark Allen Weiss
* @see CursorListItr
*/
public class CursorList
{
private static int alloc( )
{
int p = cursorSpace[ 0 ].next;
cursorSpace[ 0 ].next = cursorSpace[ p ].next;
if( p == 0 )
throw new OutOfMemoryError( );
return p;
}
private static void free( int p )
{
cursorSpace[ p ].element = null;
cursorSpace[ p ].next = cursorSpace[ 0 ].next;
cursorSpace[ 0 ].next = p;
}
/**
* Construct the list.
*/
public CursorList( )
{
header = alloc( );
cursorSpace[ header ].next = 0;
}
/**
* Test if the list is logically empty.
* @return true if empty, false otherwise.
*/
public boolean isEmpty( )
{
return cursorSpace[ header ].next == 0;
}
/**
* Make the list logically empty.
*/
public void makeEmpty( )
{
while( !isEmpty( ) )
remove( first( ).retrieve( ) );
}
/**
* Return an iterator representing the header node.
*/
public CursorListItr zeroth( )
{
return new CursorListItr( header );
}
/**
* Return an iterator representing the first node in the list.
* This operation is valid for empty lists.
*/
public CursorListItr first( )
{
return new CursorListItr( cursorSpace[ header ].next );
}
/**
* Insert after p.
* @param x the item to insert.
* @param p the position prior to the newly inserted item.
*/
public void insert( Object x, CursorListItr p )
{
if( p != null && p.current != 0 )
{
int pos = p.current;
int tmp = alloc( );
cursorSpace[ tmp ].element = x;
cursorSpace[ tmp ].next = cursorSpace[ pos ].next;
cursorSpace[ pos ].next = tmp;
}
}
/**
* 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 CursorListItr find( Object x )
{
/* 1*/ int itr = cursorSpace[ header ].next;
/* 2*/ while( itr != 0 && !cursorSpace[ itr ].element.equals( x ) )
/* 3*/ itr = cursorSpace[ itr ].next;
/* 4*/ return new CursorListItr( itr );
}
/**
* 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 CursorListItr findPrevious( Object x )
{
/* 1*/ int itr = header;
/* 2*/ while( cursorSpace[ itr ].next != 0 &&
!cursorSpace[ cursorSpace[ itr ].next ].element.equals( x ) )
/* 3*/ itr = cursorSpace[ itr ].next;
/* 4*/ return new CursorListItr( itr );
}
/**
* Remove the first occurrence of an item.
* @param x the item to remove.
*/
public void remove( Object x )
{
CursorListItr p = findPrevious( x );
int pos = p.current;
if( cursorSpace[ pos ].next != 0 )
{
int tmp = cursorSpace[ pos ].next;
cursorSpace[ pos ].next = cursorSpace[ tmp ].next;
free( tmp );
}
}
// Simple print method
static public void printList( CursorList theList )
{
if( theList.isEmpty( ) )
System.out.print( "Empty list" );
else
{
CursorListItr itr = theList.first( );
for( ; !itr.isPastEnd( ); itr.advance( ) )
System.out.print( itr.retrieve( ) + " " );
}
System.out.println( );
}
private int header;
static CursorNode[ ] cursorSpace;
private static final int SPACE_SIZE = 100;
static
{
cursorSpace = new CursorNode[ SPACE_SIZE ];
for( int i = 0; i < SPACE_SIZE; i++ )
cursorSpace[ i ] = new CursorNode( null, i + 1 );
cursorSpace[ SPACE_SIZE - 1 ].next = 0;
}
public static void main( String [ ] args )
{
CursorList theList = new CursorList( );
CursorListItr theItr;
int i;
theItr = theList.zeroth( );
printList( theList );
for( i = 0; i < 10; i++ )
{
theList.insert( new MyInteger( i ), theItr );
printList( theList );
theItr.advance( );
}
for( i = 0; i < 10; i += 2 )
theList.remove( new MyInteger( i ) );
for( i = 0; i < 10; i++ )
if( ( i % 2 == 0 ) != ( theList.find( new MyInteger( i ) ).isPastEnd( ) ) )
System.out.println( "Find fails!" );
System.out.println( "Finished deletions" );
printList( theList );
}
}
// CursorListItr class; maintains "current position"
//
// CONSTRUCTION: Package friendly only, with a CursorNode
//
// ******************PUBLIC OPERATIONS*********************
// void advance( ) --> Advance
// boolean isPastEnd( ) --> 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; cursor version.
* @author Mark Allen Weiss
* @see CursorList
*/
public class CursorListItr
{
/**
* Construct the list iterator
* @param theNode any node in the linked list.
*/
CursorListItr( int theNode )
{
current = theNode;
}
/**
* Test if the current position is past the end of the list.
* @return true if the current position is null-equivalent.
*/
public boolean isPastEnd( )
{
return current == 0;
}
/**
* 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 isPastEnd( ) ? null : CursorList.cursorSpace[ current ].element;
}
/**
* Advance the current position to the next node in the list.
* If the current position is null, then do nothing.
*/
public void advance( )
{
if( !isPastEnd( ) )
current = CursorList.cursorSpace[ current ].next;
}
int current; // Current position
}