Chapter 12, Problem 9PP

Program Plan Intro

Doubly linked list

Program Plan:

“DoublyLinkedList.java”:

• Define “DoublyLinkedList” class.
  • Declare required variables.
  • Default constructor for “DoublyLinkedList” class.
  • Define the method “length”.
    • Declare required variable.
    • Check condition using “while” loop.
    • Return the result of count value
  • Define “addANodeToStart” method.
    • Declare variable by using “ListNode” class.
    • Assign value to head.
    • If tail is null, then assign tail to head.
    • If old head is not null, then set the values to link value at head and previous value at old head node.
  • Define “getDataAtCurrent” method.
    • If current is not null, then returns the data at current.
    • Otherwise, display the given error message.
    • Finally returns the null value.
  • Define “resetIteration” method.
    • This method is used to set current to head.
  • Define “moreToIterate” method.
    • This method is used to return the result of “current != null”.
  • Define “goToNext” method.
    • If current is not null, then set current value to link value at current.
    • If head is not null, then display given message.
  • Define “goToPrevious” method.
    • If current is not null, then set current to previous value at current.
    • If head is not null, then display given error statement.
  • Define “insertNodeAfterCurrent” method.
    • Declare required variables.
    • If tail is equal to current, then set tail to new node.
    • If current is not null, then set given values to given variables.
      • If the link value at new node is not null, then set the value to new node.
        • If the value of head is not null, then display given error message.
  • Define “deleteCurrentNode” method.
    • Declare variable using “ListNode” class.
    • If tail is equal to current and current is not null, then set tail to previous value at current node.
    • If current and previous value at current node is not null, then set values for given variables.
    • If current is not null and previous value at current node is null, then set values for head node.
    • Otherwise, that is if current is equal to null, then display error message.
  • Define “deleteHeadNode” method.
    • If tail is equal to head, then set tail to null.
    • If head is not null, then assign values for head.
    • Otherwise, display error message.
  • Define “findInList” method.
    • Declare required variables.
    • Check condition using “while” loop.
      • Get the data position by calling the method “getData” and then store it to a variable “data_position”.
      • If the position of data is equals to target node, then set “current” to “location” and then return true.
      • Then get the location by calling the method “getLink”.
        • Finally assign the “current” to “null” and return “false”.
  • Define “onList” method.
    • This method returns the result of “Find(target_node) != null”.
  • Define “Find” method.
    • Declare required variables.
    • Check condition using “while” loop.
  • Define “showList” method.
    • Declare required variables.
    • Display the data at each location using “while” loop.
  • Define “displayListValues” method.
    • This method is used to return the values in head, current, tail and number of items in list.
  • Define node class “ListNode”.
    • Declare required variables
    • Define constructor for “ListNode” class.
    • Define parameterized constructor for “ListNode” class.
    • Define set and get method for data and link.

“DoublyLinkedListTest.java”:

• Define “DoublyLinkedListTest” class.
  • Define main function.
  • Assign result to “false”.
  • Create an object for “DoublyLinkedList” class.
  • Display the values in list by calling the method “displayListValues”.
  • Add a name “John” to “nameList” by calling the method “addANodeToStart”.
  • After adding, display the values in list by calling the method “displayListValues”.
  • Reset the iteration for given list by calling the method “resetIteration”.
  • Add a name “Merry” to “nameList” by calling the method “addANodeToStart”.
  • After adding, display the values in list by calling the method “displayListValues”.
  • Go to next node by calling the method “goToNext”.
  • Add a name “Rose” to “nameList” by calling the method “addANodeToStart”.
  • After adding, display the values in list by calling the method “displayListValues”.
  • Display the list by calling “showList” method.
  • Reset the iteration for given list by calling the method “resetIteration”.
  • Go to next node by calling the method “goToNext”.
  • After adding, display the values in list by calling the method “displayListValues”.
  • Add a name “Jansi” to “nameList” by calling the method “addANodeToStart”.
  • After adding, display the values in list by calling the method “displayListValues”.
  • Display the list by calling “showList” method.
  • Go to next node by calling the method “goToNext”.
  • Delete first node by calling “deleteHeadNode” method.
  • After deleting, display the list by calling “showList” method.
  • Go to next node by calling the method “goToNext”.
  • Add a name “Rosie” to “nameList” by calling the method “addANodeToStart”.
  • Go to next node by calling the method “goToNext”.
  • Add a name “Joshph” to “nameList” by calling the method “addANodeToStart”.
  • After adding, display the values in list by calling the method “displayListValues”.
  • Display the list by calling “showList” method.
  • Go to previous node by calling the method “goToPrevious”.
  • Display the values in list by calling the method “displayListValues”.
  • Display the list by calling “showList” method.
  • Go to previous node by calling the method “goToPrevious”.
  • Get the current node by calling the method “getDataAtCurrent”.
  • Delete node at current by calling the method “deleteCurrentNode”.
  • After deleting, display the values in list by calling the method “displayListValues” and method “showList”.
  • Add a name “Jack” to beginning of “nameList” by calling the method “addANodeToStart”.
  • After deleting, display the values in list by calling the method “displayListValues” and method “showList”.
  • Iterate to the end of list using “while” loop. After iterating, display the values in list by calling the method “displayListValues”.
  • Iterate the list in reverse by calling “resetIterationReverse” method.
  • After reverse iteration, display the values in list by calling the method “displayListValues”.
  • Delete the current node by calling “deleteCurrentNode” method.
  • After deleting current node, display the values in list by calling the method “displayListValues” and method “showList”.
  • Check if “Rose” is found in list or not by calling “findInList” method. If the given name found, then display the message “Found”. Otherwise, display “Not found”.
  • After performing check condition, display the values in list by calling the method “displayListValues” and method “showList”.
  • Check if “Josph” is found in list or not by calling “findInList” method. If the given name found, then display the message “Found”. Otherwise, display “Not found”.
  • After performing check condition, display the values in list by calling the method “displayListValues” and method “showList”.