For this question, you need to write a program that implements a doubly-like linked structure. Your...

Transcribed Image Text:

For this question, you need to write a program that implements a doubly-like linked structure. Your code should be able to create such a structure and add objects (of generic type E) to this structure. Each node in the list is an instance of a (nested) Node class (see attached code). Each instance of Node points to two other Node instances: the node immediately to its right (next) and the node before it by skipping one (prevSkip)! (see examples below for prevSkip illustration) A single node in this structure will look like this: For simplicity, the node will be drawn as: prevSkip next prevSkip 5 next Once the node point to a null, the typical symbol used in lectures will be used This class has a main function called add. Once the add function is used repeatedly for the following four integer objects: 5,2,7,3 starting from an empty list, the result after each add is: Head prevSkip 5 next next 2 Head prevSkip 5 Head prevskip prevskip next next next 5 2 7 Head 5 prevskip Prevskip 3 Moreover, your code should be able to transform a given one-dimensional array of objects (of a generic type E) into this structure. This can be done at the construction time (using a specific constructor). Example: Integer [6] As an array: 5 2 7 3 1 9 As a doubly-like linked structure: Head 5 2 7 3 9 Question 1 is decomposed into five sub-questions: Questions 1.1 to 1.5. The implementation of all these questions will all be done in Linked DoublySkip.java (The only file to be uploaded back). Questions: 1.1) public void add(E object) { .... //8 marks 1.2) 1.3) This is a public function that adds one extra node to the structure. public LinkedDoublySkip() { ... //2 marks This is the default constructor. public Linked DoublySkip(E[] array) { .... //5 marks This constructor receives an array and creates a list structure from the array content. Hint: you can call other methods from the same class (e.g. add(...)). 1.4) public E getElementAt(int index) { .... //6 marks 1.5) This function returns the element at position index, assuming the first node in the list is at position 0 private class Linked Doublylterator implements Iterator {... //9 marks Finish the constructor Linked DoublyIterator and methods hasNext and next and add any necessary private variables (if needed!) to iterate the structure as shown in the sample output (once you reach the last node, follow prevSkip to the first node). Sample test class: (See Q1Test.java file) Sample output: List 1 with toString List 2 with toString List 1 with getElementAt List 2 with getElementAt List 1 with iIterator List 2 with iIterator 1, 2, 3, 4 1, 2, 3, 4, 5 1, 2, 3, 4 1, 2, 3, 4, 5 1, 2, 3, 4, 2, 1 1, 2, 3, 4, 5, 3, 1 -- second set of test cases: using the second constructor List 1 with toString List 2 with toString List 1 with getElementAt List 2 with getElementAt List 1 with iIterator List 2 with iIterator : 5, 2, 7, 3, 1, 9 : 5, 2, 7, 3, 1, 9, 10 : 5, 2, 7, 3, 1, 9 : 5, 2, 7, 3, 1, 9, 10 : 5, 2, 7, 3, 1, 9, : 5, 2, 7, 3, 1, 9, Important Restrictions for Question 1 -- 3, 2, 5 10, 1, 7, 5 You cannot define any new variable or method in the classes Linked DoublySkip or Node You may define new private variables in the inner class Linked DoublyIterator. Do not add any exception handling beyond what is provided to you in the shell implementation. . You cannot import anything at all. You cannot use any other classes than the ones we provide. The file LinkedDoublySkip.java should contain all your answers to all five questions. For this question, you need to write a program that implements a doubly-like linked structure. Your code should be able to create such a structure and add objects (of generic type E) to this structure. Each node in the list is an instance of a (nested) Node class (see attached code). Each instance of Node points to two other Node instances: the node immediately to its right (next) and the node before it by skipping one (prevSkip)! (see examples below for prevSkip illustration) A single node in this structure will look like this: For simplicity, the node will be drawn as: prevSkip next prevSkip 5 next Once the node point to a null, the typical symbol used in lectures will be used This class has a main function called add. Once the add function is used repeatedly for the following four integer objects: 5,2,7,3 starting from an empty list, the result after each add is: Head prevSkip 5 next next 2 Head prevSkip 5 Head prevskip prevskip next next next 5 2 7 Head 5 prevskip Prevskip 3 Moreover, your code should be able to transform a given one-dimensional array of objects (of a generic type E) into this structure. This can be done at the construction time (using a specific constructor). Example: Integer [6] As an array: 5 2 7 3 1 9 As a doubly-like linked structure: Head 5 2 7 3 9 Question 1 is decomposed into five sub-questions: Questions 1.1 to 1.5. The implementation of all these questions will all be done in Linked DoublySkip.java (The only file to be uploaded back). Questions: 1.1) public void add(E object) { .... //8 marks 1.2) 1.3) This is a public function that adds one extra node to the structure. public LinkedDoublySkip() { ... //2 marks This is the default constructor. public Linked DoublySkip(E[] array) { .... //5 marks This constructor receives an array and creates a list structure from the array content. Hint: you can call other methods from the same class (e.g. add(...)). 1.4) public E getElementAt(int index) { .... //6 marks 1.5) This function returns the element at position index, assuming the first node in the list is at position 0 private class Linked Doublylterator implements Iterator {... //9 marks Finish the constructor Linked DoublyIterator and methods hasNext and next and add any necessary private variables (if needed!) to iterate the structure as shown in the sample output (once you reach the last node, follow prevSkip to the first node). Sample test class: (See Q1Test.java file) Sample output: List 1 with toString List 2 with toString List 1 with getElementAt List 2 with getElementAt List 1 with iIterator List 2 with iIterator 1, 2, 3, 4 1, 2, 3, 4, 5 1, 2, 3, 4 1, 2, 3, 4, 5 1, 2, 3, 4, 2, 1 1, 2, 3, 4, 5, 3, 1 -- second set of test cases: using the second constructor List 1 with toString List 2 with toString List 1 with getElementAt List 2 with getElementAt List 1 with iIterator List 2 with iIterator : 5, 2, 7, 3, 1, 9 : 5, 2, 7, 3, 1, 9, 10 : 5, 2, 7, 3, 1, 9 : 5, 2, 7, 3, 1, 9, 10 : 5, 2, 7, 3, 1, 9, : 5, 2, 7, 3, 1, 9, Important Restrictions for Question 1 -- 3, 2, 5 10, 1, 7, 5 You cannot define any new variable or method in the classes Linked DoublySkip or Node You may define new private variables in the inner class Linked DoublyIterator. Do not add any exception handling beyond what is provided to you in the shell implementation. . You cannot import anything at all. You cannot use any other classes than the ones we provide. The file LinkedDoublySkip.java should contain all your answers to all five questions.