Lab 6: List Practice, Reading

You've implemented a LinkedList<E>, and now its time to demonstrate that you know how to use it. This is a paper-based set of questions—that means you should work your problems out on paper, present your solutions to me in a 1-on-1 meeting, and answer any questions that I might have about your implementation.

It isn't massive in scope, but it represents the end of our dealings with lists (but not linked structures in general). After you're done, it's time for some reading.

Following the Natural Recursion

If you want to implement your solutions in a naturally recursive way, assume that your LinkedList<E> implementation has the following constructor and methods (not tested... should be close to correct):


// This lets us construct non-empty lists.

// Contrast with setting first = null.

public LinkedList<E>(ListNode<E> ln) {

  first = ln;

}


// Returns the first item in the list.

public E first() {

  if (first != null) {

    return (E)first.getItem();

  } else { ... exception ... }

}


public LinkedList<E> rest() {

  // Constructs a new, non-empty LinkedList<E>

  // beginning with the second node.

  if (first != null)

    return new LinkedList<E>(first.getNext());

  } else { ... exception ... }

}


[ WARNING ] The above implementation of rest() has a fundamental problem, and in practice would cause huge problems! Can you figure out what that problem is? (Conceptually, it works just fine.) 


These methods let you write code that using the LinkedList<E> like the following:

public int listSize(LinkedList<E> ls) {

  if (ls.first() == null) {

    return 0;

  } else { 

    return 1 + listSize(ls.rest());

}

This may look like your size() implementation, but instead of being written as a method of the class in terms of ListNode<E> objects, this is written as an external method in terms of LinkedList<E>s.

As always, you may write your solutions in terms of loops. However, all of these can be written if you follow the definition of a list.

List Questions

Assuming you are given a LinkedList<E> class like the one you have recently implemented (and those extensions noted above), write methods that match the following signatures and descriptions. (Assume that these are all being implemented in a driver class called ListQuestions, not in the LinkedList<E> class itself.)

  1. public int count(LinkedList<Integer>, Integer target)

    Write the method count() so that it takes a list and an integer, and returns the number of times that Integer appears in the list.

  2. public LinkedList<E> append(LinkedList<E> ls1, LinkedList<E> ls2) 

    Write the method append(); it should consume two lists and return a list that is the combination of the two lists.

  3. public boolean member(LinkedList<E> ls, E target)

    Write the method member(); it should consume a list and a target, and return true if the list contains that element.

  4. public LinkedList<E> removeDupes(LinkedList<E> ls)

    Write a method that, given a list, returns a new list that is free of duplicates. You may use member() in your solution.

  5. public LinkedList<E> reverse(LinkedList<E> ls)

    Write a method that returns the reverse of a list.


All of these questions have naturally recursive solutions. You are discouraged from using each-other as resources. Challenge yourself with these questions, and feel free to ask me for advice (via email, etc.) as needed.

Algorithmic Analysis

After you're done having fun with recursion, read chapter seven in Drake.

Creative Commons License Creative Commons BY-NC-SA 3.0 Licensed where possible.