The Sorted List ADT Implement the SortedList class. The SortedList class extends

Question

The Sorted List ADT

Implement the SortedList class. The SortedList class extends
the List class. Both can be seen here. Need to
implement (recursively) all of the abstract methods of the List class.
They are:

-insert (recursive)

-iterator

-remove (recursive)

-retrieve (recursive)

-search (recursive)

You must also implement an Iterator inner class for the
SortedList class. You must submit a modified SortedList.java
file with your source code. Do not submit and do not modify
the List.java file.

List.java public abstract class List implements Iterable protected class NodT protected Node (T data) ( this.datadata; protected T data; protected Node next; public abstract void insert E data) public abstract void remove(E data) public abstract E retrieve(int index) public abstract boolean search(E data); protected NodeE> head; SortedList.javia public class SortedListcE extends Comparable

Explanation / Answer

SortedList.java

import java.util.Iterator;

public class SortedList<E extends Comparable<? super E>> extends List<E> {

    public void insert(E data) {
        head = insert(head, new Node<>(data));
    }

    private Node<E> insert(Node<E> cur, Node<E> node) {
        if (cur == null) return node;
        if (node.data.compareTo(cur.data) < 0) {
            node.next = cur;
            return node;
        }
        cur.next = insert(cur.next, node);
        return cur;
    }

    public void remove(E data) {
        head = remove(head, data);
    }

    private Node<E> remove(Node<E> cur, E data) {
        if (cur == null) return null;
        if (data.compareTo(cur.data) == 0) return cur.next;
        cur.next = remove(cur.next, data);
        return cur;
    }

    public E retrieve(int index) {
        return retrieve(head, 0, index);
    }

    private E retrieve(Node<E> cur, int i, int index) {
        if (i <= index) return cur == null ? null : cur.data;
        return retrieve(cur.next, i + 1, index);
    }

    public boolean search(E data) {
        return search(head, data);
    }

    private boolean search(Node<E> cur, E data) {
        if (cur == null) return false;
        if (data.compareTo(cur.data) == 0) return true;
        return search(cur.next, data);
    }

    public Iterator<E> iterator() {
        return new Iterator<E>() {
            private Node<E> cur = head;
            public boolean hasNext() {
                return cur != null;
            }
            public E next() {
                E next = cur.data;
                cur = cur.next;
                return next;
            }
        };
    }
}

List.java

public abstract class List<E> implements Iterable<E> {

    protected class Node<T> {

        protected Node(T data) {
            this.data = data;
        }

        protected T data;
        protected Node<T> next;
    }

    public abstract void insert(E data);
    public abstract void remove(E data);
    public abstract E retrieve(int index);
    public abstract boolean search(E data);

    protected Node<E> head;
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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