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