I feel like I am overcomplicating this problem been struggling with it for the l
ID: 3806036 • Letter: I
Question
I feel like I am overcomplicating this problem been struggling with it for the last two days so any help would be great.
a) In the class MyLinkedList, the implantation of the methods contains(E e), get(int index), indexOf(E e), lastIndexOf(E e), and set(int index, E e) have been omitted. Implement these methods.
b) In the private class LinkedListIterator (which is internal to MyLinkedList), implement method remove(). This method removes from the list the last element that was returned by next(). This call can only be made once per call to next(). It can be made only if add(E) has not been called after the last call to next.
c) Add code to “TestMyLinkedList.java” to demonstrate that these methods work correctly.
#MyLinkedList
public class MyLinkedList<E> extends MyAbstractList<E> {
private Node<E> head, tail;
/**Create a default list*/
public MyLinkedList() {
}
/**Create a list from an array of objects*/
public MyLinkedList(E[] objects) {
super(objects);
}
/**Return the head element in the list*/
public E getFirst() {
if (size == 0) {
return null;
} else {
return head.element;
}
}
/**Return the last element in the list*/
public E getLast() {
if (size == 0) {
return null;
} else {
return tail.element;
}
}
/**Add an element to the beginning of the list*/
public void addFirst(E e) {
Node<E> newNode = new Node<E>(e); // Create a new node
newNode.next = head; // link the new node with the head
head = newNode; // head points to the new node
size++; // Increase list size
if (tail == null) // the new node is the only node in list
{
tail = head;
}
}
/**Add an element to the end of the list*/
public void addLast(E e) {
Node<E> newNode = new Node<E>(e); // Create a new for element e
if (tail == null) {
head = tail = newNode; // The new node is the only node in list
} else {
tail.next = newNode; // Link the new with the last node
tail = tail.next; // tail now points to the last node
}
size++; // Increase size
}
@Override
/**Add a new element at the specified index in this list. The index of the
* head element is 0*/
public void add(int index, E e) {
if (index == 0) {
addFirst(e);
} else if (index >= size) {
addLast(e);
} else {
Node<E> current = head;
for (int i = 1; i < index; i++) {
current = current.next;
}
Node<E> temp = current.next;
current.next = new Node<E>(e);
(current.next).next = temp;
size++;
}
}
/**Remove the head node and return the object that is contained in the
* removed node.*/
public E removeFirst() {
if (size == 0) {
return null;
} else {
Node<E> temp = head;
head = head.next;
size--;
if (head == null) {
tail = null;
}
return temp.element;
}
}
/**Remove the last node and return the object that is contained in the
* removed node.*/
public E removeLast() {
if (size == 0) {
return null;
} else if (size == 1) {
Node<E> temp = head;
head = tail = null;
size = 0;
return temp.element;
} else {
Node<E> current = head;
for (int i = 0; i < size - 2; i++) {
current = current.next;
}
Node<E> temp = tail;
tail = current;
tail.next = null;
size--;
return temp.element;
}
}
@Override
/**Remove the element at the specified position in this list. Return the
* element that was removed from the list.*/
public E remove(int index) {
if (index < 0 || index >= size) {
return null;
} else if (index == 0) {
return removeFirst();
} else if (index == size - 1) {
return removeLast();
} else {
Node<E> previous = head;
for (int i = 1; i < index; i++) {
previous = previous.next;
}
Node<E> current = previous.next;
previous.next = current.next;
size--;
return current.element;
}
}
@Override
/**Override toString() to return elements in the list*/
public String toString() {
StringBuilder result = new StringBuilder("[");
Node<E> current = head;
for (int i = 0; i < size; i++) {
result.append(current.element);
current = current.next;
if (current != null) {
result.append(", "); // Separate two elements with a comma
} else {
result.append("]"); // Insert the closing ] in the string
}
}
return result.toString();
}
@Override
/**Clear the list*/
public void clear() {
size = 0;
head = tail = null;
}
@Override
/**Return true if this list contains the element e*/
public boolean contains(E e) {
System.out.println("Implementation left as an exercise");
return true;
}
@Override
/**Return the element at the specified index*/
public E get(int index) {
System.out.println("Implementation left as an exercise");
return null;
}
@Override
/**Return the index of the head matching element in this list. Return -1 if
* no match.*/
public int indexOf(E e) {
System.out.println("Implementation left as an exercise");
return 0;
}
@Override
/**Return the index of the last matching element in this list. Return -1 if
* no match.*/
public int lastIndexOf(E e) {
System.out.println("Implementation left as an exercise");
return 0;
}
@Override
/**Replace the element at the specified position in this list with the
* specified element.*/
public E set(int index, E e) {
System.out.println("Implementation left as an exercise");
return null;
}
@Override
/**Override iterator() defined in Iterable*/
public java.util.Iterator<E> iterator() {
return new LinkedListIterator();
}
private void checkIndex(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
}
private class LinkedListIterator
implements java.util.Iterator<E> {
private Node<E> current = head; // Current index
@Override
public boolean hasNext() {
return (current != null);
}
@Override
public E next() {
E e = current.element;
current = current.next;
return e;
}
@Override
public void remove() {
System.out.println("Implementation left as an exercise");
}
} // end of LinkedListIterator
private static class Node<E> {
E element;
Node<E> next;
public Node(E element) {
this.element = element;
}
} // end of Node
}
#TestMyLinkedList
package listapi;
public class TestMyLinkedList {
public TestMyLinkedList() {
// Create a list for strings
MyLinkedList<String> list = new MyLinkedList<String>();
// Add elements to the list
list.add("America"); // Add it to the list
System.out.println("(1) " + list);
list.add(0, "Canada"); // Add it to the beginning of the list
System.out.println("(2) " + list);
list.add("Russia"); // Add it to the end of the list
System.out.println("(3) " + list);
list.addLast("France"); // Add it to the end of the list
System.out.println("(4) " + list);
list.add(2, "Germany"); // Add it to the list at index 2
System.out.println("(5) " + list);
list.add(5, "Norway"); // Add it to the list at index 5
System.out.println("(6) " + list);
list.add(0, "Poland"); // Same as list.addFirst("Poland")
System.out.println("(7) " + list);
// Remove elements from the list
list.remove(0); // Same as list.remove("Australia") in this case
System.out.println("(8) " + list);
list.remove(2); // Remove the element at index 2
System.out.println("(9) " + list);
list.remove(list.size() - 1); // Remove the last element
System.out.print("(10) " + list + " (11) ");
for (String s : list) {
System.out.print(s.toUpperCase() + " ");
}
list.clear();
System.out.println(" After clearing the list, the list size is "
+ list.size());
}
}
Explanation / Answer
Here is the code implemented for you:
public class MyLinkedList<E> extends MyAbstractList<E> {
private Node<E> head, tail;
/**Create a default list*/
public MyLinkedList() {
}
/**Create a list from an array of objects*/
public MyLinkedList(E[] objects) {
super(objects);
}
/**Return the head element in the list*/
public E getFirst() {
if (size == 0) {
return null;
} else {
return head.element;
}
}
/**Return the last element in the list*/
public E getLast() {
if (size == 0) {
return null;
} else {
return tail.element;
}
}
/**Add an element to the beginning of the list*/
public void addFirst(E e) {
Node<E> newNode = new Node<E>(e); // Create a new node
newNode.next = head; // link the new node with the head
head = newNode; // head points to the new node
size++; // Increase list size
if (tail == null) // the new node is the only node in list
{
tail = head;
}
}
/**Add an element to the end of the list*/
public void addLast(E e) {
Node<E> newNode = new Node<E>(e); // Create a new for element e
if (tail == null) {
head = tail = newNode; // The new node is the only node in list
} else {
tail.next = newNode; // Link the new with the last node
tail = tail.next; // tail now points to the last node
}
size++; // Increase size
}
@Override
/**Add a new element at the specified index in this list. The index of the
* head element is 0*/
public void add(int index, E e) {
if (index == 0) {
addFirst(e);
} else if (index >= size) {
addLast(e);
} else {
Node<E> current = head;
for (int i = 1; i < index; i++) {
current = current.next;
}
Node<E> temp = current.next;
current.next = new Node<E>(e);
(current.next).next = temp;
size++;
}
}
/**Remove the head node and return the object that is contained in the
* removed node.*/
public E removeFirst() {
if (size == 0) {
return null;
} else {
Node<E> temp = head;
head = head.next;
size--;
if (head == null) {
tail = null;
}
return temp.element;
}
}
/**Remove the last node and return the object that is contained in the
* removed node.*/
public E removeLast() {
if (size == 0) {
return null;
} else if (size == 1) {
Node<E> temp = head;
head = tail = null;
size = 0;
return temp.element;
} else {
Node<E> current = head;
for (int i = 0; i < size - 2; i++) {
current = current.next;
}
Node<E> temp = tail;
tail = current;
tail.next = null;
size--;
return temp.element;
}
}
@Override
/**Remove the element at the specified position in this list. Return the
* element that was removed from the list.*/
public E remove(int index) {
if (index < 0 || index >= size) {
return null;
} else if (index == 0) {
return removeFirst();
} else if (index == size - 1) {
return removeLast();
} else {
Node<E> previous = head;
for (int i = 1; i < index; i++) {
previous = previous.next;
}
Node<E> current = previous.next;
previous.next = current.next;
size--;
return current.element;
}
}
@Override
/**Override toString() to return elements in the list*/
public String toString() {
StringBuilder result = new StringBuilder("[");
Node<E> current = head;
for (int i = 0; i < size; i++) {
result.append(current.element);
current = current.next;
if (current != null) {
result.append(", "); // Separate two elements with a comma
} else {
result.append("]"); // Insert the closing ] in the string
}
}
return result.toString();
}
@Override
/**Clear the list*/
public void clear() {
size = 0;
head = tail = null;
}
@Override
/**Return true if this list contains the element e*/
public boolean contains(E e) {
Node<E> current = head;
for(int i = 0; i < size; i++)
if(current.element == e)
return true;
return false;
}
@Override
/**Return the element at the specified index*/
public E get(int index) {
if (index < 0 || index >= size) {
return null;
} else if (index == 0) {
return head.element;
} else if (index == size - 1) {
return tail.element;
} else {
Node<E> previous = head;
for (int i = 1; i < index; i++) {
previous = previous.next;
}
Node<E> current = previous.next;
return current.element;
}
}
@Override
/**Return the index of the head matching element in this list. Return -1 if
* no match.*/
public int indexOf(E e) {
Node<E> current = head;
for (int i = 0; i < size; i++) {
if(current.element == e)
return i;
}
return -1;
}
@Override
/**Return the index of the last matching element in this list. Return -1 if
* no match.*/
public int lastIndexOf(E e) {
Node<E> current = head;
for (int i = size; i >= 0; i--) {
if(this.get(i) == e)
return i;
}
return -1;
}
@Override
/**Replace the element at the specified position in this list with the
* specified element.*/
public E set(int index, E e) {
if (index < 0 || index >= size) {
return null;
} else if (index == 0) {
head.element = e;
} else if (index == size - 1) {
tail.element = e;
} else {
Node<E> previous = head;
for (int i = 1; i < index; i++) {
previous = previous.next;
}
Node<E> current = previous.next;
current.element = e;
}
return e;
}
@Override
/**Override iterator() defined in Iterable*/
public java.util.Iterator<E> iterator() {
return new LinkedListIterator();
}
private void checkIndex(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
}
private class LinkedListIterator
implements java.util.Iterator<E> {
private Node<E> current = head; // Current index
@Override
public boolean hasNext() {
return (current != null);
}
@Override
public E next() {
E e = current.element;
current = current.next;
return e;
}
@Override
public void remove() {
System.out.println("Implementation left as an exercise");
}
} // end of LinkedListIterator
private static class Node<E> {
E element;
Node<E> next;
public Node(E element) {
this.element = element;
}
} // end of Node
}
If you want the detailed implementation with execution, you should also provide the MyAbstractList, which is extended here.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.