Write a method void split

Assignment Help JAVA Programming
Reference no: EM131590846

Looking for help answering these 7 questions.

4.1 (Include your modified DList.java source code file in your homework solution zip archive) Usingwhatever Java IDE you prefer, create a project and add DList.java and DListTest.java to it (these files are providedin the Week 6 Source zip archive). Modify DList to implement a method that removes all occurrences of a specificinteger from the list. Here is the pseudocode:Method removeAll(In: Integer pData) Returns NothingDefine index variable i and initialize i to 0While i the size of this Dlist DoIf get(i) equals pData Thenremove(i)ElseIncrement iEnd IfEnd WhileEnd Method removeAllNext, modify DListTest() to add test case 21 which tests that removeAll() works correctly.

4.2 Let n be the size of a DList, i.e., the number of elements. The remove(index) method is O(n). The get(i) method isO(n) because in the worst case, we have to traverse almost the entire list to locate the element at index i. Why?get(i) calls getNodeAt(i) to obtain a reference to the node at index i so the time complexity of get(i) is proportionalto the time complexity of getNodeAt(i).Now what is the time complexity of getNodeAt(i)? The key operations in getNodeAt() are the assignments ofgetHead().getNext() before the loop starts and the assignment of node.getNext() to node during each iteration of thefor loop. For getNodeAt(0) and getNodeAt(n - 1) the key operations will never be performed so the best case time complexity of getNodeAt() is O(1). In the worst case, i would be n - 2 and the key operations would be performed 1+ n - 2 = n - 1 times so the worst case time complexity is O(n).The key operations of removeAll() are the key operations of getNodeAt(). For this exercise, define a function f(n)which specifies the maximum number of times the key operations will occur as a function of the list size n. Then specify what the worst case time complexity of removeAll() is in big O notation (you don't have to provide a formal proof; just do a little hand waving).

4.3 (Include DList.java in your solution zip archive) Here is the Java implementation of three useful methods(which are not currently in Dlist). /** * Removes the head node from this DList. It would be inadvisable to call this method on an * empty list because we do not check for that condition. Returns the data stored in the head * node. */ protected Integer removeHead() { Integer data = getHead().getData(); if (getSize() == 1) { setHead(null); setTail(null); } else { getHead().getNext().setPrev(null); setHead(getHead().getNext()); } setSize(getSize() - 1); return data; } /** * Removes an interior node pNode from this DList. It would be inadvisable to call this method * when pNode is null because we do not check for that condition. Returns the data stored in * pNode. */ protected Integer removeInterior(Node pNode) { Integer data = pNode.getData(); pNode.getPrev().setNext(pNode.getNext()); pNode.getNext().setPrev(pNode.getPrev()); setSize(getSize() - 1); return data; } /** * Removes the tail node from this DList. It would be inadvisable to call this method on an * empty list because we do not check for that condition. Returns the data stored in the tail * node. */ protected Integer removeTail() { Integer data = getTail().getData(); if (getSize() == 1) { setHead(null); setTail(null); } else { getTail().getPrev().setNext(null); setTail(getTail().getPrev()); } setSize(getSize() - 1); return data; }Using these three methods, rewrite the provided remove(index) method to make the code in that method simplerand more readable (my new and improved remove() method is half-a-dozen lines of code). Be sure to run the testcases in DListTest to ensure that your new remove() method still works correctly. Also, make sure remove() throwsan IndexOutOfBoundsException if pIndex is less than 0 or greater than or equal to getSize().

4.4 (Include DList.java in your solution zip archive) Here is the Java implementation of three useful methods(which are not currently in Dlist). /** * Adds a new node storing pData to be the new head of this DList. */ protected void addHead(Integer pData) { Node newNode = new Node(pData, null, getHead()); if (getHead() == null) { setTail(newNode); } else { getHead().setPrev(newNode); } setHead(newNode); setSize(getSize() + 1); } /** * Adds a new node storing pData to be the predecessor to pNode pNode (pNode may be head or tail). */ protected void addInterior(Integer pData, Node pNode) { if (pNode == getHead()) { addHead(pData); } else { Node newNode = new Node(pData, pNode.getPrev(), pNode); pNode.getPrev().setNext(newNode); pNode.setPrev(newNode); setSize(getSize() + 1); } } /** * Adds a new node storing pData to be the new tail of this DList. */ protected void addTail(Integer pData) { Node newNode = new Node(pData, getTail(), null); if (getTail() == null) { setHead(newNode); } else { getTail().setNext(newNode); } setTail(newNode); setSize(getSize() + 1); }Using these three methods, rewrite add(index, data) to make the code in that method simpler and more readable(my new and improved add() method is half-a-dozen lines of code). Be sure to run the test cases in DListTest toensure that your new remove() method still works correctly. Also, make sure add() still throws an IndexOutOfBoundsException if pIndex is less than 0 or greater than getSize().

4.5 (Include DList.java in your solution zip archive) If you determined the correct answer to Exercise 4.2, you may wonder if the pseudocode of Exercise 4.1 is really the best way to remove all nodes containing a specific valuefrom the list. For this exercise, comment out the statements in removeAll() that that you implemented in Exercise4.1, and provide a more efficient implementation of this method. Reuse your same test case from Exercise 4.1 to verify that your new implementation works correctly. Rather than giving you pseudocode, I will give you a hint by describing the general procedure. Create a Node object named node which initially refers to the head of the list. Compare the data in the head node to pData. If they match, call removeHead() to remove the head node (note that the next node you will visit will be the new head node). If they do not match, make node refer to the node succeeding head. Compare the data in the element in the node to pData. if they match, and if this is not the tail node, call removeInterior() to remove the node. Continue moving node to each successive node, checking for a match and removing when necessary. Like the head node,removing the tail node has to be handled specially by calling removeTail(). Do not even think about callinggetNodeAt(index) or remove(index); the only methods my solution uses are getHead(), removeHead(), removeInterior(), removeTail(), and getNext() on the node when we need to move to the next node.

4.6 Give an informal proof of the worst case time complexity of your new removeAll() method of Exercise 4.5. Basically,what I am looking for is an identification of the key operation, a function f(n) which counts the maximum number oftimes the key operation is performed as a function of the list size n, and then state that f(n) is O(g(n)) for someg(n).

4.7 (Include DList.java in your solution zip archive) Using the new add methods,rewrite append(data) and prepend(data).

4.8 (Include DList.java in your solution zip archive) Write a method void orderedAdd(Integer pData) that will insert Integers into a DList such that ascending sort order is maintained. For example,DList list = new DList(); // list = { }list.orderedAdd(5); // list = { 5 }list.orderedAdd(3); // list = { 3 5 }list.orderedAdd(1); // list = { 1 3 5 }list.orderedAdd(7); // list = { 1 3 5 7 }list.orderedAdd(9); // list = { 1 3 5 7 9 }list.orderedAdd(-5); // list = { -5 1 3 5 7 9 }

4.9 Write a method void split(int pIndex, DList pLeft, DList pRight) that will "split" thisDList (the one on which the method is invoked) into a left sublist pLeft and a right sublist pRight. The elements ofpLeft will consist of list elements at indices 0, 1, 2, ..., pIndex - 1. The elements of pRight will consist of list elementsat indices pIndex, pIndex + 1, ..., getSize() - 1. Note that pLeft and pRight must be created (and are assumed to beempty) before calling split(). For example:DList list = new DList(); // list = { }list.append(3); list.append(5); list.append(7); list.append(11);list.append(13); list.append(17); list.append(19); list.append(29);// list = { 3, 5, 7, 11, 13, 17, 19, 29 }DList left = new DList, right = new DList();list.split(5, left, right);// left = { 3, 5, 7, 11, 13 }, right = { 17, 19, 29 }

Attachment:- DList.rar

Reference no: EM131590846

Questions Cloud

What is organized crime : What is organized crime. What are some examples of organized crime. What are the similarities among various criminal organizations
How many electrons must be removed : AN object has a charge of -2 microC. How many electrons must be removed so that the charge becomes +3 microC?
What are some of the challenges and how can they be overcome : What are some of the challenges and how can they be overcome? Do you feel incentive programs are beneficial? Why or why not?
Define the enforcement of victimless crimes : argument by defining victimless crime and discuss whether or not you believe the enforcement of victimless crimes makes society safer
Write a method void split : Create a project and add DList.java and DListTest.java to it - If you determined the correct answer to Exercise 4.2, you may wonder if the pseudocode
Find at least one thing you liked or felt was a strong point : For each essay, find at least one thing you liked or felt was a strong point. Was it a descriptive detail? Why did it make the paper better for you?
Describe the facets of organizational culture : Describe the facets of organizational culture, including influences and functions, challenges related to changing the culture, and the impact of culture.
Determine the initial velocity of the stone : A stone is thrown vertically upwards and reaches a height of 100 m. Determine the initial velocity of the stone.
How much heat was needed for this transformation : Heat is added to the chunk until it is completely vaporized and the steam is at a temperature of 116.1 degrees C.

Reviews

Write a Review

JAVA Programming Questions & Answers

  Recursive factorial program

Write a class Array that encapsulates an array and provides bounds-checked access. Create a recursive factorial program that prompts the user for an integer N and writes out a series of equations representing the calculation of N!.

  Hunt the wumpus game

Reprot on Hunt the Wumpus Game has Source Code listing, screen captures and UML design here and also, may include Javadoc source here.

  Create a gui interface

Create GUI Interface in java programing with these function: Sort by last name and print all employees info, Sort by job title and print all employees info, Sort by weekly salary and print all employees info, search by job title and print that emp..

  Plot pois on a graph

Write a JAVA program that would get the locations of all the POIs from the file and plot them on a map.

  Write a university grading system in java

University grading system maintains number of tables to store, retrieve and manipulate student marks. Write a JAVA program that would simulate a number of cars.

  Wolves and sheep: design a game

This project is designed a game in java. you choose whether you'd like to write a wolf or a sheep agent. Then, you are assigned to either a "sheep" or a "wolf" team.

  Build a graphical user interface for displaying the image

Build a graphical user interface for displaying the image groups (= cluster) in JMJRST. Design and implement using a Swing interface.

  Determine the day of the week for new year''s day

This assignment contains a java project. Project evaluates the day of the week for New Year's Day.

  Write a java windowed application

Write a Java windowed application to do online quiz on general knowledge and the application also displays the quiz result.

  Input pairs of natural numbers

Java program to input pairs of natural numbers.

  Create classes implement java interface

Interface that contains a generic type. Create two classes that implement this interface.

  Java class, array, link list , generic class

These 14 questions covers java class, Array, link list , generic class.

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd