QuestionQuestion

1. What is the time complexity for the following operations in an ordered list that is implemented with links, and an ordered list that is implemented with arrays, respectively? For each method, answer for both implementations.
a. add()
b. remove()
c. removeFirst()
d. removeLast()
e. Find the middle of the list, for instance, if a given list (say 1,2,3,4,5) contains an odd number of items, then the output should be:

2. Implement a generic circular un-ordered linked list, where the next field of the last node is pointing to the first node of the list.
Requirements:
a. Complete all the List ADT operations
b. Add a function to the class called getMiddle(), which returns the middle element of the list (returning the second middle element if there are an even number of elements in the list). Throw the EmptyCollectionException if the list is empty.
c. Create a linked list instance of Integers with this class and insert the following numbers to the list: 10, 23, 34, 14, 55, 100, 75, and then print the middle of this list with the added function.
d. Add a function to the class called getAfter(T target), which finds the first occurrence of the parameter target in the list and returns the element immediately after target. Because it is a circular list, note that if the parameter target is the last element in the list, then the return value should be the first element in the list. Use getAfter with the list you created in part (c). Verify that getAfter(34) returns 14 and getAfter(75) returns 10.

Solution PreviewSolution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

public class LinearNode<E> {

    private LinearNode<E> next;
    private E element;

    /**
    * Creates an empty node.
    */
    public LinearNode() {
       next = null;
       element = null;
    }

    /**
    * Creates a node storing the specified element.
    *
    * @param elem the element to be stored within the new node
    */
    public LinearNode(E elem) {
       next = null;
       element = elem;
    }

    /**
    * Returns the node that follows this one.
    *
    * @return the node that follows the current one
    */
    public LinearNode<E> getNext() {
       return next;
    }

    /**
    * Sets the node that follows this one.
    *
    * @param node the node to be set to follow the current one
    */
    public void setNext(LinearNode<E> node) {
       next = node;
    }

    /**
    * Returns the element stored in this node.
    *
    * @return the element stored in this node
    */
    public E getElement() {
       return element;
    }

    /**
    * Sets the element stored in this node.
    *
    * @param elem the element to be stored in this node
    */
    public void setElement(E elem) {
       element = elem;
    }
}...

By purchasing this solution you'll be able to access the following files:
Solution.zip.

50% discount

Hours
Minutes
Seconds
$50.00 $25.00
for this solution

or FREE if you
register a new account!

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Data Structures and Algorithms Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats