ࡱ> <>;  !bjbj 40hh  45 "bZ0yL05#R:##85# : Doubly Linked Lists Sometimes it is convenient to maintain references to both the next node and the previous node in a linked list. This is called a doubly linked list and is illustrated in Figure 12.4 of the text. File DoubleLinked.java contains definitions for a doubly linked list of integers. This class contains an inner class IntNode that holds information for a single node in the list (its value and references to the next and previous nodes). The DoubleLinked class also contains the following methods: _ public DoubleLinked()constructor; creates an empty list of integers _ public void addToFront(int val)takes an integer and puts it on the front of the list _ public void print()prints the elements in the list from first to last File DoubleLinkedTest.java contains a driver that allows you to experiment with these methods. Save both of these files to your directory, compile and run DoubleLinkedTest, and play around with it to see how it works. Then add the following methods to the DoubleLinked class. For each, add an option to the driver to test it. 1. public void addToEnd(int val)takes an integer and puts it on the end of the list 2. public void removeFirst()removes the first value from the list. If the list is empty, does nothing. 3. public void removeLast()removes the last element of the list. If the list is empty, does nothing. 4. public void remove(int oldVal)removes the first occurrence of oldVal in the list. // **************************************************************** // DoubleLinked.java // // A class using a doubly linked list to represent a list of integers. // // **************************************************************** public class DoubleLinked { private IntNode list; // -------------------------------------------------- // Constructor -- initializes list // -------------------------------------------------- public DoubleLinked() { list = null; } // -------------------------------------------------- // Prints the list elements // -------------------------------------------------- public void print() { for (IntNode temp = list; temp != null; temp = temp.next) System.out.println(temp.val); } // -------------------------------------------------- // Adds new element to front of list // -------------------------------------------------- public void addToFront(int val) { IntNode newNode = new IntNode(val); newNode.next = list; if (list != null) list.prev = newNode; list = newNode; } 258 Chapter 12: Collections //************************************************************* // An inner class that represents a list element. //************************************************************* private class IntNode { public int val; public IntNode next; public IntNode prev; public IntNode(int val) { this.val = val; this.next = null; this.prev = null; } } } // ************************************************************* // DoubleLinkedTest.java // // Driver to test DoubleLinked methods. // ************************************************************* import java.util.Scanner; public class DoubleLinkedTest { private static Scanner scan; private static DoubleLinked list = new DoubleLinked(); //---------------------------------------------------------------- // Creates a list, then repeatedly prints the menu and does what // the user asks until they quit. //---------------------------------------------------------------- public static void main(String[] args) { scan = new Scanner(System.in); printMenu(); int choice = scan.nextInt(); while (choice != 0) { dispatch(choice); printMenu(); choice = scan.nextInt(); } } //---------------------------------------- // Does what the menu item calls for. //---------------------------------------- public static void dispatch(int choice) { int newVal; switch(choice) { case 0: Chapter 12: Collections 259 System.out.println("Bye!"); break; case 1: //print System.out.println("** List elements **"); list.print(); break; case 2: //add to front System.out.println("Enter integer to add to front"); newVal = scan.nextInt(); list.addToFront(newVal); break; default: System.out.println("Sorry, invalid choice"); } } //---------------------------------------- // Prints the user's choices //---------------------------------------- public static void printMenu() { System.out.println("\n Menu "); System.out.println(" ===="); System.out.println("0: Quit"); System.out.println("1: Print list"); System.out.println("2: Add an integer to the front of the list"); System.out.print("\nEnter your choice: "); } } Recursive Processing of Linked Lists File IntList.java contains definitions for a linked list of integers (see previous exercise). The class contains an inner class IntNode, which holds information for a single node in the list (a node has a value and a reference to the next node) and the following IntList methods: _ public IntList()constructor; creates an empty list of integers _ public void addToFront(int val)takes an integer and puts it on the front of the list _ public void addToEnd(int val)takes an integer and puts it on the end of the list _ public void removeFirst()removes the first value from the list _ public void print()prints the elements in the list from first to last File IntListTest.java contains a driver that allows you to experiment with these methods. Save both of these files to your directory. If you have not already worked with these files in a previous exercise, compile and run IntListTest and play around with it to see how it works. Then add the following methods to the IntList class. For each, add an option in the driver to test the method. 1. public void printRec()prints the list from first to last using recursion. Hint: The basic idea is that you print the first item in the list then do a recursive call to print the rest of the list. This means you need to keep track of what hasn't been printed yet (the "rest" of the list). In particular, your recursive method needs to know where the first item is. Note that printRec() has no parameter so you need to use a helper method that does most of the work. It should have a parameter that lets it know where the part of the list to be printed starts. 2. public void printRecBackwards()prints the list from last to first using recursion. Hint: Printing backward recursively is just like printing forward recursively except you print the rest of the list before printing this element. Simple! L T  OVev4:p v ! !±£hR! hY 5CJOJQJ\^JaJhY CJOJQJ^JaJ hY 5CJOJQJ\^JaJhY CJOJQJ^JaJ hY 6CJOJQJ]^JaJhY CJOJQJ^JaJ hY 5CJ$OJQJ\^JaJ$" G c . Q JMRh d7$8$H$gdY hjwyQoq"$H]o$dz| d7$8$H$gdY | Kdg '^Gnp d7$8$H$gdY   6\%P^e| d7$8$H$gdY  "$Ol9{O)` d7$8$H$gdY `Ze` !gdY d7$8$H$gdY 21h:pR!/ =!"#$% j  666666666~~~~~~~~~666666>66666666666666666666666666666666666666666666666666hH6666666666666666666666666666666666666666666666666666666666666666662 0@P`p2( 0@P`p 0@P`p 0@P`p 0@P`p 0@P`p 0@P`p8XV~ OJ PJ QJ _HmH nH sH tH F`F R!NormaldCJ_HaJmH sH tH DA D Default Paragraph FontRiR 0 Table Normal4 l4a (k ( 0No List PK![Content_Types].xmlj0Eжr(΢Iw},-j4 wP-t#bΙ{UTU^hd}㨫)*1P' ^W0)T9<l#$yi};~@(Hu* Dנz/0ǰ $ X3aZ,D0j~3߶b~i>3\`?/[G\!-Rk.sԻ..a濭?PK!֧6 _rels/.relsj0 }Q%v/C/}(h"O = C?hv=Ʌ%[xp{۵_Pѣ<1H0ORBdJE4b$q_6LR7`0̞O,En7Lib/SeеPK!kytheme/theme/themeManager.xml M @}w7c(EbˮCAǠҟ7՛K Y, e.|,H,lxɴIsQ}#Ր ֵ+!,^$j=GW)E+& 8PK!wXtheme/theme/theme1.xmlYM5#M6fM6BvIztfw=67q7J\ʯY("/ڞIƛI7T TUxïW !)OZ^RC$y@>T8 0 iyS"+;wo}"qˋJ֤X^)Iۘ+xZ z\1M<OPvr]zgbY`Fȩ01ky ''CrOyaC˫?omΈZB[뙿.#֍LfBތ0vnuV"zoy@qwҨ]|mAvtL >f}w7ntd|ocYw1-u@{ 2l J f٥EyZr2h4%cCwp<kx˅%- I_TR 1/=A?YF>N"Ջ>''߾xe9^鯿|Qǿ?}a |WQ>19A<ÌW\H3aib7 %NR¿"}cYG6q=x[@(^uDbhkQ6^e<$ap1)1>.$cx'" ' $! oPO}%+t6.ґMs}C\e6Co6geVc UYC7^2Cïc)9 J )hn k:VilHQ"ru"eM"Cy)We>w+DCp4ܷ)q}~7ECGy/c 1M^Վ~ls14<*ɬ7žTV g2٦"o~Ó@/nWp rq֖7UlD3,YSs-ՙHVL)Uز--TJ?%f",ngZ]ÅH^BEIQ'`И;.ܮ Ag7KsepS4D"A03Q&$2Y)(,Z`cHc8  0 !h|` !8@0(  B S  ?LS U_`cdg=EFIJMgjkqYe#FOQc     $ + , 3 : A B E H T o x { r y y  6 B N Z h l %7PZ|&9K{OV7ABEFI>I`h(9 IOcg17TZRXjnQd  : B ] _ d k |  ' . G M p t %8P[^cei|'9L{+1Z^ei`i" 3333333333333333333333333333333333333333333333333333333333333333333333333333333333333 6p  Y RR!d2}U9N9  @ h@Unknown G* Times New Roman5Symbol3. * ArialMTimesNewRoman,BoldCTimesNewRomanQTimesNewRoman,ItalicO1 CourierCourier New=Times,Bold3Times7.{ @CalibriA BCambria Math"qh͚Ɔ͚ƆN -N -!202HX$PY 0! xxJolanta SoltisJolanta SoltisOh+'0|  8 D P\dltJolanta Soltis Normal.dotmJolanta Soltis2Microsoft Office Word@G@@N՜.+,0 hp  NJIT-   Title  !"#$%&'()*,-./012456789:=Root Entry F\?1Table#WordDocument40SummaryInformation(+DocumentSummaryInformation83CompObjy  F'Microsoft Office Word 97-2003 Document MSWordDocWord.Document.89q