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 ADTStacks 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 ListCan 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 ListIn the LinkStackApp, we pushed two items onto the stackDisplayed the stackPushed two more itemsDisplayed stack againPopped two itemsDisplayed 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 ListSame song, second verse.Idea is
View Full Document