Linked Lists From Scratch: Implementing Singly Linked Nodes in Java
Added on 2019-09-30
6 Pages3352 Words188 Views
Project Two: Linked Lists From ScratchHigh level languages and data structures enable us to allocate our precious brain cycles to thinkabout the actual problem that we need to solve instead of dealing with the nitty gritty details ofwhat is really going on. Let the computer and the virtual machine take care of all that grunt work!The normal way to represent linked lists and other data structures of individual nodes pointing toone another is to define two separate classes; one whose objects represent the list as a whole, andanother (typically defined as an inner class of the previous class) whose objects represent theindividual nodes that contain references to other nodes. This approach has several upsides,especially when combined with object-oriented programming techniques of polymorphism andgenerics. As for all objects in Java, garbage collection will then automatically release the objects thathave become unreachable, so we don't need to worry about doing that in our code.However, such high level representation has one giant downside of its overhead of memoryconsumption. Consider a simple linked list whose keys are integers. Both the dynamic binding ofmethod calls and the implementation of memory management and garbage collection in the JavaVirtual Machine necessitate every object to have constant bookkeeping memory overhead inaddition to the space actually needed to store the data in the object fields. This bookkeeping cost isseparate for each individual object. This makes it far worse to store million individual node objectscompared to storing one array object (with the array object bookkeeping data stored only once)that contains the same data payload as those nodes. These days our computers and JVM processes have such an embarrassment of riches of heapmemory available compared to the size of the problem that the above is not really an issue forrealistic problem sizes. But suppose that your linked lists grew up to contain, say, a hundred millionelements, constantly being allocated and garbage collected. It would make a pretty huge differencewhether that list structure uses 800 megabytes or about 2.5 gigabytes of the process RAM.In this second programming project, we use Java to take a time travel journey back to the sixtiesand forget all the high level object oriented stuff. Instead of storing the nodes of a list as separateobjects, we use arrays to simulate the memory in which these node objects are stored. For example,The Art of Computer Programming still presents all its algorithms and data structures in such low-level way..The IntList ClassThe instructors provide a class intlist.java that implements a mechanism to manage chains of singlylinked nodes that contain int keys. There are no header nodes to represent the entire list, but alloperations consists of management of chains. You may not modify this class in any way in thisproject, but you should still read through its code carefully to get an understanding of what is goingon. The integer arrays key and next are used to store the key and the successor of each node.
These two arrays essentially simulate the random access memory in which these nodes are storedwith zero additional overhead. Therefore each node is identified by its integer index to these arrays,instead of an actual memory address stored in a reference variable.To initialize the Intlist class and actually allocate the memory for the arrays used to store thenodes, the user code must first call the method IntList.initialize(m) with the maximumnumber of nodes as the parameter m. (This call is made by the automated tester at the startup, soyour code does not need to worry about that. But just in case that somebody other than theinstructor will ever use this class as part of their own project that needs lots of little chains...) The relevant publicstatic methods of IntList that your code will have to call are getKey,getNext, setNext, allocate and release. None of your methods should ever need to call themethod setKey, but this method is provided here again in case that somebody wants to useIntList as part of some real world project. The following table shows how to convert theordinary linked list operations on separate Node objects into the IntList method calls used inthis project:OperationNode objects, usual wayBut in this project...Declare a variable n used to refer to one nodeNode n;int n;Create a new noden = new Node(k);n = IntList.allocate(k);Get key in noden.keyIntList.getKey(n)Assign key k into noden.key = k;IntList.setKey(n, k);Get successor of noden.nextIntList.getNext(n)Assign successor m to noden.next = m;IntList.setNext(n, m);Check if node existsn != nulln != 0Release an unused node to make it available for future node allocations(The Java garbage collection takes care of that for you, and you don't do anything)IntList.release(n);Note that in this representation, only individual nodes exist (once again, these nodes don't reallyfinger-quotes "exist" as actual Java objects, but are simulated inside two ordinary integer arrays),and there is no separate data type whose objects would represent header nodes to represent anentire list as a whole. Therefore, the individual node at the head of some chain simultaneouslystands for the entire chain hanging from that node. Methods that operate on entire lists receive theinteger index of this head node as parameter.
Unlike the Java object heap with its additional bookkeeping data per object, this representation ofsingly linked chains of nodes does not allow for automatic garbage collection of nodes that havebecome unreachable to make their perfectly good memory bytes available for later nodeallocations. Therefore, once your program logic knows that some node n is no longer needed, itshould call IntList.release(n) to release the entire chain of nodes starting from n. (Torelease only that one node instead of the entire chain, you need to first callIntList.setNext(n, 0). Make sure to take the index of the first node of the rest of the chainfor safekeeping to avoid the rest of that chain becoming an unreachable memory leak!)For convenience, the IntList class already defines a static method toString(int n) toconvert the chain starting from node n into a human-readable string representation. You shouldcarefully read through this method until you understand how it works, followed by similar study ofthe two other educational example methods removeFirst(int n, int k) andreverse(int n) also operating on chains, to serve as inspirational examples for the methodsthat you need to write in this project. You can run the main method of IntList to see a shortdemo of these methods in action.The IntList class keeps internally track of which nodes have already been allocated and whichare still available for future allocations. (The nodes that are still available are organized in a singlechain of free nodes to make both node allocation and release work in O(1) time.) The IntListclass also internally enforces memory safety so that once some node has been released, anyattempt to read or modify its key or successor through the public interface of IntList will causean IllegalStateException being thrown.Automated TesterThe instructors provide an automated tester class IntListMethodsTest.java that is used tocheck and grade your project. Used on the command line, it has the formatjava IntListMethodsTest SEED ROUNDS SIZE VERBOSEwhere SEED is the seed to initialize the pseudorandom number generator that produces the testcases, ROUNDS is the number of tests to run, SIZE is the number of elements in the test lists, andVERBOSE determines whether the tester should print out the intermediate results for yourdebugging purposes. Each test case consists of an array of integers that is first converted into a list.Your code, using the methods defined below, will first release all the nodes whose key is divisibleby a randomly chosen k between 2 and 7, and then sort the nodes that remain. An example run forfive rounds with twenty elements each might look like the following:matryximac:Java 609 mycomputern$ java IntListMethodsTest 777 5 20 trueOriginal: [12, 19, -18, 2, 13, -10, -13, 11, -6, -4, 3, -4, -11, 13, 20, 5, -20, 1, 0,-9]After removeIf(3): [19, 2, 13, -10, -13, 11, -4, -4, -11, 13, 20, 5, -20, 1]
End of preview
Want to access all the pages? Upload your documents or become a member.
Related Documents
Implementing Linked List in C++: Efficient Data Structure for Storing and Manipulating Elementslg...
|3
|282
|146
Network Optimisation using Graph Theory | Deskliblg...
|16
|1379
|79