Outline Notes.docx - Randomly Philled



CIS 55 Data StructuresProgramming Assignment 1In this assignment, you will use a modified Node structure to create a “Circular Doubly Linked List” data structure. The Node structure is defined as follows (we will use integers for data elements):public class Node{public int data;public Node next;public Node previous;}The Circular Linked List class definition is as follows:public class CircularLinkedList{public int currentSize;public Node current;}This design modifies the standard linked list. In the standard that we discussed in class, there is a head node that represents the first node in the list and each node contains a reference to the next node in the list until the chain of nodes reach null. In this Circular Doubly Linked List (CDLL), each node has a reference to a next and previous node. When new Node elements are added to the CDLL, the structure looks like a standard linked list with the last node’s next pointer pointing to the first. In this way, no “next” pointers of every Node in the CDLL are ever pointing to null.Since this is also a doubly linked list, the “previous” pointers of each Node are pointing to the Node behind it in the CDLL. Also, since this is a CDLL, the first Node’s previous pointer should also be pointing to the last Node and no “previous” pointers of every Node are ever pointing to null.For example, if a CDLL has elements “5”, “3” and “4” and “current” is pointing to “3”, the CDLL should look like:Key observations with this structure:The current node in the CDLL is always pointing to an existing node. If current is null, the CDLL should be emptyAll Nodes’ next and previous pointers are pointing to an existing nodeTraversing all elements means starting at the current node and going in either direction until you come back to the current nodePart 1) Complete the following functions for the CDLL:public CircularDoublyLinkedList()public void insertBeforeCurrent(int n)public void insertAfterCurrent(int n)public Node search(int n)public boolean update(int o, int n)public boolean delete(int n)public void printSize()public void printCurrent()public void printForward()public void printReverse()The requirements for each function are as follows:CircularDoublyLinkedList():This function is the default constructor for the CDLL and creates an empty list of size 0insertBeforeCurrent(int n):This creates a new node and inserts it “behind” the current node. If the list is empty, the new node’s next and previous pointers point to itself. If the list has at least 1 element, the new node is placed “behind” current while keeping the CDLL structure intact. When complete, the new node inserted is the new “current” nodeinsertAfterCurrent(int n):This creates a new node and inserts it “after” the current node. If the list is empty, the new node’s next and previous pointers point to itself. If the list has at least 1 element, the new node is placed “after” current while keeping the CDLL structure intact. When complete, the new node inserted is the new “current” nodesearch(int n):This searches the CDLL for a Node where its data property matches the given n. If a match is found, the Node is returned and the “current” Node in the CDLL is now this Node. If a match is not found, the function returns null and the “current” Node should be the same as when the function startedupdate(int o, int n):This searches the CDLL for a Node where its data property matches the given o. If a match is found, the Node’s data element is updated to the given n and the function returns true. The “current” Node in the CDLL is now this Node. If a match is not found, the function returns false and the “current” Node should be the same as when the function starteddelete(int n):This searches the CDLL for a Node where its data property matches the given n. If a match is found, the Node’s is removed from the CDLL while keeping the structure intact and the “current” Node is the Node that is “after” the Node that was removed. The function returns true. If a match is not found, the function returns false and the “current” Node should be the same as when the function startedprint functions:Size: displays the number of elements in the CDLLCurrent: displays the data value of the current element in the CDLL. If the list is empty, it prints “Empty List”Forward: displays all Node data values starting from current and traversing each element in “next” order. The “current” Node should be the same when the function completes. If the list is empty, it prints “Empty List”Reverse: displays all Node data values starting from current and traversing each element in “previous” order. The “current” Node should be the same when the function completes. If the list is empty, it prints “Empty List”Part 2) Write a main test program that allows the user to interactively test all these functions. The user must be able to insert, change, delete and search elements at any time and display the CDLL using any of the four print functions required. The demo of the program will be such that I will be testing to make sure everything works to my satisfaction.When developing and testing this project, remember every function (except the constructor) should be dealing with 3 scenarios:Empty listsLists with only 1 NodeLists with more than 1 NodeExamples of expected results are at the end of this documentSome things to also consider with this work that will help you with your studies are below. You do not need to complete these for the programming assignment, but practicing these may help with your preparation for the final exam at the end of the semester:What is the Big-O performance category in the worst case of the insert*, search, update and delete functions using compare operationsHow does this function compare to the single standard linked list version (compare Big-Os for insert, update, search and delete)What are the advantages/disadvantages to using this data structure?Based on all this, is the increased amount of code worth doing over single standard linked lists? (If your answer is “it depends”, then what does it depend on?)Program notes:The code samples above are in Java. You are welcome to use any other programming language as long as the node and circular doubly linked list structure is the same and you create all functions requiredAssume memory is available and data entry from the user is correct. The focus is on the data structure and not on user entry data handlingThe program should support duplicate data values and the code should not need to be any different because of it. I may or may not test for duplicate valuesGroup work: I recommend working on your own, but you are welcome to work in pairs. If you work in pairs, put both names on the work you submit. Working in groups of 3 or more is not allowed. I also recommend that both team members understand the details of all code developed.As such, please avoid submitting work that is exactly the same or eerily similar across individuals and teams. If 2 individuals are sharing code, work together as a team instead. I also encourage collaboration so please do share ideas and such across individuals and teams. I understand function code will be similar across students, but when I look at the code during the demo, know that I've done enough teaching to spot the difference between work ideas that are shared between students and work that is copied.Ask questions and draw pictures. Get a head start and submit work soon. I recommend completing as much of the assignment as you can, if not all, by the 2nd programming project which will likely be assigned around that time we get to Tree structures.Expected output examples: Below are some example test cases that show what kind of results you should be getting when this program is done. Note the exact output format does not have to match these examples. The order in which the data is maintained and presented, though, should be the sameExample 1: Basic function coverageinsertBefore: 5insertBefore: 3insertBefore: 4printCurrent: 4printForward: 4 3 5printReverse: 4 5 3printSize: 3search: 55 was foundprintForward: 5 4 3printReverse: 5 3 4search: 1010 was not foundprintForward: 5 4 3printReverse: 5 3 4update: 4 6Update successfulprintForward: 6 3 5printCurrent: 6printReverse: 6 5 3update: 10 5Update failedprintForward: 6 3 5printCurrent: 6printReverse: 6 5 3insertAfter: 10insertAfter: 20printForward: 20 3 5 6 10printReverse: 20 10 6 5 3delete: 6Delete successfulprintCurrent: 10printForward: 10 20 3 5printReverse: 10 5 3 20delete: 2Delete failedprintCurrent: 10printForward: 10 20 3 5printReverse: 10 5 3 20Example 2: Empty and 1 node situationssearch:55 was not foundupdate: 7 10Update faileddelete: 6Delete failedprintCurrent: Empty ListprintForward: Empty ListprintReverse: Empty ListprintSize: 0insertAfter: 5update: 5 6Update successfuldelete: 5Delete faileddelete: 6Delete successfulSearch: 66 was not foundNote: other test cases will be done during demo through interactive portion of program ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download