API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Jul 21st, 2017
477
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 17.99 KB | None | 0 0
raw download clone embed print report
  1.  
  2. /**
  3.  * LinkedList
  4.  *
  5.  * Many thanks to the inspectors who vastly improved this document.  It
  6.  * has been made a much better product as a result.
  7.  *
  8.  * This code implements the following features:
  9.  * Head and Tail - This list accurately keeps track of both head and tail
  10.  * Doubly Linked List - The nodes support a notion of containing pointers
  11.  *    that aim to the next node and the previous node.
  12.  * The concept of a "Current" Pointer - that node we're
  13.  *     currently aimed at is supported by an intNode class that maintains
  14.  *     both forward and backward pointers.
  15.  * Here are the properties of the Current Pointer:
  16.  *  -- The Current Pointer can be in a number of states.  These states
  17.  *     will be represented by an integer when the method
  18.  *     getCurrentPointerState() asks for the state of the Current Pointer,
  19.  *     represented in a particular way, but internally the states may be
  20.  *     represented in any fashion desired.
  21.  *     The states are:
  22.  *           Head - this state means that the Current Pointer is at the
  23.  *                  head of the list - it is NOT at the first node.
  24.  *           Tail - this state means that the Current Pointer is at the
  25.  *                  tail of the list - it is NOT at the last node.
  26.  *           Node Position - The Current Pointer has a state that's
  27.  *                  represented as the position of a node on the list.
  28.  *    For instance if  head --> NodeID=3 --> NodeID=4  --> null
  29.  *    Then when Current Pointer = 2, it represents the node with ID = 4.
  30.  *    Note use of the word "represents" rather than "points to" describe
  31.  *    this state.
  32.  *
  33.  *  -- The Current Pointer supports sequential access;  the Current
  34.  *     Pointer can be moved to a new state by using the methods
  35.  *         setCurrentAtHead()
  36.  *         setCurrentAtTail()
  37.  *         setCurrentToNext()
  38.  *         setCurrentToPrevious()
  39.  *     and the state of Current Pointer can be determined with
  40.  *         getCurrentPointerState()
  41.  *
  42.  *  Additional properties of the linked list, as exemplified by
  43.  *  its methods, include these:
  44.  *         addNodeAfterCurrent()
  45.  *         getNodeAtCurrent()
  46.  *         removeNodeAtCurrent()
  47.  *         getListLength()
  48.  *         printLinkedList()
  49.  *         sort()
  50.  *         getNodeVersion()
  51.  *
  52.  *  All these methods are described below.
  53.  *
  54.  *  Pre-Release  February 23, 2010
  55.  *  Inspected on February 25, 2010 by students in CS121
  56.  *  Released for use on February 26, 2010.
  57.  *  Authors Alex Bird, J. Breecher
  58.  **/
  59. public class LinkedList {
  60.  
  61.     IntNode head = null;
  62.     IntNode tail = null;
  63.     int CurrentPosition = -1;
  64.  
  65.     /**
  66.      * Constructor - defines a linked list with no nodes on the list
  67.      * @param none </CODE>
  68.      * <dt><b>Postcondition:</b><dd>
  69.      *   There are no nodes placed on the Linked List by this constructor.
  70.      *   The Current Pointer is set to the state -head-
  71.      **/
  72.     public LinkedList() {
  73.         // Code will be added here by students
  74.         head = null;
  75.         tail = null;
  76.         CurrentPosition = -1;
  77.  
  78.     }
  79.  
  80.     /**
  81.      * Sets the Current Pointer to the head of the Linked List
  82.      * @param None
  83.      * <dt><b>Postcondition:</b><dd>
  84.      *   The Current Pointer is set in the state -head-
  85.      **/
  86.     public void setCurrentAtHead() {
  87.         // Code will be added here by students
  88.         CurrentPosition = -1;
  89.     }
  90.  
  91.     /**
  92.      * Sets the Current Pointer to the tail of the Linked List
  93.      * @param none </CODE>
  94.      * <dt><b>Postcondition:</b><dd>
  95.      *   The Current Pointer is set in the state -tail-
  96.      **/
  97.     public void setCurrentAtTail() {
  98.         // Code will be added here by students
  99.         CurrentPosition = -2;
  100.     }
  101.  
  102.     /**
  103.      * Sets the Current Pointer to the state of the next node on the List
  104.      * @param None
  105.      * <dt><b>Postcondition:</b><dd>
  106.      *  If Current Pointer has a state such that it can be legally moved,
  107.      *      it is placed in a state representing the next node
  108.      *      on the list.
  109.      *  If the result of advancing the Current Pointer would be to
  110.      *      position it after the last node, then the Current Pointer is
  111.      *      not moved but remains in its current state.
  112.      * If the Current Pointer is -head- , and there are nodes on the
  113.      *      list, then the Current Pointer takes on a state representing
  114.      *      the first node on the list.
  115.      * If the Current Pointer is -tail- , then the Current Pointer
  116.      *      is not legally moved.
  117.      * @return
  118.      *  If Current Pointer has been legally moved, then return true.
  119.      *      otherwise return false.
  120.      **/
  121.     public Boolean setCurrentAtNext() {
  122.         // Code will be added here by students
  123.  
  124.         if (CurrentPosition == -1 && getListLength() > 0) {
  125.             CurrentPosition = 1;
  126.             return true;
  127.         }
  128.         if (CurrentPosition == -2) {
  129.             return false;
  130.         }
  131.         if (CurrentPosition >= 0 && CurrentPosition < getListLength()) {
  132.             CurrentPosition++;
  133.             return true;
  134.         } else {
  135.             return false;
  136.         }
  137.     }
  138.  
  139.     /**
  140.      * Sets the Current Pointer to the state of the previous node on the List
  141.      * @param none </CODE>
  142.      * <dt><b>Postcondition:</b><dd>
  143.      *  If Current Pointer has a state such that it can be legally moved,
  144.      *      it is placed in a state representing the previous node
  145.      *      on the list.
  146.      *  If the result of "backwarding" the Current Pointer would be to
  147.      *      position it before the last node, then the Current Pointer is
  148.      *      not moved but remains in its current state.
  149.      * If the Current Pointer is -tail- , and there are nodes on the
  150.      *      list, then the Current Pointer takes on a state representing
  151.      *      the last node on the list.
  152.      * If the Current Pointer is -head- , then the Current Pointer
  153.      *      is not legally moved.
  154.      * @return
  155.      *  If Current Pointer has been legally moved, then return true.
  156.      *      otherwise return false.
  157.      **/
  158.     public Boolean setCurrentAtPrevious() {
  159.         // Code will be added here by students
  160.  
  161.         if (CurrentPosition == -2 && getListLength() > 0) {
  162.             CurrentPosition = getListLength();
  163.             return true;
  164.         }
  165.         if (CurrentPosition == -1) {
  166.             return false;
  167.         }
  168.         if (CurrentPosition > 1) {
  169.             CurrentPosition--;
  170.             return true;
  171.         } else {
  172.             return false;
  173.         }
  174.  
  175.  
  176.     }
  177.  
  178.     /**
  179.      * Returns the state of the Current Pointer.  State means one of the
  180.      *   states that the pointer can occupy.
  181.      *   See the initial comments for this class to see the possible
  182.      *   states.
  183.      * <dt><b>Postcondition:</b><dd>
  184.      *   The Current Pointer is not modified.
  185.      * @return
  186.      *   If the Current Pointer is -head- , then a -1 is returned.
  187.      *   If the Current Pointer is -tail- , then a -2 is returned.
  188.      *   If the Current Pointer represents the position of a node,
  189.      *   then the position of that node in the linked list is returned.
  190.      **/
  191.     public int getCurrentPointerState() {
  192.         // Code will be added here by students
  193.         return CurrentPosition;
  194.     }
  195.  
  196.     /**
  197.      * Add a node based on the state of the Current Pointer
  198.      * @param newNodeID</CODE>
  199.      *   This is the NodeID that will be used in the new node
  200.      * @param newNodeData</CODE>
  201.      *   This is the data that will be used in the new node
  202.      * <dt><b>Precondition:</b><dd>
  203.      *   none
  204.      * <dt><b>Postcondition:</b><dd>
  205.      *  If Current Pointer is -head-, then the new Node is added
  206.      *      as the first node on the list.
  207.      *  If Current Pointer represents a node position, then the
  208.      *      New Node is added after the current node.
  209.      *  If Current Pointer is -tail-, then no action is performed.
  210.      *  If the addition occurs, the Current Pointer is set to
  211.      *      the location of the new node, otherwise the CP is not
  212.      *      modified.
  213.      * @return
  214.      *  If addition occurs, then true is returned.  Else false is returned.
  215.      **/
  216.     public Boolean addNodeAfterCurrent(int newNodeID, int newData) {
  217.         // Code will be added here by students
  218.  
  219.         while (head == null) {
  220.             IntNode originalHead = head;
  221.             head = new IntNode(newNodeID, newData, tail, null);
  222.  
  223.             // If the head was null, there was nothing on the linked list so tail = head
  224.             if (originalHead == null) {
  225.                 tail = head;
  226.             }
  227.             CurrentPosition = 1;
  228.             return true;
  229.         }
  230.         if(CurrentPosition == -2)
  231.             return false;
  232.  
  233.         while (head != null) {
  234.             IntNode next = head;
  235.             IntNode afterThisOne = null; //The node after which we'll be adding
  236.             IntNode afterAdd = null; //The node before which we'll be adding
  237.  
  238.             while (next != null) {
  239.                 if (next == getNodeAtCurrent()) {
  240.                     afterThisOne = next;
  241.                     afterAdd = afterThisOne.getForwardLink();
  242.                     break;
  243.                 } else {
  244.                     next = next.getForwardLink();
  245.                 }
  246.             }
  247.             if (afterThisOne != null) {
  248.                 IntNode newNode = new IntNode(newNodeID, newData, afterThisOne.getForwardLink(), afterThisOne);
  249.                 afterThisOne.setForwardLink(newNode);
  250.                 if (afterAdd != null) {
  251.                     afterAdd.setBackwardLink(newNode);
  252.                 }
  253.                 if (newNode.getForwardLink() == null) {
  254.                     tail = newNode;
  255.                 }
  256.  
  257.                 if (newNode.getBackwardLink() == null) {
  258.                     newNode.setBackwardLink(afterThisOne);
  259.                 }
  260.  
  261.             }
  262.             CurrentPosition++;
  263.             return true;
  264.         }
  265.         return false;
  266.     }
  267.  
  268.     /**
  269.      * Remove a node based on the state of the Current Pointer
  270.      * <dt><b>Postcondition:</b><dd>
  271.      *  If Current Pointer represents a node position, then the Node at
  272.      *  that location is removed.
  273.      *  if Current Pointer is -head- or -tail-, then no removal happens.
  274.      *  The Current Pointer takes on a new state after the removal.
  275.      *      If there is a node now remaining before the removed node,
  276.      *          then Current Pointer aims at that node.
  277.      *      If the removed node was the first node on the list, then
  278.      *          Current Pointer takes on the state -head-.
  279.      * @return
  280.      *  If removal is performed then true is returned, else false is returned.
  281.      *
  282.      **/
  283.     public Boolean removeNodeAtCurrent() {
  284.         // Code will be added here by students
  285.         while (getCurrentPointerState() <= 0) {
  286.             return false;
  287.         }
  288.  
  289.         while (head == null) {
  290.             return false;
  291.         }
  292.         while (CurrentPosition == 1) {
  293.             if (head != null) {
  294.                 head = head.getForwardLink();
  295.             }
  296.             if (head == null) {
  297.                 tail = head;
  298.             }
  299.             CurrentPosition = -1;
  300.             return true;
  301.         }
  302.         IntNode next = head;
  303.         IntNode afterNext = null;  // The node which we'll be removing
  304.         IntNode beforeNext = null;
  305.  
  306.         while (next != null) {
  307.             if (next.getForwardLink() == getNodeAtCurrent()) {
  308.                 afterNext = next.getForwardLink();
  309.                 beforeNext = next.getBackwardLink();
  310.                 break;
  311.             } else {
  312.                 next = next.getForwardLink();
  313.             }
  314.         }
  315.         if (afterNext != null) {
  316.             if (afterNext != tail) {
  317.                 next.setForwardLink(afterNext.getForwardLink());
  318.                 next.setBackwardLink(beforeNext);
  319.             } else {
  320.                 next.setForwardLink(null);
  321.                 next.setBackwardLink(beforeNext);
  322.  
  323.                 tail = next;
  324.             }
  325.             CurrentPosition--;
  326.             return true;
  327.         }
  328.         return false;
  329.     }
  330.  
  331.     /**
  332.      * Returns The node represented by the State of Current Pointer
  333.      * <dt><b>Postcondition:</b><dd>
  334.      *   The Current Pointer is not modified.
  335.      * @return
  336.      *  If the Current Pointer state represents a node, that Node is returned.
  337.      *     If the Current Pointer state is -head- or -tail-, a null
  338.      *     is returned.
  339.      **/
  340.     public IntNode getNodeAtCurrent() {
  341.         // Code will be added here by students
  342.         IntNode NodeAtCurrent;
  343.  
  344.         if (CurrentPosition >= 0) {
  345.             NodeAtCurrent = head;
  346.             try {
  347.                 for (int i = 1; i < CurrentPosition; i++) {
  348.                     NodeAtCurrent = NodeAtCurrent.getForwardLink();
  349.                 }
  350.  
  351.             } catch (NullPointerException npe) {
  352.             }
  353.         } else {
  354.             NodeAtCurrent = null;
  355.         }
  356.         return NodeAtCurrent;
  357.  
  358.  
  359.     }
  360.  
  361.     /**
  362.      * Returns the number of items on the Linked List
  363.      * <dt><b>Postcondition:</b><dd>
  364.      *   Neither the Current Pointer nor any list items are modified.
  365.      * @return
  366.      *   The number of nodes on the list.  The head and tail are not nodes
  367.      *   even though they may point at nodes.
  368.      **/
  369.     public int getListLength() {
  370.         // Code will be added here by students
  371.         int len = 0;
  372.         for (IntNode in = head; in != null; in = in.getForwardLink()) {
  373.             len++;
  374.         }
  375.         return len;
  376.     }
  377.  
  378.     /**
  379.      * Takes a linked list of integers and rearranges the nodes so the integers
  380.      * (data) stored are sorted into the order of smallest to largest, with
  381.      * the smallest integer in the node at the head of the list.
  382.      * If there are several Nodes have the same data values, then there is a
  383.      * sub-sort so that the lowest NodeIDs come first.
  384.      * Initial Data:
  385.      *        +-----+      +-----+      +-----+     +-----+     +-----+
  386.      *  ----> | ID=1|----> | ID=9|----> |ID=7 |---->|ID=6 |---->|ID=5 |
  387.      *        |dat=5|      |dat=3|      |dat=1|     |dat=3|     |dat=3|
  388.      *        +-----+      +-----+      +-----+     +-----+     +-----+
  389.      * Sorted Data:
  390.      *        +-----+      +-----+      +-----+     +-----+     +-----+
  391.      *  ----> | ID=7|----> | ID=5|----> |ID=6 |---->|ID=9 |---->|ID=1 |
  392.      *        |dat=1|      |dat=3|      |dat=3|     |dat=3|     |dat=5|
  393.      *        +-----+      +-----+      +-----+     +-----+     +-----+
  394.      * It is recommended that you look at Problem 4.7 on pages 239 - 240 of your text.
  395.      *      * <dt><b>Postcondition:</b><dd>
  396.      * The return value is a head reference of a linked list with exactly the
  397.      * same entries as the original list (including repetitions if any) but the
  398.      * entries in this list are sorted from smallest to largest.  The original
  399.      * linked list is no longer available.
  400.      * The Current Pointer is set to head.
  401.      * @return
  402.      *   A pointer to the new Linked List is returned.
  403.      **/
  404.     public IntNode sort() {
  405.         // Code will be added here by students
  406.         //IntNode newList;
  407.         IntNode previousNode = null;
  408.         IntNode NextNode = head.getForwardLink();
  409.         IntNode newHead = head;
  410.         //newHead.setForwardLink(head.getForwardLink)
  411.         int lowData = newHead.getData();
  412.         int previousLowID = newHead.getNodeID();
  413.         try {
  414.             for (IntNode sorter = newHead; sorter != null; sorter = sorter.getForwardLink()) {
  415.                 NextNode = sorter.getForwardLink();
  416.                 previousNode = sorter.getBackwardLink();
  417.                 if (sorter.getData() > NextNode.getData()) {
  418.  
  419.                     sorter.setForwardLink(NextNode.getForwardLink());
  420.                     previousNode.setForwardLink(NextNode);
  421.                     NextNode.setBackwardLink(previousNode);
  422.                     sorter.setBackwardLink(NextNode);
  423.                     NextNode.setForwardLink(sorter);
  424.                     sort();
  425.  
  426.                 }
  427. //                sort();
  428.  
  429.             }
  430.         } catch (NullPointerException npe) {
  431.         }
  432.         //for(int i = 1; i < getListLength(); i++)
  433.         //{
  434.  
  435.         //}
  436.         //newList.printLinkedList();
  437.         //CurrentPosition = -1;
  438.         return newHead;
  439.     }
  440.  
  441.     /**
  442.      * Returns to the caller the version of the node as maintained by the node.
  443.      * The Version number is a property of the Node class being used by this
  444.      *   Linked List.  Should that Node change its properties, it would be
  445.      *   important to know what set of properties are embodied in the Node.
  446.      * @return
  447.      *   The node version is returned.
  448.      **/
  449.     public String getNodeVersion() {
  450.         // Code will be added here by students
  451.         return IntNode.getNodeVersion();
  452.     }
  453.  
  454.     /**
  455.      * Print out the current state of the Linked List including the head,
  456.      *    all nodes on the list, and the tail.
  457.      * <dt><b>Postcondition:</b><dd>
  458.      *   No list components are modified
  459.      *   There is a printout to output, but no return value from the method
  460.      *   THERE SHOULD BE NO NEED FOR STUDENTS TO MODIFY THIS METHOD
  461.      **/
  462.     public void printLinkedList() {
  463.         // Get all the info necessary to print out the head
  464.         IntNode next = head;
  465.         String result = "";
  466.  
  467.         if (next == null) {
  468.             result = "null";
  469.         } else {
  470.             result = " node " + next.getNodeID();
  471.         }
  472.         System.out.println("Head points to " + result);
  473.  
  474.         // Walk down the nodes and print out their info.  Do this
  475.         // until we get to a null pointer.  Note that this uses
  476.         // the toString method in the IntNode class.
  477.         while (next != null) {
  478.             System.out.println(next);
  479.             next = next.getForwardLink();
  480.         }
  481.         // Get all the info necessary to print out the tail
  482.         if (tail == null) {
  483.             result = "null";
  484.         } else {
  485.             result = " node " + tail.getNodeID();
  486.         }
  487.         System.out.println("Tail points to " + result);
  488.         System.out.println("");
  489.     }
  490. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!