Tutorial 4 Lecturer: Ray Reiter Tutor: Andria Hunter ========== 990127 Wed@1pm (PA105) Topics: ------------------------------ - questions on A1 - code for a linked data structure Where we are in lectures - I've finished up through slide 119. Some instructors are quite far ahead, and a couple a bit behind. They'll keep you posted. My students seemed to really understand linked lists, better than last year. Probably because most have had 108. Info for you - The next tutorial after this one will be a midterm. (Already! You may want to remind your students that it's coming up.) It will be held in tutorial and day TAs will each supervise their own class. - We'll tell the students in lecture what to expect on the test. - We will post a solution to A0 within the week, after students with extensions are done. - The second online homework, on pointer basics, is a good one for the students to do. Please take a look at it yourself, and encourage students to work through it. The homework doesn't take long, and should help them firm up their understanding of fundamental concepts. It was very popular last year, and I've already had several students comment on how useful (and fun) it was. - The third online homework, on inserting into a linked list, is also ready. Encourage them to do that, too. Assignment 1 ------------------------------ - Take questions on the assnt. Note that it doesn't directly involve linked lists, although it does involve an in-depth understanding of object references. - You'll need to read the handout carefully, and to look closely at the starter code in order to prepare for these questions. More on code for a linked data structure ------------------------------ - The purpose of this week's tutorial is to increase students' comfort with linked structures. - Do one or both of the example(s) below. - Please get your class to develop the code with you. And as you develop it, go through careful traces of the code. Many students either don't know how, or are unwilling to trace code. and this is a particularly big handicap with linked structures. I'm planning on having them trace code on my midterm; other instructors may decide to do that, too. Linked List Code ---------------- - This week you will have them implement a ListOfInts as a linked list. (Don't worry, this is the last week dealing with Ints.) - The Node and ListOfInts class definition is at the end of this message. Deleting the 1st element of a linked list ----------------------------------------- - Very trivial. You could ask them to write it at their desks and then take it up. public void removeFirst () { theList = theList.nextOne; // No "free" required (or even expressible in Java). // If nothing refers to the old front node, it gets garbage collected. } Printing the contents of a linked list -------------------------------------- public void print () { Node current = theList; while (current != null) { System.out.println(current.data); current = current.next; } } Printing a linked list in reverse --------------------------------- - This one is much trickier. Print an existing linked list in reverse order, without using recursion or more than a const amount of extra memory. public void printReverse () { Node last = null; Node current; // print the one before last, and then move last back one node. // Continue until last gets to the front. while (last != theList) { current = theList; while (current.nextOne != last) { current = current.nextOne; } System.out.println(current.data); last = current; } } - This is, of course, not the way one would ever implement reverse printing, but it is a medium tricky example, and as a bonus it motivates recursion (which we will be getting into later). - This example could lead in to a fun discussion of o the time complexity of this method vs the obvious method for reverse-printing the contents of an _array_. Remember that students have seen nothing on big-oh yet. o more efficient ways to do reversePrint, and their time complexities. Faster methods include (1) using a doubly-linked list (2) using a stack, and (3) using recursion. Remember that the students are not yet familiar with recursion. Stacks have been briefly mentioned. Another reverse print --------------------- - I don't think anyone will run out of material, but if you do, here's another example you can work on. - Another crazy way to print a linked list in reverse order: go down the list reversing the pointers, then when you hit the end, return back printing the elements and restoring the pointers. See the May 93 final exam in the handbook for a solution in OOT. A complete program ------------------ - If you want to play around with the code, here's a running program. class Node { public int data; public Node nextOne; // Constructor public Node (int initialValue) { data = initialValue; nextOne = null; } } class ListOfInts { private Node theList; private int numElements; // Don't need a maxListSize; no limit other than memory limits. // Constructor public ListOfInts() { // Actually, the default constructor would do the same inits for us. theList = null; numElements = 0; } public void removeFirst () { theList = theList.nextOne; // If nothing refers to the old front node, it gets garbage collected. } public void print () { Node current = theList; while (current != null) { System.out.println(current.data); current = current.next; } } public void printReverse () { Node last = null; Node current; while (last != theList) { current = theList; while (current.nextOne != last) current = current.nextOne; System.out.println(current.data); last = current; } } public void addInt (int n) { Node temp = new Node(n); temp.nextOne = theList; theList = temp; numElements++; } public float average () { Node temp = theList; int sum = 0; while (temp != null) { // Or could still use this: for (int i=0; i