CS111 Lab 9
Linked Lists


Part I: Understanding Linked Lists
  1. What is a linked list and how is it similar to an array or an ArrayList?
  2. How is a linked list different from an array or an ArrayList?
  3. Why is an array and an ArrayList inefficient?
  4. What are the pros and cons of linked lists?



Part II: Using the LinkedList class
NOTES:
      Creating a basic linked list can be done by using the LinkedList class provided by the Java library. This class is part of the java.util package. It is a generic class, just like the ArrayList class.
    1. Creating a linked list requires a generic class.

    2. Provide an iterator for visiting list elements.

    3. LinkedList methods:
      addLast()
      addFirst()
      getFirst()
      getLast()
      removeFirst()

    4. The LinkedList class also inherits the methods of the collection interface.
      size()
      add()
      toString()
      contains()

    5. You can use the for each loop with any collection. Example:
      for (Integer c:list) System.out.println(c);

    6. You can use methods of the Iterator and ListIterator Interfaces. next()
      previous()
      hasNext()
      hasPrevious()
      set()
      add()
      remove()


Exercise 1
    Task 1: Create the linked list shown below.
    Task 2: Create an iterator and position it after the third number in the list. Insert the number 4 at this position.
    Task 3: Remove the number 5 from the list. You will need to reposition the iterator.
    Task 4: Display the new contents of the linked list.



Exercise 2:
    The visual below is a double linked list.
    Every node has two links, one points to the next node and one points to the previous node.
    This type of linked list can be traversed in either direction.
    Write the code to produce the list shown in the figure below.





Part III: Implementing a linked list class: Linked
  1. Create a node class.
    Use Object to represent the data.
    Construct a reference to the next node.

  2. Write the code to produce the list shown in the figure below.
    TIP: The head reference to a linked list is usually fixed. It should only point to the first node in the list.




  3. Write the code to produce the list shown in the figures below.
    TIP: The head and last pointers are not part of the actual list. The actual list elements are between the header and trailer nodes.





  4. Write the code to produce the list shown in the figure below.




  5. Write code fso that the node with n = 2.0 is inserted between node 1.0 and node 4.0. See the figure below.
  6. Delete the first node in the list.




  7. Implement a class for the linked list. In this example, the class will be called Linked.


Part IV: Add a method to the Linked class that locates a specified node and deletes it.
    Use the following Test class to test your implementation.


public class Test {
    public static void main(String[] args) {
      // TASK 1: CREATE AN EMPTY LINKED LIST
      Linked students = new Linked();

      //TASK 2: ADD STUDENTS TO THE LIST
      students.addNode("Roger", "Baca", 70);
      students.addNode("Suzy", "Davis", 98);
      students.addNode("Bobo", "Green", 50);
      students.addNode("Cat", "Ling", 85);
      students.addNode("Ken", "Molich", 99);
      students.display();

      //TASK 3: SEARCH FOR A GRADE AND DELETE THE FIRST NODE MATCH
      System.out.println();
      students.deleteNode(85);
      students.display();
    }
}