2) Implement a SinglyLinkedList class that implements the interface List to stor

Question

2) Implement a SinglyLinkedList class that implements the interface List to store elements of a generic type: (i.e., public class SinglyLinkedList > implements List). Just as in the lectures, the class must have a nested static class called Node that stores the generic value and a reference variable next that points to the next node in the list. Here are the methods included in the interface: 1) public int size(); returns the size of the list (must be implemented as a recursive method).

2) public T get(int i); returns the element at position i (first position index is 0).

3) public int indexOf(Object item); returns the position of item ( note that it is of type objects).

4) public void add(int i, T item); adds item at position i of the list.

5) public T remove(int i); removes item at position i of the list.

6a) public T min(); returns the item with the minimum value in the list;

6b) public T minR(); returns the item with the minimum value in the list (must be implemented as a recursive method);

7a) public T max(); returns the item with the maximum value in the list;

7B) public T maxR(); returns the item with the maximum value in the list (must be implemented as a recursive method);

8) public boolean Empty(): returns true if the list is empty.

9) public void addAthead(T item) : adds an “element at the head of the list

10) public void addAtEnd(T item): adds an element at the end of the list.

11) public void replace(T first, T second): takes two elements as an input, searches for the first(first) in the list, if it is found it will replace it with second ( without creating an nodes).

12) public List duplicate(T item): A recursive method to duplicate every element in a linked list, that is equal to a certain value. For example, if the linked list contains 4, 8, 4, 10 the element to duplicate is 4 the new list should contain 4,4,8,4,4, 10.

13) public void reverse(): A recursive method that prints out the data elements of a linked list in reverse order.

14) public List countGreaterThan(T threshold): A recursive method that returns a list containing all the elements in the original list that are larger than threshold.

15) public Boolean equals(Object other): A recursive method returns true if other is a list that has the same elements in the list with the same order.

16) public String toString(): returns a string representation of the elements in the list separated by a comm..

17) public List inorder(); returns a new list that has all the elements in the list sorted in an ascending order.

18) public void removeEven(): removes all the elements at even positions from the list (0,2, 4, ..) and keeps only the elements at the odd positions.

plz help solving part 3,9,10,11,13,15,17,18 if possible

Explanation / Answer

/** * * @author Frank van Heeswijk * @param Type of elements the list stores */ public class LinkedList implements List { /** Fake head node, meaning that it is not part of the List it represents. **/ private Node head; /** Fake tail node, meaning that it is not part of the List it represents. **/ private Node tail; /** If this list is a sublist of a LinkedList, then the parent will be in this variable. **/ private LinkedList parentList; /** The amount of modifications that occured to this LinkedList so far. **/ private int modificationsCount; /** The size of this LinkedList. **/ private int size; public LinkedList() { this(Collections.emptyList()); } public LinkedList(final Collection collection) { Objects.requireNonNull(collection); return collection.stream().allMatch(this::contains); } @Override public boolean addAll(final Collection collection) { Objects.requireNonNull(collection); if (collection.isEmpty()) { return false; } int deletions = 0; ListIterator listIterator = listIterator(); while (listIterator.hasNext()) { E next = listIterator.next(); if (collection.stream().anyMatch(elem -> elem.equals(next))) { listIterator.remove(); deletions++; } } return (deletions > 0); } @Override public boolean retainAll(final Collection collection) { Objects.requireNonNull(collection); if (collection.isEmpty()) { return false; } int deletions = 0; ListIterator listIterator = listIterator(); while (listIterator.hasNext()) { E next = listIterator.next(); if (collection.stream().noneMatch(elem -> elem.equals(next))) { listIterator.remove(); deletions++; } } return (deletions > 0); } @Override public void clear() { if (isEmpty()) { return; } connect(head, tail); modifySize(-size()); } @Override public E get(final int index) { assertIndex(index); return listIterator(index).next(); } @Override public E set(final int index, final E element) { if (this == element) { throw new IllegalArgumentException(); } assertIndex(index); ListIterator listIterator = listIterator(index); E old = listIterator.next(); listIterator.set(element); return old; } @Override public void add(final int index, final E element) { if (this == element) { throw new IllegalArgumentException(); } assertIndexExclusive(index); ListIterator listIterator = listIterator(index); listIterator.add(element); } @Override public E remove(final int index) { assertIndex(index); ListIterator listIterator = listIterator(index); E old = listIterator.next(); listIterator.remove(); return old; } @Override public int indexOf(final Object object) { ListIterator listIterator = listIterator(); while (listIterator.hasNext()) { if (listIterator.next().equals(object)) { return listIterator.nextIndex() - 1; } } return -1; } @Override public int lastIndexOf(final Object object) { ListIterator listIterator = listIterator(size()); while (listIterator.hasPrevious()) { if (listIterator.previous().equals(object)) { return listIterator.previousIndex() + 1; } } return -1; } @Override public ListIterator listIterator() { return listIterator(0); } @Override public ListIterator listIterator(final int index) { assertIndexExclusive(index); ListIterator listIterator; if (isEmpty()) { listIterator = listNodeIteratorEmpty(); } else if (index size() || fromIndex > toIndex) { throw new IndexOutOfBoundsException(); } if (toIndex - fromIndex == 0) { return new LinkedList(head, head.next, 0, this); } ListIterator listIterator = new LinkedListNodeListIterator(); while (listIterator.hasNext() && fromIndex != listIterator.nextIndex()) { listIterator.next(); } Node fromNode = listIterator.next(); while (listIterator.hasNext() && toIndex != listIterator.nextIndex()) { listIterator.next(); } Node toNode = listIterator.previous(); return new LinkedList(fromNode.previous, toNode.next, toIndex - fromIndex, this); } @Override public boolean equals(final Object other) { if (other == null) { return false; } if (!(other instanceof List)) { return false; } List otherList = (List)other; if (size() != otherList.size()) { return false; } Iterator iterator = iterator(); Iterator otherIterator = otherList.iterator(); while (iterator.hasNext() && otherIterator.hasNext()) { E next = iterator.next(); Object otherNext = otherIterator.next(); if (!Objects.equals(next, otherNext)) { return false; } } return true; } @Override public int hashCode() { return Objects.hash(iteratorToStream().toArray()); } @Override public String toString() { return "[" + iteratorToStream() .map(object -> (object == null ? "null" : object.toString())) .collect(Collectors.joining(", ")) + "]"; } private void assertIndex(final int index) { if (index < 0 || index >= size()) { throw new IndexOutOfBoundsException(); } } private void assertIndexExclusive(final int index) { if (index < 0 || index > size()) { throw new IndexOutOfBoundsException(); } } private void modifySize(final int deltaSize) { size += deltaSize; if (parentList != null) { parentList.modifySize(deltaSize); } } private void incrementModificationsCount() { modificationsCount++; if (parentList != null) { parentList.incrementModificationsCount(); } } private Stream iteratorToStream() { return StreamSupport.stream(spliterator(), false); } private LinkedListListIterator listNodeIteratorEmpty() { return new LinkedListListIterator(-1, head, 0, tail); } private LinkedListListIterator listNodeIteratorFromHead() { return new LinkedListListIterator(-1, head, 0, head.next); } private LinkedListListIterator listNodeIteratorFromTail() { return new LinkedListListIterator(size() - 1, tail.previous, size(), tail); } @SafeVarargs private final void connect(final Node... nodes) { if (nodes.length == 0 || nodes.length == 1) { throw new IllegalArgumentException(); } for (int i = 0; i

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.