Practice: DoubleLinkedList

Take out a piece of paper. We’ll be programming on paper.

Problem 1

• What are the steps (psuedo code) to add an item at index and to remove an at index:

public class DLinkedList<E> implements List211<E> {
  /** Holds the head of the list. */
  private DLinkedNode<E> head;
  /** The size of the list. */
  private int size;

  // Your steps go here.

  /** Doubly linked node. */
  private class DLinkedNode<E> {
    E data;
    DLinkedNode<E> next;
    DLinkedNode<E> prev;
  }
}

Problem 2

• Answer the following questions:

  • What is the Big-O of the add(E item) method? Why?

  • What is the Big-O of the remove(int index) method? Why?

Show me your code before you leave