Understanding Java StackSet Operations and Linked Cells

StackSet: Notes on Linked Cells in Java Your code has several classes, most notably the class that represents the entire StackSet data structure, and the class that is a linked cell (an element in the stack). mySST The class that is the entire StackSet has the methods of the ADT (constructors, push, pop, size, etc.) and will have some data fields. head constructor function One data field is size an integer that tells how many items are in the list. push, pop, etc. function size One field is limit, which is the upper limit to how many elements can be stored at one time (comes from the argument to the constructor) limit

Initial State (after the constructor) Another field is named head. This field will give access to the chain of linked cells that contain the elements that are in the data structure. The head field will directly point to an object of the Node class When the StackSet object is first created, the head field is null (there are no data cells in the stack) State shown exists after call new StackSet(25) with null head pointer and 0 in size. Field limit is set to 25, since that is the parameter value sent to the constructor mySST head constructor function push, pop, etc. function size 0 limit 25

Pointers in Java code An arrow in box-arrow diagram, I call a pointer In Java this is a reference to an object ( or just an object ) Reference is the address in memory where the object storage is located public class Node { double val; Node next ; // link . . . } val 12.5 23.74 -17.8 val val next next next 1 2 0

Operation push Sometimes push acts like a normal stack, sometimes its different. Consider StackSet S and a call to S.push(n) Lets assume S.size() is smaller than S.limit() This means there is room for one more item in L If n is not already in S, then the push acts like a normal stack and leaves n as the top element the size of S increases by 1 we return true If n is in S already, then we don t want it to be added again so we move n to the top (and leave all the other elements in the same relative order) the size of S does not change we turn true

Operation push Now let s assume S.size() is equal to S.limit() This means there is no room for one more item in S However, we might still be able to do the push If n is not already in S, then the push needs to add n, and there is no room so we cannot do the push, nothing about S changes, and we return false If n is in S already, then we can move the n that is there to the top without changing the size of S so we do that, and return true So S.push(n) only fails (returns false) when S is maxed out, and n is not in S.

Operation push Various properties of a StackSet: This is true: if push(n) returns true then n is the top element This is true: if push(n) returns false then the StackSet is unchanged This is true: if push(n) returns false then n is not in the StackSet This is true: if push(n) returns true and n is in the StackSet before, then the size of the StackSet is unchanged And other properties let s look at some diagrams

StackSet push example after mySST.push(12.0) mySST mySST head head constructor function constructor function val 12.0 push, pop, etc. function push, pop, etc. function next size size 1 0 limit 3 limit 3 after mySST = New StackSet(3)

StackSet push example mySST head constructor function val val -17.3 12.0 push, pop, etc. function next next size 2 limit 3 after mySST.push(-17.3)

StackSet push example mySST head constructor function val val val 6.518 12.0 -17.3 push, pop, etc. function next next next size 3 limit 3 after mySST.push(6.518)

StackSet push example mySST head constructor function val val val 12.0 -17.3 6.518 push, pop, etc. function next next next size 3 limit 3 after mySST.push(12.0)

StackSet push example mySST head constructor function val val val 6.518 -17.3 12.0 push, pop, etc. function next next next size 3 limit 3 after mySST.push(6.518)

StackSet push example mySST.isFull() gives true mySST mySST.peek() gives 6.518 head constructor function val val val 6.518 -17.3 12.0 push, pop, etc. function next next next size 3 after mySST.push(101.5) no change, it fails due to limit, and 101.5 not in mySST to be moved limit 3

StackSet pop example mySST.isEmpty() gives false mySST.isFull() gives false myLS mySST.contains(27.7) gives false mySST.contains(-17.3) gives true nodes mySST.peek() gives 12.0 constructor function data data 12.0 -17.3 mySST.size() gives 2 push, pop, etc. function next next mySST.limit() gives 3 numElts 2 after mySST.pop() limit 3

Back to pointers in Java code An arrow in box-arrow diagram, I call a pointer In Java this is a reference to an object ( or just an object ) public class Node { double val; Node nx ; // link Node pv ; // link . . . } val 12.5 23.74 val nx nx pv pv 0 1

Side note this is a doubly linked list In this code, we have a data cell with 2 links 2 pointers nx points to the next cell in the list pv points to the previous cell linked cells A doubly linked list lets you go forwards and backwards in a list or sequence of This is useful in many list applications, but we do not need it for the stack-like StackSet implementation public class Node { double val; Node nx ; // link Node pv ; // link . . . } val 12.5 23.74 val nx nx So our Assignment 1 code has nodes with just a next link pv pv 0 1

Walking down a linked list of cells Need some variables to hold obj refs (hold pointers) head (type Node) never changes, always references the list (first cell in list) curr (type Node) where we currently are as we walk down the cells curr = head; while (curr !== sentinel) { count++; curr = curr.nx; } count = 0; curr So count is 5 head Sentinel, or null val val val 23.74 val 7.31 3.61 val 0.454 241.2 nx nx nx nx nx pv pv pv pv pv Sentinel, or null 0 4 2 1 3

Adding a new cell curr = head; ct = 0; while (curr !== sentinel) { if (ct < 2) { curr=curr.nx; ct++; } else { break; } } // here, curr is loc of new cell insert ( 6.8, 2 ) curr head val val val 23.74 val 7.31 val 3.61 0.454 241.2 Sentinel, or null nx nx nx nx nx pv pv pv pv pv 0 1 3 2 Sentinel, or null 4 5 4 3 Node c = new Node(6.8); val 6.8 c.pv = curr.pv; curr.pv = c; c.pv.nx = c; c.nx = curr; nx pv 2 c