I am stuck on this problem: Write a method void split(int pIndex, DList pLeft, D
ID: 3714628 • Letter: I
Question
I am stuck on this problem:
Write a method void split(int pIndex, DList pLeft, DList pRight) that will "split" this DList (the one on which the method is invoked) into a left sublist pLeft and a right sublist pRight. The elements of pLeft will consist of list elements at indices 0, 1, 2, ..., pIndex - 1. The elements of pRight will consist of list elements at indices pIndex, pIndex + 1, ..., getSize() - 1. Note that pLeft and pRight must be created (and are assumed to be empty) 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);
//lists would end up looking like: left = { 3, 5, 7, 11, 13 }, right = { 17, 19, 29 }
Explanation / Answer
Hi Dear,
Please find my answer.
Part e. Write a method void split(int pIndex, DList pLeft, DList pRight) that will "split" this DList (the one on which the method is invoked) into a left sublist pLeft and a right sublist pRight. The elements of pLeft will consist of list elements at indices 0, 1, 2, ..., pIndex - 1. The elements of pRightwill consist of list elements at indices pIndex, pIndex + 1, ..., getSize() - 1'
if we do getSize()-1 the last element of the list will be exempted. This has been corrected as getSize()
DList.java
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
//**************************************************************************************************
//CLASS: DList (DList.java)
//
//DESCRIPTION
//Implements a doubly linked list data structure where each element is an Integer.
//
//AUTHOR
//**************************************************************************************************
/**
* Implements a doubly linked list of Integers.
*/
public class DList {
//==============================================================================================
//DList Instance Variables
//==============================================================================================
/**
* For a nonempty DList, mHead is a reference to the first Node in the DList. For an empty
* DList, mHead will be null.
*/
private Node mHead;
/**
* The number of Nodes containing data in this DList. For an empty DList, mSize is 0.
*/
private int mSize;
/**
* For a nonempty DList, mTail is a reference to the last Node in the DList. For an empty DList,
* mTail will be null.
*/
private Node mTail;
//==============================================================================================
//DList Instance Methods
//==============================================================================================
/**
* Creates an empty DList. For an empty DList, mHead = null, mTail = null, and mSize = 0.
*/
public DList() {
setHead(null);
setTail(null);
setSize(0);
}
/**
* Creates a new DList with one element containing pData.
*/
public DList(Integer pData) {
//Create a new Node storing pData. The ctor makes the mPrev and mNext references null.
Node newNode = new Node(pData);
//Make the mHead reference refer to the new node.
setHead(newNode);
//Make the mTail reference refer to the new node.
setTail(newNode);
//The size of the list is now 1.
setSize(1);
}
/**
* Inserts a new Node containing pData into this DList at index pIndex. Shifts the element
* currently at that index (if it exists) and succeeding elements to the right (i.e., adds
* one to their indices).
*
* Note that if pIndex == getSize() the new element is appended to the list.
*
* Throws an IndexOutOfBoundsException if pIndex < 0 or pIndex > size of the DList.
*/
public void add(int pIndex, Integer pData) throws IndexOutOfBoundsException {
//Check for pIndex out of bounds.
if (pIndex < 0 || pIndex > getSize()) throw new IndexOutOfBoundsException();
//Are we appending?
if (pIndex == getSize()) {
//Create a new Node storing pData. The mNext reference is initialized to null because
//the new Node will become the tail Node of the DList and the mNext reference of the
//tail Node is always null. The mPrev reference is initialized to mTail so it will
//refer to the Node preceding the new Node.
Node newNode = new Node(pData, getTail(), null);
//If this DList is empty the new Node becomes the head Node. Otherwise change mNext of
//the tail Node to refer to the new Node.
if (isEmpty()) setHead(newNode);
else getTail().setNext(newNode);
//In any case, we must change mTail to refer to the new Node that is now at the tail.
setTail(newNode);
}
//We are not appending.
else {
//Get a reference to the Node at pIndex. We are inserting a new Node before 'node'.
Node node = getNodeAt(pIndex);
//Create a new Node storing pData. Set the mPrev reference of the new Node to refer to
//the Node preceding 'node'. Set the mNext reference of the new Node to refer to
//'node'.
Node newNode = new Node(pData, node.getPrev(), node);
//If we are not inserting at pIndex = 0 then we need to change the mNext reference of
//the Node preceding 'node' to refer to the new Node.
if (pIndex != 0) node.getPrev().setNext(newNode);
//Make the mPrev reference of 'node' refer to the new Node. The result of these three
//operations is to "link" the the new Node into the DList.
node.setPrev(newNode);
//Are we inserting at index 0? If so, we need to change the head to refer to the new
//Node because the new Node is now at head.
if (pIndex == 0) setHead(newNode);
}
//We have added a new Node to the DList. Increment the size of the DList.
setSize(getSize() + 1);
}
/**
* Appends a new Node storing pData to this DList. Note that passing an index of getSize() to
* add(int pIndex, Integer pData) will cause add() to perform an append operation.
*/
public void append(Integer pData) {
add(getSize(), pData);
}
/**
* Removes all of the elements from the DList. After this operation the DList will be empty.
*/
public void clear() {
//To clear the list is simple. Simply remove the node at index 0 until the list becomes
//empty.
while (!isEmpty()) { remove(0); }
}
/**
* Returns the element at index pIndex.
*
* Thows IndexOutOfBoundsException if pIndex < 0 or pIndex >= mSize.
*/
public Integer get(int pIndex) throws IndexOutOfBoundsException {
return getNodeAt(pIndex).getData();
}
/**
* Accessor method for the mHead field.
*/
protected Node getHead() {
return mHead;
}
/**
* Returns a reference to the Node at index pIndex.
*
* Thows IndexOutOfBoundsException if pIndex < 0 or pIndex >= getSize()
*/
protected Node getNodeAt(int pIndex) throws IndexOutOfBoundsException {
//Check for pIndex out of bounds and throw exception is necessary.
if (pIndex < 0 || pIndex >= getSize()) throw new IndexOutOfBoundsException();
//Since accessing the head and tail nodes is a common operation we check for those cases
//first.
if (pIndex == 0) return getHead();
else if (pIndex == getSize() - 1) return getTail();
//Otherwise, start at the node at index 1 and walk forward until the node at index pIndex
//is reached and then return it.
Node node = getHead().getNext();
for (int index = 1; index < pIndex; ++index) node = node.getNext();
return node;
}
/**
* Accessor method for the mSize field.
*/
public int getSize() {
return mSize;
}
/**
* Accessor method for the mTail field.
*/
protected Node getTail() {
return mTail;
}
/**
* Returns true if this DList is empty.
*/
public boolean isEmpty() {
return getSize() == 0;
}
/**
* Prepends a new Node storing pData to this DList.
*/
public void prepend(Integer pData) {
add(0, pData);
}
/**
* 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;
}
/**
* Removes the element at index pIndex from this DList. Shifts any succeeding elements to
* the left (i.e., subtracts one from their indices). Returns the element that was removed from
* the list.
*
* Throws an IndexOutOfBoundsException is pIndex < 0 || pIndex >= getSize().
*/
public Integer remove(int pIndex) throws IndexOutOfBoundsException {
if (pIndex < 0 || pIndex >= getSize()){
throw new IndexOutOfBoundsException();
}
//Else are we removing the head node in a list with more than one element (note: we will
//not get here if the list has only one element)?
if (pIndex == 0) {
return removeHead();
}
//Else are we removing the tail node in a list with more than one element (note: we will
//not get here if the list has only one element)?
else if (pIndex == getSize() - 1) {
return removeTail();
}
//We are not removing the head or tail node.
else {
Node node = getNodeAt(pIndex);
return removeInterior(node);
}
}
/**
* Method removeAll(In: Integer pData) Returns Nothing
*/
public void removeAll(int pData){
int index = 0;
while ( index < getSize()){
if(get(index).equals(pData)){
remove(index);
}else{
index++;
}
}
}
/**
* Adds element to the list and keeps the
* list in ascending order after every entry
*/
public void orderedAdd( int pData){
append(pData);
List<Integer> listContents = new LinkedList<Integer>();
for (int i = 0; i < getSize(); ++i)
listContents.add(get(i));
Collections.sort(listContents);
clear();
listContents.forEach(e -> append(e) );
}
/**
* Adds element to the list and keeps the
* list in ascending order after every entry
*/
public void split( int pIndex, DList pLeft, DList pRight){
for (int i = 0; i < pIndex-1; ++i)
pLeft.append(get(i));
for (int i = pIndex; i < getSize(); ++i)
pRight.append(get(i));
}
/**
* Removes the element at index pIndex from this DList. Shifts any succeeding elements to
* the left (i.e., subtracts one from their indices). Returns the element that was removed from
* the list.
*
* Throws an IndexOutOfBoundsException is pIndex < 0 || pIndex >= getSize().
*
public Integer remove(int pIndex) throws IndexOutOfBoundsException {
Node node = getNodeAt(pIndex);
//Are we removing the only element in a list with one element?
if (getSize() == 1) {
setHead(null);
setTail(null);
}
//Else are we removing the head node in a list with more than one element (note: we will
//not get here if the list has only one element)?
else if (pIndex == 0) {
//Change the prev reference of the next node to null because the next node will now
//be the head node in the list.
node.getNext().setPrev(null);
//Since we removed the head node, we have to change the head reference to refer to the
//next node succeeding the one that was just removed.
setHead(node.getNext());
}
//Else are we removing the tail node in a list with more than one element (note: we will
//not get here if the list has only one element)?
else if (pIndex == getSize() - 1) {
//Change the next reference of the previous node to null because the previous node will
//now be the tail node in the list.
node.getPrev().setNext(null);
//Since we removed the tail node, we have to change the tail reference to refer to the
//previous node preceding the one that was just removed.
setTail(node.getPrev());
}
//We are not removing the head or tail node.
else {
node.getPrev().setNext(node.getNext());
node.getNext().setPrev(node.getPrev());
}
//We have removed a Node so decrement the size of the list.
setSize(getSize() - 1);
//Return the data stored at the removed Node.
return node.getData();
}*/
/**
* Replaces the element at the specified position in this list with the specified element.
* Returns the element that was previously stored at pIndex.
*/
public Integer set(int pIndex, Integer pData) throws IndexOutOfBoundsException {
Node node = getNodeAt(pIndex);
Integer original = node.getData();
node.setData(pData);
return original;
}
/**
* Mutator method for the mHead field.
*/
protected void setHead(Node pHead) {
mHead = pHead;
}
/**
* Mutator method for the mSize field.
*/
protected void setSize(int pSize) {
mSize = pSize;
}
/**
* Mutator method for the mTail field.
*/
protected void setTail(Node pTail) {
mTail = pTail;
}
/**
* Returns a string representation of this DList where we define string representation be the
* string representation of each of the Nodes.
*/
@Override
public String toString() {
String string = "";
for (int i = 0; i < getSize(); ++i) string += get(i) + " ";
return string;
}
//**********************************************************************************************
//Static Nested Class: Node
//**********************************************************************************************
/**
* The data for each element of the DList is stored in a Node object. A Node object contains
* three instance variables: (1) mData is a reference to the data stored in the Node; (2) mNext
* is a reference to the succeeding Node in the DList; and (3) mPrev is a reference to the
* preceding Node in the DList.
*
* Note that Node is declared as protected so it is not visible to other classes but it is
* accessible to subclasses of DList.
*/
protected static class Node {
//==========================================================================================
//Node Instance Variables
//==========================================================================================
/**
* The data stored in this Node.
*/
Integer mData;
/**
* A reference to the succeeding Node in the DList.
*/
Node mNext;
/**
* A reference to the preceding Node in the DList.
*/
Node mPrev;
//==========================================================================================
//Node Instance Methods
//==========================================================================================
/**
* Creates a new Node storing no data and with mNext and mPrev set to null.
*/
public Node() {
this(null);
}
/**
* Creates a new Node storing pData as the data and with mNext and mPrev set to null.
*/
public Node(Integer pData) {
setData(pData);
setNext(null);
setPrev(null);
}
/**
* Creates a new Node storing pData as the data, mPrev initialized to pPrev, and mNext
* initialized to pNext.
*/
public Node(Integer pData, Node pPrev, Node pNext) {
setData(pData);
setPrev(pPrev);
setNext(pNext);
}
/**
* Returns true if this Node and pNode are equal to each other where equal is defined as:
*
* 1. If pNode is null, returns false.
* 2. If mNode == pNode is true, returns true.
* 3. If the instance variables of this Node are equal to the instance variables of pNode
* returns true.
* 4. Otherwise, returns false.
*/
@Override
public boolean equals(Object pNode) {
Node node = (Node)pNode;
if (node == null) return false;
if (this == node) return true;
if (getData() == node.getData() && getNext() == node.getNext() &&
getPrev() == node.getPrev()) return true;
return false;
}
/**
* Accessor method for the mData instance variable.
*/
public Integer getData() {
return mData;
}
/**
* Accessor method for the mNext instance variable.
*/
public Node getNext() {
return mNext;
}
/**
* Accessor method for the mPrev instance variable.
*/
public Node getPrev() {
return mPrev;
}
/**
* Mutator method for the mData instance variable.
*/
public void setData(Integer pData) {
mData = pData;
}
/**
* Mutator method for the mNext instance variable.
*/
public void setNext(Node pNext) {
mNext = pNext;
}
/**
* Mutator method for the mPrev instance variable.
*/
public void setPrev(Node pPrev) {
mPrev = pPrev;
}
/**
* Returns a string representation of this Node where we define the string representation
* to be the string representation of the data stored in this Node.
*/
@Override
public String toString() {
return "" + getData();
}
}
}
DListTest.java
//**************************************************************************************************
//CLASS: DListTest (DListTest.java)
//
//DESCRIPTION
//Tests the DList class.
//
//AUTHOR
//***********************************************************
/**
* Tests the DList class.
*/
public class DListTest {
public static void main(String[] pArgs) {
new DListTest().run();
}
private DListTest() {
}
private void passOrFail(int pCase, DList list, String pExpected) {
String listAsString = list.toString();
if (!listAsString.equals(pExpected)) {
System.out.println("failed [" + listAsString + "]");
} else {
System.out.println("passed");
}
}
private void run() {
testCase1();
testCase2();
testCase3();
testCase4();
testCase5();
testCase6();
testCase7();
testCase8();
testCase9();
testCase10();
testCase11();
testCase12();
testCase13();
testCase14();
testCase15();
testCase16();
testCase17();
testCase18();
testCase19();
testCase21();
testCase22();
testCase23();
}
/**
* Test Case 1: tests appending of one element to an empty list.
*/
private void testCase1() {
System.out.print("Running test case 1... ");
DList list = new DList();
list.append(1);
passOrFail(1, list, "1 ");
}
/**
* Test Case 2: tests appending of multiple elements.
*/
private void testCase2() {
System.out.print("Running test case 2... ");
DList list = new DList();
list.append(1);
list.append(2);
list.append(3);
list.append(4);
list.append(5);
list.append(6);
passOrFail(2, list, "1 2 3 4 5 6 ");
}
/**
* Test Case 3: test adding one element to an empty list (at pIndex = 0).
*/
private void testCase3() {
System.out.print("Running test case 3... ");
DList list = new DList();
list.add(0, 1);
passOrFail(3, list, "1 ");
}
/**
* Test Case 4: test adding multiple elements to the head of a list (at pIndex = 0).
*/
private void testCase4() {
System.out.print("Running test case 4... ");
DList list = new DList();
list.add(0, 1);
list.add(0, 2);
list.add(0, 3);
list.add(0, 4);
list.add(0, 5);
passOrFail(4, list, "5 4 3 2 1 ");
}
/**
* Test Case 5: test adding multiple elements to the tail of a nonempty list (at
* pIndex = list.getSize()).
*/
private void testCase5() {
System.out.print("Running test case 5... ");
DList list = new DList();
list.add(0, 1);
list.add(list.getSize(), 2);
list.add(list.getSize(), 3);
list.add(list.getSize(), 4);
list.add(list.getSize(), 5);
passOrFail(5, list, "1 2 3 4 5 ");
}
/**
* Test Case 6: test adding multiple elements to the middle of a nonempty list.
*/
private void testCase6() {
System.out.print("Running test case 6... ");
DList list = new DList();
list.add(0, 1);
list.add(1, 2);
list.add(1, 3);
list.add(1, 4);
list.add(1, 5);
list.add(1, 6);
passOrFail(6, list, "1 6 5 4 3 2 ");
}
/**
* Test Case 7: tests prepending of one element to an empty list.
*/
private void testCase7() {
System.out.print("Running test case 7... ");
DList list = new DList();
list.prepend(1);
passOrFail(7, list, "1 ");
}
/**
* Test Case 8: tests prepending of multiple elements to a nonempty list.
*/
private void testCase8() {
System.out.print("Running test case 8... ");
DList list = new DList();
list.prepend(1);
list.prepend(2);
list.prepend(3);
list.prepend(4);
list.prepend(5);
list.prepend(6);
passOrFail(8, list, "6 5 4 3 2 1 ");
}
/**
* Test Case 9: tests that get(index) throws an IndexOutOfBoundsException when an invalid
* index is passed on an empty list.
*/
private void testCase9() {
System.out.print("Running test case 9... ");
DList list = new DList();
try {
Integer i = list.get(0);
} catch (IndexOutOfBoundsException pExcept) {
System.out.println("passed");
}
}
/**
* Test Case 10: tests that get(index) throws an IndexOutOfBoundsException when an invalid
* index < 0 is passed on a nonempty list.
*/
private void testCase10() {
System.out.print("Running test case 10... ");
DList list = new DList();
list.append(1);
list.append(2);
list.append(3);
try {
Integer i = list.get(-1);
} catch (IndexOutOfBoundsException pExcept) {
System.out.println("passed");
}
}
/**
* Test Case 11: tests that get(index) throws an IndexOutOfBoundsException when an invalid
* index >= list.getSize() is passed on a nonempty list.
*/
private void testCase11() {
System.out.print("Running test case 11... ");
DList list = new DList();
list.append(1);
list.append(2);
list.append(3);
try {
Integer i = list.get(3);
} catch (IndexOutOfBoundsException pExcept) {
System.out.println("passed");
}
}
/**
* Test Case 12: tests that remove(index) throws an IndexOutOfBoundsException when an invalid
* index is passed on a empty list.
*/
private void testCase12() {
System.out.print("Running test case 12... ");
DList list = new DList();
try {
Integer i = list.remove(0);
} catch (IndexOutOfBoundsException pExcept) {
System.out.println("passed");
}
}
/**
* Test Case 13: tests that remove(index) throws an IndexOutOfBoundsException when an invalid
* index < 0 is passed on a nonempty list.
*/
private void testCase13() {
System.out.print("Running test case 13... ");
DList list = new DList();
list.append(1);
list.append(2);
list.append(3);
try {
Integer i = list.remove(-1);
} catch (IndexOutOfBoundsException pExcept) {
System.out.println("passed");
}
}
/**
* Test Case 14: tests that remove(index) throws an IndexOutOfBoundsException when an invalid
* index >= list.getSize() is passed on a nonempty list.
*/
private void testCase14() {
System.out.print("Running test case 14... ");
DList list = new DList();
list.append(1);
list.append(2);
list.append(3);
try {
Integer i = list.remove(3);
} catch (IndexOutOfBoundsException pExcept) {
System.out.println("passed");
}
}
/**
* Test Case 15: tests that remove(index) removes the element at index 0 in a list of size 1.
*/
private void testCase15() {
System.out.print("Running test case 15... ");
DList list = new DList();
list.append(1);
Integer i = list.remove(0);
if (i != 1) System.out.println("failed");
passOrFail(15, list, "");
}
/**
* Test Case 16: tests that remove(index) removes the element at index 0 in a nonempty list.
*/
private void testCase16() {
System.out.print("Running test case 16... ");
DList list = new DList();
list.append(1);
list.append(2);
list.append(3);
list.append(4);
Integer i = list.remove(0);
if (i != 1) System.out.println("failed");
passOrFail(16, list, "2 3 4 ");
}
/**
* Test Case 17: tests that remove(index) removes the element at the end of a nonempty list.
*/
private void testCase17() {
System.out.print("Running test case 17... ");
DList list = new DList();
list.append(1);
list.append(2);
list.append(3);
list.append(4);
Integer i = list.remove(3);
if (i != 4) System.out.println("failed");
passOrFail(17, list, "1 2 3 ");
}
/**
* Test Case 18: tests that remove(index) removes the elements from the middle of a nonempty
* list.
*/
private void testCase18() {
System.out.print("Running test case 18... ");
DList list = new DList();
list.append(1);
list.append(2);
list.append(3);
list.append(4);
list.append(5);
list.append(6);
list.append(7);
list.append(8);
list.append(9);
Integer i = list.remove(2);
if (i != 3) System.out.println("failed");
i = list.remove(4);
if (i != 6) System.out.println("failed");
i = list.remove(5);
if (i != 8) System.out.println("failed");
passOrFail(18, list, "1 2 4 5 7 9 ");
}
/**
* Test Case 19/20: tests that clear erases the list.
*/
private void testCase19() {
System.out.print("Running test case 19... ");
DList list = new DList();
list.append(1);
list.append(2);
list.append(3);
list.append(4);
list.append(5);
list.append(6);
list.append(7);
list.append(8);
list.append(9);
list.clear();
passOrFail(19, list, "");
System.out.print("Running test case 20... ");
list.add(0, 8);
list.append(9);
list.append(9);
list.append(9);
passOrFail(20, list, "8 9 9 9 ");
}
/**
* Test Case 21: tests removeAll().
*/
private void testCase21() {
System.out.print("Running test case 21... ");
DList list = new DList();
list.append(1);
list.append(2);
list.append(3);
list.append(3);
list.append(5);
list.append(3);
list.append(3);
list.append(3);
list.append(9);
list.removeAll(3);
passOrFail(21, list, "1 2 5 9 ");
}
/**
* Test Case 22: tests orderedAdd(int pData).
*/
private void testCase22() {
System.out.println("**********************");
System.out.print("Running test case 22... ");
System.out.println();
DList list = new DList();
list.orderedAdd(10);
System.out.println("Add 10: "+ list.toString());
list.orderedAdd(9);
System.out.println("Add 9: "+ list.toString());
list.orderedAdd(1);
System.out.println("Add 1: "+ list.toString());
list.orderedAdd(22);
System.out.println("Add 22: "+ list.toString());
System.out.println("... passed");
System.out.println("**********************");
}
/**
* Test Case 23: tests split().
*/
private void testCase23() {
System.out.println("**********************");
System.out.print("Running test case 23... ");
System.out.println();
DList list = new DList();
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 }
System.out.println("Current list: " + list.toString());
DList pLeft = new DList();
DList pRight = new DList();
list.split(5, pLeft, pRight);
// left = { 3, 5, 7, 11, 13 }
System.out.println("Current pLeft list: " + pLeft.toString());
//right = { 17, 19, 29 }
System.out.println("Current pRight list: " + pRight.toString());
System.out.println("... passed");
System.out.println("**********************");
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.