Question

Create an ExtLinkedList class by extending the LinkedList class to include the following methods and estimate the run-time complexity of each method.

3. public ExtLinkedList evenList()

// gets the elements E in locations 0,2,4,6,… of this list and puts them in a new ExtLinkedList in that order and returns it

// make sure to handle errors

4. public ExtLinkedList intsersect (ExtLinkedList eli)

// picks out elements that are common to this ExtLinkedList and eli

// and returns them in the form of a new ExtLinkedList

// once again, you can use equals () method // the new list should not have duplicate elements

// handle errors or exceptional situations appropriately.

// example: this: {1,3,4,4}, parameter : {1,4,5,7} then return {1,4}

Answer 1

Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. Thanks

// ExtLinkedList.java

import java.util.Iterator;

import java.util.LinkedList;

public class ExtLinkedList<T> extends LinkedList<T> {

      // returns the elements in even indices as a new list

      // runtime complexity is O(n) since this will loop through the list once

      public ExtLinkedList<T> evenList() {

            // creating a new list

            ExtLinkedList<T> result = new ExtLinkedList<T>();

            // getting an iterator for this list

            Iterator<T> it = iterator();

            int i = 0;

            // looping through each object

            while (it.hasNext()) {

                  // getting element

                  T element = it.next();

                  // if i is even, adding to result

                  if (i % 2 == 0) {

                        // this will take O(1) time

                        result.addLast(element);

                  }

                  i++;

            }

            return result;

      }

      // returns the intersection of this list and another

      // The runtime complexity is O(n^2) or O(2n^2) (I'm not really sure since in

      // every iteration of the loop, it will use O(n) time for checking if

      // element exist on other list and O(n) time for checking if the element

      // exist on result list (to avoid duplication))

      public ExtLinkedList<T> intsersect(ExtLinkedList<T> eli) {

            if (eli == null) {

                  // invalid parameter

                  return null;

            }

            ExtLinkedList<T> result = new ExtLinkedList<T>();

            // getting an iterator and looping through the list

            Iterator<T> it = iterator();

            while (it.hasNext()) {

                  T element = it.next();

                  // if this element exist on other list and not added before, adding

                  // it to result

                  if (eli.contains(element) && !result.contains(element)) {

                        result.addLast(element);

                  }

            }

            return result;

      }

}