Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

Instruction: Consider a member method findDuplicates which returns a new List with all the elements that appear more than once in the original list. The

Instruction: Consider a member method findDuplicates which returns a new List with all the elements that appear more than once in the original list. The resulting list itself cannot have duplicates. If there are no duplicates, the method returns an empty list. Implement this method for the SinglyLinkedList class. For example, if L = {1, 0, 4, 3, 1, 1, 2, 4}, then L.findDuplicates() returns {1, 4}.

import java.util.Iterator; import java.util.NoSuchElementException; public class LinkedListWrapper2 { public static interface List extends Iterable { public int size(); public boolean isEmpty(); public boolean isMember(E e); public int firstIndexOf(E e); public int lastIndexOf(E e); public void add(E e); public void add(E e, int index); public E get(int index); public E remove(int index); public boolean remove(E e); public int removeAll(E e); public E replace(int index, E newElement); public void clear(); public Object[] toArray(); public List findDuplicates(); } public static class SinglyLinkedList implements List { @SuppressWarnings("hiding") private class SinglyLinkedListIterator implements Iterator{ private Node nextNode; @SuppressWarnings("unchecked") public SinglyLinkedListIterator() { this.nextNode = (Node) header.getNext(); } @Override public boolean hasNext() { return nextNode != null; } @Override public E next() { if (this.hasNext()) { E result = this.nextNode.getElement(); this.nextNode = this.nextNode.getNext(); return result; } else { throw new NoSuchElementException(); } } } private static class Node { private E element; private Node next; public Node(E element, Node next) { super(); this.element = element; this.next = next; } public Node() { super(); } public E getElement() { return element; } public void setElement(E element) { this.element = element; } public Node getNext() { return next; } public void setNext(Node next) { this.next = next; } } private Node header; private int currentSize; public SinglyLinkedList() { this.header = new Node<>(); this.currentSize = 0; } @Override public int size() { return this.currentSize; } @Override public boolean isEmpty() { return this.size() == 0; } @Override public boolean isMember(E e) { return this.firstIndexOf(e) >= 0; } @Override public int firstIndexOf(E e) { int i = 0; for (Node temp = this.header.getNext(); temp != null; temp = temp.getNext(), ++i) { if (temp.getElement().equals(e)) { return i; } } // not found return -1; } @Override public void add(E e) { if (this.isEmpty()) { this.header.setNext(new Node(e, null)); this.currentSize++; } else { Nodetemp= this.header.getNext(); while (temp.getNext() != null) { temp = temp.getNext(); } Node newNode = new Node<>(e, null); temp.setNext(newNode); this.currentSize++; } } @Override public void add(E e, int index) { if ((index < 0) || (index > this.currentSize)) { throw new IndexOutOfBoundsException(); } if (index == this.currentSize) { this.add(e); } else { Node temp = null; if (index == 0) { temp = this.header; } else { temp = this.getPosition(index -1); } Node newNode = new Node<>(); newNode.setElement(e); newNode.setNext(temp.getNext()); temp.setNext(newNode); this.currentSize++; } } @Override public E get(int position) { if ((position < 0) || position >= this.currentSize) { throw new IndexOutOfBoundsException(); } Node temp = this.getPosition(position); return temp.getElement(); } private Node getPosition(int index){ int currentPosition=0; Node temp = this.header.getNext(); while(currentPosition != index) { temp = temp.getNext(); currentPosition++; } return temp; } @Override public E remove(int index) { if ((index < 0) || (index >= this.currentSize)){ throw new IndexOutOfBoundsException(); } else { Node temp = this.header; int currentPosition =0; Node target = null; while (currentPosition != index) { temp = temp.getNext(); currentPosition++; } E result = null; target = temp.getNext(); result = target.getElement(); temp.setNext(target.getNext()); target.setElement(null); target.setNext(null); this.currentSize--; return result; } } @Override public E replace(int position, E newElement) { if ((position < 0) || position >= this.currentSize) { throw new IndexOutOfBoundsException(); } Node temp = this.getPosition(position); E result = temp.getElement(); temp.setElement(newElement); return result; } @Override public void clear() { while(!this.isEmpty()) { this.remove(0); } } @Override public Object[] toArray() { Object[] result = new Object[this.size()]; for (int i=0; i < this.size(); ++i) { result[i] = this.get(i); } return result; } @Override public Iterator iterator() { return new SinglyLinkedListIterator(); } @Override public int lastIndexOf(E e) { int i = 0, result = -1; for (Node temp = this.header.getNext(); temp != null; temp = temp.getNext(), ++i) { if (temp.getElement().equals(e)) { result = i; } } // not found return result; } @Override public boolean remove(E e) { int i = this.firstIndexOf(e); if (i < 0) { return false; }else { this.remove(i); return true; } } @Override public int removeAll(E e) { int count = 0; while (this.remove(e)) { count++; } return count; } @Override public List findDuplicates() { // ADD YOUR CODE HERE } } }

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

The Database Experts Guide To Database 2

Authors: Bruce L. Larson

1st Edition

0070232679, 978-0070232679

More Books

Students also viewed these Databases questions