Question? Leave a message!

Linked Lists, Stacks and Queues

Linked Lists, Stacks and Queues
Linked Lists, Stacks and QueuesImplementing Your Own Linked List  To create a doubly linked list as seen below  MyLinkedList class  Node class  LinkedListIterator class  Sentinel nodes at head and tail www.TheisisScientist.comEmpty Linked List  An empty double linked list with sentinel nodes. www.TheisisScientist.comInner classes  Inner class objects require the construction of an outer class object before they are instantiated.  Compiler adds an implicit reference to outer class in an inner class (MyArrayList.this).  Good for when you need several inner objects to refer to exactly one outer object (as in an Iterator object). www.TheisisScientist.comNested classes  Considered part of the outer class, thus no issues of visibility.  No reference to the outer class. If a nested (static) class has public accessibility, then it can be instantiated without the outer class.  Making an inner class private means only the outer class may access the data fields within the nested class.  Is Node a prime candidate for nested or inner class public or private www.TheisisScientist.comImplementation for MyLinkedList 1. Class declaration and nested Node class public class MyLinkedListAnyType implements IterableAnyType // static key word makes Node a nested class private static class NodeAnyType public Node( AnyType d, NodeAnyType p, NodeAnyType n ) data = d; prev = p; next = n; public AnyType data; public NodeAnyType prev; public NodeAnyType next; www.TheisisScientist.com2. Data Fields and Accessors private int theSize; //used to help iterator detect changes in List private int modCount = 0; private NodeAnyType beginMarker; //head node private NodeAnyType endMarker; //tail node public int size( ) return theSize; public boolean isEmpty( ) return size( ) == 0; www.TheisisScientist.com3. Constructor(s) public MyLinkedList( ) clear( ); // Changes the size of this collection to zero. public void clear( ) beginMarker = new NodeAnyType( null, null,null ); endMarker = new NodeAnyType( null, beginMarker, null ); = endMarker; theSize = 0; modCount++; www.TheisisScientist.com4. More Accessors and Mutators public boolean add( AnyType x ) add( size( ), x ); return true; public void add( int idx, AnyType x ) addBefore( getNode( idx ), x ); public AnyType get( int idx ) return getNode( idx ).data; public AnyType set( int idx, AnyType newVal ) NodeAnyType p = getNode( idx ); AnyType oldVal =; = newVal; return oldVal; public AnyType remove( int idx ) return remove( getNode( idx ) ); www.TheisisScientist.com5. getNode Method private NodeAnyType getNode( int idx ) NodeAnyType p; if( idx 0 idx size( ) ) throw new IndexOutOfBoundsException( ); if( idx size( ) / 2 ) p =; for( int i = 0; i idx; i++ ) p =; else p = endMarker; for( int i = size( ); i idx; i ) p = p.prev; return p; www.TheisisScientist.com6. addBefore Method private void addBefore(NodeAnyType p, AnyType x) NodeAnyType newNode = new NodeAnyType( x, p.prev, p ); = newNode; p.prev = newNode; theSize++; modCount++; www.TheisisScientist.com7. remove and iterator Methods private AnyType remove( NodeAnyType p ) = p.prev; =; theSize; modCount++; return; //required by the Iterable interface public java.util.IteratorAnyType iterator( ) return new LinkedListIterator( ); www.TheisisScientist.com8a. LinkedListIterator class import java.util.; private class LinkedListIteratorAnyType implements IteratorAnyType private NodeAnyType current =; //used to check for modifications to List private int expectedModCount = modCount; private boolean okToRemove = false; public boolean hasNext( ) return current = endMarker; //continues on next slide… www.TheisisScientist.com8b. LinkedListIterator class public AnyType next( ) if( modCount = expectedModCount ) throw new ConcurrentModificationException( ); if( hasNext( ) ) throw new NoSuchElementException( ); AnyType nextItem =; current =; okToRemove = true; return nextItem; //continues on next slide… www.TheisisScientist.com8c. LinkedListIterator class public void remove( ) if( modCount = expectedModCount ) throw new ConcurrentModificationException( ); if( okToRemove ) throw new IllegalStateException( ); MyLinkedList.this.remove(current.prev); okToRemove = false; ++expectedModCount; // end of remove Method // end of LinkedListIterator class //end of MyLinkedList class www.TheisisScientist.comStacks  A restricted list where insertions and deletions can only be performed at one location, the end of the list (top).  LIFO – Last In First Out  Laundry Basket – last thing you put in is the first thing you remove  Plates – remove from the top of the stack and add to the top of the stack www.TheisisScientist.comStack ADT  Basic operations are  Stack Model push, pop, and top www.TheisisScientist.comAdapting Lists to Implement Stacks  Adapter Design Pattern  Allow a client to use a class whose interface is different from the one expected by the client  Do not modify client or class, write adapter class that sits between them  In this case, the List is an adapter for the Stack. The client (user) calls methods of the Stack which in turn calls appropriate List method(s). www.TheisisScientist.comAdapter Model for Stack Client (Stack user) theStack.push( 10 ) Stack (adapter) theList.add(0, 10 ) ; List (adaptee) www.TheisisScientist.comQueues  Restricted List  only add to head  only remove from tail  Examples  line waiting for service  jobs waiting to print  Implement as an adapter of List www.TheisisScientist.comQueue ADT  Basic Operations are enqueue and dequeue www.TheisisScientist.comAdapter Model for Queue Client (Queue user) theQ.enqueue( 10 ) Queue (adapter) theList.add(theList.size() 1, 10 ) List (adaptee)
Document Information
User Name:
User Type:
United Arab Emirates
Uploaded Date: