Linked Bag Implementation Overview

Linked Bag Implementation

Outline Pros and cons of ArrayBag Links and linked structures Class Node private class Node LinkedBag Methods Pros and cons of LinkedBag

Pros and Cons of ArrayList Pros: quick, direct access to known positions fast add/remove at end of array Cons fixed size or cost of copying entries slower remove in front/middle wasted space

Alternative to Arrays Each entry remembers who s next bag itself remembers who s first Known as a chain Fencer Architect Business Man (no one) Golfer Doctor

Adding to the Chain New guy remembers who was first bag remembers the new person Fencer Doctor Architect Business Man (no one) Golfer Doctor Professor

Removing from the Chain From front is easy reverse adding at front Fencer Doctor Architect Business Man (no one) Golfer Doctor Professor

Removing from the Chain From middle is harder find person remembering guy leaving have them remember the one after the person leaving Fencer Architect Business Man Fencer (no one) Golfer Doctor

Chains: Why? How? Don t need a whole array of spaces one extra space for each object in the bag to remember who comes next But the objects don t have extra space for remembering the following object! would require an extra instance variable can t add an extra instance variable to a String (e.g.) we need some help a little helper class

Minions Minions remember a person and a minion Gru remembers which minion comes first

Class Node (Our Minion) Remembers one object and one node must be able to remember any sort of object generic class next node remembers same kind of thing public class Node<T> { private T data; private Node<T> next; } some data a Node & & another Node & & more data

Class LinkedBag (Our Gru) Remembers which Node comes first first node remembers the kind of thing that s in the bag (same parameter) public class LinkedBag<T> { private Node<T> first; private int numInBag; } a LinkedBag & 4 a Node & & some data

LinkedBag Constructor Bag starts empty no first entry, zero entries public LinkedBag() { first = null; numInBag = 0; }

Linked Bag Bag with doctor, architect, golfer and fencer & 4 & & & & & & & /

Following the Chain curNode keeps track of where we are start at first minion/node (curNode = first) go to next minion/node (curNode = curNode.next) stop when curNode becomes null & 4 & & & & & & & / curNode & /

Following the Chain Node<T> curNode = first; while (curNode != null) { /* do something with curNode.data, then */ curNode = curNode.next; } & 4 & & & & & & & / curNode & /

Minions at Risk Clients should not be able to access Nodes could accidentally/maliciously change values curNode.next = curNode; & 4 & & & & & & & / curNode & Fencer has been lost. Now have 2 (or infinitely many) golfers.

Private Classes One class can actually belong to another Node can belong to LinkedBag Can be public or private private only owner class can use it owner gets full access either way! Declare owned class inside owner class public class Owner { private class Owned {

Owned Generic Classes Don t need <T> on owned class owner is already <T>, so owned is, too! public class LinkedNode<T> { private class Node { private T data; private Node next; } private Node first; private int numInBag; } // same type as bag s base type

Node Constructors Will need to create new nodes data filled in, next maybe filled in (null if not) code goes inside Node class inside LinkedBag public Node(T value, Node n) { data = value; next = n; } public Node(T value) { this(value, null); }

Add an Entry / 0 First First add: & & / 0 0 1 & / Second (and later) add: Later First & 1 1 2 & & & / & &

add(T) Method LinkedBag method (not a Node method!) create Node to remember new data value its next field is whatever was first even if there was nothing in the bag (first == null) public boolean add(T newData) { first = new Node(newData, first); ++numInBag; return true; }

Core Methods Have constructor and add method just about ready to start testing Need toString method for ArrayBag used Arrays.toString won t work here (no array!) How about we write toArray method first then can use Arrays.toString

toArray() Method Need to make a new array & copy values loop thru the array and follow minion trail public T[] toArray() { T[] result = (T[]) new Object[numInBag]; Node currentNode = first; for (int i = 0; i < numInBag; ++i) { result[i] = currentNode.data; currentNode = currentNode.next; } return result; }

Now toString No need to copy the array it s not our instance variable it s already the correct length @Override public String toString() { return Arrays.toString(toArray()); }

Testing Core Methods Tests for LinkedBag are exactly the same as for ArrayBag same methods; same behaviour expected replace new ArrayBag with new LinkedBag should get same results

getCurrentSize() Method Return the number of entries public int getCurrentSize() { return numInBag; } we could count the number of entries what would that code look like? but why bother? & 4

isEmpty() Method Two versions numInBag is zero: public boolean isEmpty() { return numInBag == 0; } first is null: public boolean isEmpty() { return first == null; } / 0

frequencyOf(T) Method Loop thru Nodes counting those equals public int frequencyOf(T anEntry) { int count = 0; Node curNode = first; while (curNode != null) { if (Objects.equals(curNode.data, anEntry)) { ++count; } curNode = curNode.next; } return count; }

contains(T) Method Loop thru until find data or end of bag public boolean contains(T anEntry) { Node curNode = first; while (curNode != null) { if (Objects.equals(curNode.data, anEntry)) { return true; } curNode = curNode.next; } return false; }

remove() Method Reverse add method to remove first entry possible problem: nothing in bag public T remove() { if (first != null) { Node toDelete = first; first = toDelete.next; --numInBag; return toDelete.data; } throw new ; } toDelete & One Two & 1 1 4 3 & & & & & &

clear() Method Simple method that works for all Bags: keep removing until bag is empty public void clear() { while (!isEmpty()) { remove(); } }

remove(T) Considerations Remove node by updating links links to update in node before the one with data find the node before the node with the data but the data might not be there but the data might be in the first node actually, we already know how to do the first node hmm. & removing the Golfer & & & & / Node before Golfer needs to change link

remove(T) Clever Plan Find the node with the desired data Swap in the data from the first position Remove the first node using remove() & 4 3 & & & & & & & & / curNode &

remove(T) Method public boolean remove(T anEntry) { Node itsNode = findNode(anEntry); // private method if (itsNode != null) { itsNode.data = first.data; remove(); // updates numInBag return true; } return false; } what if the node with the data is the first node?

findNode(T) Method Returns the node with the wanted data returns null if the data wasn t found private Node findNode(T anEntry) { Node curNode = first; while (curNode != null) { if (curNode.data.equals(anEntry)) { return curNode; } curNode = curNode.next; } return null; }

Exercise Rewrite contains to use findNode

ArrayBag vs. LinkedBag Linked grow smoothly; Array in jumps Linked shrinks smoothly; Array doesn t can reprogram ArrayBag to shrink in jumps Small differences in: memory used (LinkedBag uses more in total) BUT ArrayBag needs a large chunk of memory LinkedBag can use plenty of small chunks traversal speed (LinkedBag slightly slower)

Which to Use? Depends on what you re doing! Biggest difference is smoothness LinkedBag grows smoothly ArrayBag grows in jumps Will the occasional delay for resizing cause any problems? e.g. for a video game, you need smooth otherwise get mini-freezes

What about Lists? Will pause-to-resize be a problem? Yes LinkedList Is most access at front or back? No ArrayList Will there be a lot of insertions/deletions Yes LinkedList No ArrayList These are rules of thumb; when in doubt, try it out!

Sets? Are duplicate entries required? Yes List (see above) Is the order of elements important? No HashSet Is it insertion order or sort order? insertion order LinkedHashSet sort order TreeSet

Questions