Chapter 16, Problem 8PE

Program Plan Intro

Reimplementation of “LinkedList” class

Program plan:

• In a file “LinkedList.java”, import necessary packages and create a class “LinkedList” that extends “AbstractSequentialList”,
  • Declare the object variable.
  • Declare the necessary variable.
  • Define the constructor to create an empty linked list.
  • Define the method “size()” to return the linked list size,
    • Returns the size.
  • 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 the front of the linked list,
    • Create a new node.
    • Assign the value to the new node.
    • Assign the first element to the next pointer of new node.
    • Assign new node to the first position.
    • Increment the size.
  • Define the method “listIterator()” of type “ListIterator”, with an argument “n”,
    • Create an object for “LinkedListIterator”.
    • Execute  a loop till the value becomes “0”,
      • Call the method “next()”
      • Decrement the value.
  • Create a class “Node”,
    • Declare the object variable for “Object”, and “Node”.
  • Create a class “LinkedListIterator”,
    • Declare the necessary object variables.
    • Declare the necessary 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.
      • Assign the position to the front of the linked list.
      • Check if position is null, set the first element to the position.
      • Otherwise, set the next position to the current position.
      • Increment the index.
      • Returns the value.
        • Define the method “hasNext()” that check whether there is next element,
        • • Check if position is null,
            • Returns true if first reference is not null.
          • Otherwise,
            • Returns true, if the next reference of the position is not null.
        • Define the method “add()”,
        • • If position is null, call the method “addFirst()”.
            • Set the first to the position.
          • Otherwise, create a new node.
            • Assign the element to the new node.
            • Set the next position to the next pointer of the new node.
            • Set the new node value to the next position.
            • Set the new node as the position.
            • Increment the size.
          • Set the Boolean value to false.
        • Define the method “remove()”,
        • • If the boolean value is false, throws an exception.
          • If position is same as the first, calls the method “removeFirst()”.
          • Otherwise,
            • Set the next position to the previous position.
            • Set the Boolean value to false.
            • Decrement the size.
          • Set the previous to the positions.
        • Define the method “set()”,
        • • If the Boolean value is false, throws an exception.
          • Set the value to the position.
        • Define the method “previousIndex()”,
        • • Return the previous of the current index.
        • Define the method “nextIndex()”,
        • • Returns the next index.
        • Define the method “previous()”,
        • • Throws an exception.
        • Define the method “hasPrevious()”,
        • • Returns false.
• In a file “SizeTest.java”, create a class “SizeTest”,
  • Define the “main()” method.
    • Create the “LinkedList” object.
    • Call the method “add()” to add the element “Tom”.
    • Print the actual and expected size.
    • Call the method “clear()”.
    • Print the actual and expected size.
    • Initialize the string array.
    • Add all the elements of string array into the list.
    • Print the actual and expected size.
    • Print the string representation of linked list.
    • Print the expected output.
    • Print the actual output for the function call “get(2)”.
    • Print the expected output.
    • Create list iterator.
    • Print he actual and expected output for the function call “next()”.