Chapter 16, Problem 7PP

Program Plan Intro

Circular doubly-linked list

Program plan:

• In a file “ListIterator.java”, create an interface “ListIterator”,
  • Declare the method “next()” that moves the iterator past the next element.
  • Declare the method “hasNext()” that check if there is an element after the iterator position.
  • Declare the method “previous()”.
  • Declare the method “hasPrevious()”.
  • Declare the method “add()”  that adds an element before the position of the iterator and moves the iterator past the added element.
  • Declare the method “remove()” that removes the last traversed element.
  • Declare the method “set()” to set the last traversed element to a previous value.
• In a file “LinkedList.java”, import the package and create a class “LinkedList”,
  • Declare two object variables of type “Node”.
  • Define the constructor to create an empty linked list.
  • Define the method “getFirst()” that returns the first element in the linked list.
  • Define the method “removeFirst()” to remove the first element in the linked list.
  • Define the method “addFirst()” that adds an element to front of the linked list.
  • Define the method “getLast()” that returns an element last in the linked list.
  • Define the method “removeLast()” that removes an element present last in the linked list.
  • Define the method “addLast()” that adds an element to the last in the linked list.
  • Define the method “listIterator()” of type “ListIterator”, that returns an iterator for iterating through the list.
  • Create a class “Node”,
    • Declare the object variable for “Object”, and “Node”.
      • Create a class “LinkedListIterator”,
        • Declare the necessary object variables.
        • Declare the necessary Boolean variables.
        • Define the constructor to create an iterator that points to the front of the linked list.
        • Define the method “next()”,
        • • If there is no next element then throws an exception.
          • Set the Boolean values to the Boolean variables.
          • Check if position is null, set the first element to the position.
          • Otherwise, set the next position to the current position.
          • Returns the value at the position.
        • Define the method “hasNext()” that check whether there is an element after the iteration and before the starting of the list.
        • Define the method “add()”,
        • • If position is null,
            • Returns the value.
              • Otherwise,
                • Returns the value.
        • Define the method “previous()”,
        • • Check if there is any previous element,
            • Throws an exception.
              • Assign the Boolean value to the Boolean variables.
              • Check the condition,
                • Set the null value to the position.
        • Define the method “hasPrevious()”,
        • • Returns the Boolean value.
        • Define the method “add()”,
        • • If position is null,
            • Call the method “addFirst()”.
            • Set the first to the position.
              • Check the condition,
                • Call the method “addLast()”.
                • Assign the value.
              • Otherwise,
                • Create a new node.
                • Set the value to the new node.
                • Set the next position to the next pointer of new node.
                • Assign the new node value to the previous of the new next node value.
                • Assign the new node value to the next position.
                • Assign the position to the previous of the new node.
                • Assign the new node to the position.
              • Assign the Boolean values to the Boolean variables.
        • Define the method “remove()”,
        • • Assign the value returned from the method “lastPosition()” to the position.
          • Check the condition,
            • Call the method “removeFirst()”.
              • Otherwise, check another condition,
                • Call the method “removeLast()”.
              • Otherwise,
                • Assign the value at the next position to the value at the next of the previous position.
                • Assign the value at the previous position to the previous of the next position.
              • Check if there is an element after the next position,
                • Assign the value at the previous position to the current position.
              • Assign the Boolean values to the Boolean variables.
        • Define the method “set()”,
        • • Assign the value returned from the method “lastPosition()”.
          • Assign the value.
        • Define the method “lastPosition()” that returns the last node iterated by the iterator if there was not an immediately preceding call to previous or next.
• In a file “ListTest.java”, create a class “ListTest”,
  • Define the “main()” method.
    • Create “LinkedList” object.
    • Get and print the number of fields in a circular list.
    • Print the expected result.
    • Call the method “addFirst()”.
    • Call the method “addFirst()”.
    • Call the method “addLast()”.
    • Print he value returned from the method “getFirst()”.
    • Print the expected result.
    • Print the value obtained from the method “getLast()”.
    • Print the expected result.
    • Call the method “removeLast()”.
    • Print the result obtained from the method “getLast()”.
    • Print the expected result.
    • Call the method “removeFirst()”.
    • Print the value returned from the method “getFirst()”.
    • Print the expected result.
    • Call the method “addFirst()”.
    • Assign the value returned from the method “listIterator()”.
    • Print the value returned from the method “hasNext()”.
    • Print the expected result.
    • Call the method “next()”
    • Print the value obtained from the method “hasNext()”.
    • Print the expected result.
    • Print the value returned from the method “hasPrevious()”.
    • Print the expected result.
    • Print the value returned from the method “next()”.
    • Print the expected result.
    • Print the value returned from the method “previous()”.
    • Print the expected result.