Unformatted text preview:

COP 3540 Data Structures with OOPAbstract Data TypesA Stack Implemented by a Linked ListPowerPoint PresentationSlide 5Slide 6Slide 7Discussion of Stack implemented with a Linked ListA Queue Implemented by a Linked ListSlide 10Slide 11Slide 12Slide 13Slide 14Discussion of Queues Implemented via Linked ListsData Types and AbstractionSlide 17ADTs as a Design Tool ( Think country classes…)Example of a Subsystem (Architectural Design)SORTED Linked LISTSJava Code to Insert an item into a Sorted ListAdditional ConsiderationsSlide 23Efficiency of Sorted Linked Lists1/26COP 3540 Data Structures with OOP Chapter 5 - Part 2Linked ListsAbstract Data Types and Sorted Lists2/26Abstract Data Types A wonderful way to deal with data structures.An ADT is a way of looking at a data structure focusing on what it does and NOT how it does whatever it is supposed to do.We implement an ADTStacks and Queues are examples of ADTs.They are ‘concepts’ ; logical data structures.Let’s first look how we can have a linked list that implements a stack.3/26A Stack Implemented by a Linked ListCan use an array, but no chance to extend it. Basic operations: push() and pop() implemented as arr[++top] = newdata; and returnedData = arr[top--];Indexes are checked for stack overflow and stack underflow and then adjusted as shown.For a Stack: implemented as a linked list, we have theList.insertFirst(data) to add an element onto the stack•(looks like a ‘push’)Retrieved data = theList.deleteFirst(). (looks like a pop) The important things: user calls push() and pop() for his/her stack operations and has no knowledge whether the logical stack is implemented as a physical array or as a physical linked list!4/26class LinkStackApp { public static void main(String[] args) { LinkStack theStack = new LinkStack(); // makes one stack object// We know nothing about the stack’s implementation from declaration. theStack.push(20); // push items theStack.push(40); theStack.displayStack(); // display stack theStack.push(60); // push items All generic at this point; abstract! theStack.push(80); theStack.displayStack(); // display stack theStack.pop(); // pop items theStack.pop(); theStack.displayStack(); // display stack } // end main() } // end class LinkStackApp all standard stack operations!!Client Application5/26 class Link (objects of this class are the nodes themselves!) { public long dData; // data item public Link next; // next link in list; note: single link.// ------------------------------------------------------------- public Link(long dd) // constructor { dData = dd; }// ------------------------------------------------------------- public void displayLink() // display ourself { System.out.print(dData + " "); } } // end class Link// Note: this is really only the data (and the link) and not the most important methods…No Changes here…just the nodes…6/26class LinkStack { private LinkList theList; ===============================//-------------------------------------------------------------- public LinkStack() // constructor { theList = new LinkList(); }//-------------------------------------------------------------- public void push(long j) // put item on top of stack { theList.insertFirst(j); }//-------------------------------------------------------------- public long pop() // take item from top of stack { return theList.deleteFirst(); }//-------------------------------------------------------------- public boolean isEmpty() // true if stack is empty { return ( theList.isEmpty() ); }//-------------------------------------------------------------- public void displayStack() { System.out.print("Stack (top-->bottom): "); theList.displayList(); }//-------------------------------------------------------------- } // end class LinkStackClient made an object of this class.This is the Interface to the implementationCan see a generic ‘push’ and ‘pop’ etc….User sees the headers; not the implementation.See some implementation via the constructor where a linked list is created.7/26class LinkList { private Link first; // ref to first item on list public LinkList() // constructor { first = null; } // no items on list yet public boolean isEmpty() // true if list is empty { return (first==null); } public void insertFirst(long dd) // insert at start of list { // make new link Link newLink = new Link(dd); newLink.next = first; // newLink --> old first first = newLink; // first --> newLink //can you draw these steps??? } public long deleteFirst() // delete first item insertion part { // (assumes list not empty) deletion part too Link temp = first; // save reference to link first = first.next; // delete it: first-->old next return temp.dData; // return deleted link //can you draw these steps??? } public void displayList() { Link current = first; // start at beginning of list while(current != null) // until end of list, { current.displayLink(); // print data current = current.next; // move to next link } System.out.println(""); } // end class LinkListHere’s the linked list implementation!Here is your control class for the Linked List – your ‘collection class,’ if you will”Note the methods and what they operate on!!Note: the push is implemented via insertFirst()The pop is implemented via deleteFirst(). which are linked list operations.Logical operations implemented on physical structures8/26Discussion of Stack implemented with a Linked ListIn the LinkStackApp, we pushed two items onto the stackDisplayed the stackPushed two more itemsDisplayed stack againPopped two itemsDisplayed the remaining stack.Design: LinkStackApp  LinkStack  LinkList  Link.Beautiful part: When client calls push() or pop(), generic stack operations, s/he has no idea HOW the stack is implemented!!9/26A Queue Implemented by a Linked ListSame song, second verse.Idea is


View Full Document

UNF COP 3540 - Linked Lists

Download Linked Lists
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Linked Lists and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Linked Lists 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?