11. Dynamic Data Structures

What We Will Cover Announcements Illuminations 11.1: Dynamic Data Structures 11.1.1: About Dynamic Data Structures 11.1.2: Dynamic Memory Allocation 11.1.3: Generic Data 11.1.4: Self-referential Classes Exercise 11.1 11.2: Linked Lists 11.2.1: Arrays vs. Linked Lists 11.2.2: Designing a Linked List Class 11.2.3: Initial List Class 11.2.4: Moving Around the List 11.2.5: Inserting a Node 11.2.6: Deleting a Node 11.2.7: Checking the List Exercise 11.2 11.3: Iterators 11.3.1: About Iterators 11.3.2: Linked-List With Iterator 11.3.3: List Iterator Class 11.3.4: Example Using Iterators Exercise 11.3 Wrap Up Events Due By Next Meeting: Nothing Illuminations Questions on Completed Assignments? A10: File Reader (11/26/03) ^ top 11.1: Dynamic Data Structures Objectives At the end of the lesson the student will be able to: Describe dynamic data structures Use generic data in a class ^ top 11.1.1: About Dynamic Data Structures Data structures are a way to organize data in a program Arrays are one such data structure we have covered However, once an array is defined, you cannot change it's size One could define a new array and copy contents from one array to another Another solution is to use a dynamic data structure Dynamic data structures can grow and shrink while the program is running Several useful types of dynamic data structures including: Linked lists Stacks Queues Trees We will examine linked lists today Textbook has descriptions of the other data structures National Institute of Standards and Technology (NIST) also contains a more comprehensive Dictionary of Algorithms and Data Structures ^ top 11.1.2: Dynamic Memory Allocation Dynamic memory allocation allows us to obtain more memory at execution time When we Instantiate objects we are getting memory from the free memory store, a.k.a. heap Eventually, a program can use up all the available memory Need some way to release memory used by objects when no longer needed Java has automatic "garbage collection" that releases memory no longer in use Dynamic data structures make use of dynamic memory allocation to manage data Heaps in Java Can get the current size of the heap in Java long heapSize = Runtime.getRuntime().totalMemory(); Can also get the maximum size of the heap in bytes Heap cannot grow beyond this size long heapMaxSize = Runtime.getRuntime().maxMemory(); Can also get the free memory within the heap in bytes long heapFreeSize = Runtime.getRuntime().freeMemory(); Size sill decrease after creating new objects Size will increase after garbage collection System.gc(); ^ top 11.1.3: Generic Data One of the problems of designing data structures is how to handle all the data types In Java, we meet this goal by storing data as a class of type Object All classes in Java are extended from Object Thus, can use an Object reference to store data for all class types To store primitive types, we must use a wrapper class Java has wrapper classes for all the primitive types including Character Double Integer What code would we use to store the int value 5 as an Object? ^ top 11.1.4: Self-referential Classes The secret to dynamic data structures is self-referential classes Self-referential class means that a class has a reference to an object of that same class Objects contain instance variables referring to objects of same class One common self-referential class is the node: class Node { private Object data; private Node nextNode; // constructors and methods ... } Member nextNode is a link nextNode "links" a Node object to another Node object Last node is set to null to mark end of list Show this graphically as: First box of each node is the data we store Second box is a memory reference (i.e. pointer) to the next structure The arrow is the "pointer" to the next memory location Box with a slash through it means there is no nextNode An alternate format of showing the end of the list is: ^ top Exercise 11.1 Take one minute to prepare an answer to the following question: Given the class Node defined below, what is the code to set a Node data value to the character 'A'? class Node { private Object data; private Node nextNode; Node(Object object, Node node) { data = object; nextNode = node; } } What would be a good value to use to indicate there is no next node? ^ top 11.2: Linked Lists Objectives At the end of the lesson the student will be able to: Use nodes in a linked list Add nodes to a linked list Delete nodes from a linked list ^ top 11.2.1: Arrays vs. Linked Lists Arrays as Lists Arrays are lists of data, all of the same type Convenient data structure, but has some inherent problems Size is fixed when declared Adding a value when the array is full requires creating a new array and copying all the elements Insertion of a new value in the middle of the array means copy about half the elements Inefficient storage: can use a partially full array, but space has been allocated for the full size Linked Lists Linked list is a linear collection of self-referential classes (nodes) Connected by reference links Has many advantages over arrays Size is not fixed -- list size increases automatically Efficient storage as a list uses just the space it needs Nodes can be inserted and deleted anywhere in the list Comparison of Arrays and Linked Lists Arrays Linked List Bad: Size is fixed when declared Inefficient storage when only partially full Inserting a value in the middle requires copy about half of the elements Good: Size is not fixed -- list size increases automatically Efficient storage as a list uses just the space it needs Insertion does not require copying any elements Good: More efficient (faster) execution when the index is known No overhead for storing node pointers Bad: Less efficient (slower) execution when the index is known Must store node pointers ^ top 11.2.2: Designing a Linked List Class Want a general list class we can use for many programs What state (variables) and behavior (methods) do we need for our class? Linked List Design Review our diagram of a linked list Will need three items: List node class to construct the list Reference to the start of the list Way to specify which node to operate upon Way to insert and remove data ListNode Class Need two data variables in each list node Data variable of type Object to store the data Data variable to point to the next node One possible implementation is: public class ListNode { private Object data; private ListNode nextNode; public Object getData() { return data;} public ListNode getNextNode() { return nextNode;} } Want our list nodes to be contained within our list class One good way to accomplish this is to use an inner class for the list node Start of List We need a reference to the start of the list ListNode first; Moving Around Need a way to specify where to operate in the list Movable pointer to any node on the list Can specify this using a ListNode variable named current ListNode current; Also convenient to have a ListNode reference to the previous node If current is pointing to the first element, previous will be null ListNode previous; Will need methods to get and set the current node Also a method to advance to the next location on the list Still another method to test if there is another item on the list //get the head of the list ListNode getFirst() //set current to the first item void moveFirst() //advance current to the next item and return it Object next() //return true if current is not the last item boolean hasNext() Inserting and Removing Data Need a way to access and modify data in a node //return the current item Object getData() //insert after the item referred to by current void insert(Object value) //remove current item and advance current to next void remove() ^ top 11.2.3: Initial List Class Putting all the requirements together, we stub out our design import java.util.*; public class List1 { private ListNode first, current, previous; //return the current item Object getData() { return null;} //insert after the item referred to by current void insert(Object value) { } //remove current item and advance current to next void remove() { } //get the head of the list ListNode getFirst() { return null;} //set current to the first item void moveFirst() { } //advance current to the next item and return it Object next() { return null;} //return true if current is not the last item boolean hasNext() { return false;} public class ListNode { private Object data; private ListNode nextNode; public Object getData() { return data;} public ListNode getNextNode() { return nextNode;} } //for testing public static void main(String[] args) { } } Will work on implementing the required methods ^ top 11.2.4: Moving Around the List Implement the methods to move around the list Accessor for the first node is easy ListNode getFirst() { return first; } To move the current pointer to the head of the list void moveFirst() { previous = current = null; } Advancing current to the next item and returning it Object next() { previous = current; if (current == null) current = first; else current = current.nextNode; if (current == null) return null; return current.data; } Also nice to know if current is the last item or not boolean hasNext() { if (current == null) return first != null; else return current.nextNode != null; } ^ top 11.2.5: Inserting a Node To add a node in the list takes two steps Create a new ListNode with our data Insert the new ListNode after the current node Several conditions to consider List is empty At beginning of list At end of list Elsewhere in the list Can collapse two of the conditions to make three cases current points to an element on the list current is not pointing to an element, but the list is not empty the list is empty The last case is the easiest to implement void insert(Object value) { previous = current; if (current != null) { ListNode temp = current.nextNode; current.nextNode = new ListNode(); current.nextNode.data = value; current = current.nextNode; current.nextNode = temp; } else if (first != null) { current = new ListNode(); current.data = value; current.nextNode = first; first = current; } else { /* list is empty */ first = current = new ListNode(); current.data = value; } } ^ top 11.2.6: Deleting a Node To remove a node from the first position in the list, we have several cases If the list is empty, we do nothing If the current pointer is off the list, we do nothing If we are at the beginning of the list, we set first to the second node Otherwise, we set current.nextNode to the following node void remove() { if (first == null) return; if (current == null) return; if (current == first) first = current = current.nextNode; else current = previous.nextNode = current.nextNode; } ^ top 11.2.7: Checking the List Need some way to test our List Can insert several elements and try the various methods To display the list, we use the following algorithm: Start at beginning of list Display the data of the first ListNode Move to next node in the list Repeat until we see null as the value of nextNode Write this method with a while-loop list.moveFirst(); while (list.hasNext()) System.out.print(list.next() + " "); Putting it all together: import java.util.*; public class List2 { private ListNode first, current, previous; //return the current item Object getData() { return current.data; } //insert after the item referred to by current void insert(Object value) { previous = current; if (current != null) { ListNode temp = current.nextNode; current.nextNode = new ListNode(); current.nextNode.data = value; current = current.nextNode; current.nextNode = temp; } else if (first != null) { current = new ListNode(); current.data = value; current.nextNode = first; first = current; } else { /* list is empty */ first = current = new ListNode(); current.data = value; } } //remove current item and advance current to next void remove() { if (first == null) return; if (current == null) return; if (current == first) first = current = current.nextNode; else current = previous.nextNode = current.nextNode; } //get the head of the list ListNode getFirst() { return first; } //set current to the first item void moveFirst() { previous = current = null; } //advance current to the next item and return it Object next() { previous = current; if (current == null) current = first; else current = current.nextNode; return current.data; } //return true if current is not the last item boolean hasNext() { if (current == null) return first != null; else return current.nextNode != null; } public class ListNode { private Object data; private ListNode nextNode; public Object getData() { return data;} public ListNode getNextNode() { return nextNode;} } public static void main(String[] args) { List list = new List(); for (int i = 0; i < 5; i++) list.insert(new Integer(i)); list.moveFirst(); while (list.hasNext()) System.out.print(list.next() + " "); System.out.println(); list.moveFirst(); list.next(); //1 list.insert(new Integer(99)); list.next(); //2 list.remove(); list.moveFirst(); while (list.hasNext()) System.out.print(list.next() + " "); System.out.println(); } } How would we implement a toString method for the List class? We could also implement toString recursively ^ top 11.3: Iterators Objectives At the end of the lesson the student will be able to: Discuss the uses of an iterator Use iterators to access the elements of a linked list ^ top 11.3.1: About Iterators Iterator: A construct that allows you to move and access items over a collection of objects (from iterate ). An array is a collection of objects or primitive values Iterator for an array is an integer variable For example, could use int i as an iterator in a for loop int[] a = {12, 25, -3, 7, 14}; for (int i = 0, i < a.length; i++} System.out.print(a[i] + " " ); The iterator itself is incremented with the increment operator, e.g. i++ Two requirements for an interator: Some way to move the iterator and get the next value Some way to determine if you have moved over the entire collection One way to use an iterator is to build it into a class such as a linked list ^ top 11.3.2: Linked List With Iterator In a linked list, a reference to the node can be used as an iterator To define a linked list class with an iterator, we use three variables first always refers to the first ListNode, or null if empty current can refer to any element; null if off the list previous refers to the item before current (convenience) Note that our linked list implementation included an internal iterator What was the name of the variable that we used as an iterator? With out linked list, we can iterate over the entire list list.moveFirst(); while (list.hasNext()) System.out.println(list.next().toString()) We can also add and remove elements at any location in the list ^ top 11.3.3: List Iterator Class Can also use an external iterator (a separate class) Building a single iterator into a class only allows use of one iterator at a time Using a separate iterator class, can have as many iterators as needed Need at least two methods for an iterator: next() and hasNext() Java has an Iterator interface we could use Iterator interface requires implementing three methods However, remove method not really required Method can simply throw an UnsupportedOperationException Using Iterator means we do not need to use a type-specific iterator Many loops using iterators now take on the form: Iterator it = myvar.iterator(); while (it.hasNext()) { MyType localVariable = (MyType)i.next(); // do something with localVariable } Usual way to create an iterator is to ask the class for one The typical method in Java is called iterator() We can add a method to return an iterator method from our class List Iterator iterator() { return new ListIter(this); } Using the following class we can have as many iterators as we want import java.util.*; class ListIter implements Iterator { List.ListNode current; List list; ListIter(List aList) { list = aList; current = null; } Object current() { if (current == null) return null; return current.getData(); } public boolean hasNext() { if (current != null) return current.getNextNode() != null; else return list.getFirst() != null; } public Object next() { if (current == null) current = list.getFirst(); else current = current.getNextNode(); if (current == null) throw new NoSuchElementException( "No more elements"); return current.getData(); } public void remove() { throw new UnsupportedOperationException(); } } Notes on the Code List.ListNode current; List list; Keep our own current position with current Also keep the reference to the List we are working with Testing the External Iterator Add the following code to the end of our main method to test the iterator: Iterator it = list.iterator(); while (it.hasNext()) System.out.print(it.next() + " "); System.out.println("\n\nTest end of list"); try { System.out.print(it.next() + " "); } catch(NoSuchElementException e) { System.out.println(e.getMessage()); } ^ top 11.3.4: Example Using Iterators Can use iterators to append one list to another Add all the elements of one list to the end of another list One solution is to use two iterators First iterator moves to end of the list Second iterator used to copy from beginning of second list void append(List list) { Iterator itThis = this.iterator(); Iterator itOther = list.iterator(); //position at end of list while (itThis.hasNext()) itThis.next(); while (itOther.hasNext()) itThis = insert(itThis, itOther.next()); } For this method to work, need a new method in class List Iterator insert(Iterator it, Object value) The method inserts a new element with the field data set to value Following the element referred to by the iterator it Method should return a new Iterator, positioned at the element just inserted Method insert is left as an exercise for the student (see next assignment) Casting the Iterator Note that our iterator method returns a generic Iterator Need to cast the generic Iterator to our type of iterator Iterator it; ... ListIter lit = (ListIter) it; ^ top Exercise 11.3 Take one minute to prepare an answer the following topic: Diagram the insert operation for inserting a new node after the current node. ^ top Wrap Up Due Next Class: Nothing ^ top Home | WebCT | Announcements | Schedule | Expectations | Syllabus Help | FAQ's | HowTo's | Links Last Updated: November 26 2003 @17:41:37