CSE 214 Computer Science II (Spring 2015)

RECITATION 4 – Linklist

Objective:

1. To work with Linklist
2. Analyze the complexity of various operations on Linklist

1. [30 minutes] The SinglyLinkedList class has head and tail instance variables that point, respectively, to the head and tail of a linked list. The  SinglyLinkedList  class has element variables that store the value associated with the node and a reference to the next  node in the list. Write the following methods of the SinglyLinkedList class and analyze their time complexity:

link: http://www3.cs.stonybrook.edu/~sael/teaching/cse214/rec/LinkedList.java

a) public T getMin(): returns the minimum value in the list.Print a message if the list is empty.

       c) void add(int index, T value): add the node after the node at the location, index. Assume index value is valid.

       d)  public T  removeTail(): removes and returns the element value at the tail of the list. Print a message if the list is empty.     

2. [20 min] Implement the equals() method in DoublyLinkedList class, assuming that the two list are equal if they have the same sequence of elements. Also analyze complexiy.

link: http://www3.cs.stonybrook.edu/~sael/teaching/cse214/rec/DoublyLinkedList.java