Отдельно связанный список: вставить узел между двумя узлами

Question

Я работаю над проектом, который имитирует сегменты памяти, поступающие и выходящие из виртуальной памяти. Когда сегмент отправляется, или память не занята, она становится дырой .

---

Ограничения:

• "голова" узел всегда должен указывать на наименьший адрес в памяти.

---

Проблема: Я попасться в круговом контуре при вставке узла между 2 узлами. Я пытаюсь провести «предыдущий» и «текущий» узел, безуспешно.
Вместо списка: Node0 -> Node1 -> Node2
он показывает Node0 ->Node2, где Node1 является вставленным узлом.

Выход:

| Расположение | Размер | Время отлета |

---

Попытка решения: Я создал предыдущий и текущий узел, чтобы вставить узел между ними. Поиск должен начинаться с узла, который был последним; lastPlacement. Я прокомментировал выше раздел, который, по моему мнению, вызывает ошибку.
Весь код размещен ниже, ошибка возникает в метод места.

Тестовый файл, чтобы использовать во время работы:

N 
R 1000 5 100 80 10000 
P 
E 

---

/******************************************************************************** 
* @author  Evan Bechtol (ecb120030) 
*    <h1>Project: Memory Segmentation Simulation</h1> 
*    <p>Simulation of arrivals/departures/placements of segments in a 
*    segmented virtual memory, through the use of a linked-list. Implements a 
*    next-fit policy. Constraints: There can never be neighboring holes.</p> 
* @since  2015-2-13 
* @see   http://www.programmingsimplified.com/java/source-code/java-program-to-bubble-sort 
* @see   http://web.cerritos.edu/jwilson/SitePages/java_language_resources/Java_printf_method_quick_reference.pdf 
* @see   http://www.algolist.net/Data_structures/Singly-linked_list/Removal 
* @see   http://crunchify.com/a-simple-singly-linked-list-implementation-in-java/ 
* 
********************************************************************************/ 

import java.util.*; 
import java.io.*; 

/** 
* Creates nodes to be used as data containers in the Memory class 
*/ 
class Node { 
    boolean segment;  // Equals false if this Node represents a hole 
    int  location;  // Position in memory of first byte 
    int  size;   // Size that node occupies 
    int  timeToDepart; // Only valid when this Node represents a segment 
    Node next; 

    /** 
    * Constructor for generating a segment in memory 
    * 
    * @param locn  location of node to be created 
    * @param sz   size of node to be created 
    * @param endOfLife the timeOfDay node is to depart 
    * @param nxt   specifies the next node to reference in the list 
    */ 
    Node (int locn, int sz, int endOfLife, Node nxt) { 
     segment  = true; 
     location  = locn; 
     size   = sz; 
     timeToDepart = endOfLife; 
     next   = nxt; 
    } 

    /** 
    * Constructor for a hole 
    * 
    * @param locn location of hole to be created 
    * @param sz  size of hole to be created 
    * @param nxt  reference to next node in the list 
    */ 
    Node (int locn, int sz, Node nxt) { 
     segment  = false; 
     location = locn; 
     size  = sz; 
     next  = nxt; 
    } 
} // End Node class 

/** 
* Creates a linked-list of ndoes to simulate virtual memory segments and holes 
*/ 
class Memory { 
    private static int memorySize; // Defines the total size for the memory 
    Node head;      // Refers to first node in memory 
    Node lastPlacement;    // Refers to the last node that was placed, or hole if the last placed segment is removed 

    /** 
    * Constructor for Memory, generates a single hole Node of the given size 
    * 
    * @param size initial size of memory object 
    */ 
    Memory (int size) { 
      memorySize = size; 
      Node n = new Node (0, memorySize, null); 
      lastPlacement = head = n; 
    } 

    /** 
    * Attempts to place a request using the Next Fit Policy. Returns false if there 
    * isn't a hole big enough. Prints a confirmation if placed; return true 
    * 
    * @param  size  size of placement to be made 
    * @param  timeOfDay the time at which the placement is being made 
    * @param  lifeTime how long the segment is to remain in memory 
    * @param  verbose  specifies if extra placement information is to be given 
    * @return  boolean: returns true if the placement was successful 
    */ 
    boolean place (int size, int timeOfDay, int lifeTime, boolean verbose) { 

     // If the list is empty, we can place as head node 
     if (isEmpty()) { 
      Node current = new Node (0, size, 0, null); 
      lastPlacement = head = current; 
      return true; 
     } 
     // There are nodes in the list 
     else { 
      Node current = lastPlacement; // We start searching for a hole at our lastPlacement 
      Node previous = head; 
      // While there are still nodes to reverse, keep looking 
      while (current != null) { 

       // If we are looking at a hole and it is equal to, or larger than our required size 
       if ((!current.segment) && (current.size >= size)) { 

        // Hole is EXACT size required 
        if (current.size == size) { 
         current.segment = true; 
         current.timeToDepart = timeOfDay + lifeTime; 
        } 
        // Hole is larger than our size required 
        else { 
         Node newNode = new Node (current.location, size, timeOfDay + lifeTime, current); //timeOfDay + lifeTime = timeToDepart 

         current.location += size + 1; 
         current.size -= size; 
         lastPlacement = newNode; 
         previous.next = newNode; 

         if (newNode.location == 0) { 
          head = newNode; 
         } 
        } 
        /* newNode.segment  = true; 
         current.next = newNode; 
         current.size = current.size - size; // Adjust size of hole after placing segment 
         lastPlacement = newNode;*/ 

         // If verbose == true, print the confirmation 
         if (verbose) { 
          System.out.println ("Segment at location: " + lastPlacement.location + "\twith size: " + lastPlacement.size + "\tdeparts at: " + lastPlacement.timeToDepart); 
         } 
         return true; 
       } 
       previous = current; 
       current = current.next; 
      } // End while 

      current = head; // To traverse from start of list 

      //While there are still nodes to reverse, keep looking 
      while (current != lastPlacement) { 
       // If we are looking at a hole 
       if ((!current.segment) && (current.size >= size)) { 

        // Hole is EXACT size required 
        if (current.size == size) { 
         current.segment = true; 
         current.timeToDepart = timeOfDay + lifeTime; 
        } 
        // Hole is larger than our size required 
        else { 

        // If the hole is larger or equal to the size we need 
         Node newNode = new Node (current.location, size, timeOfDay + lifeTime, current); //timeOfDay + lifeTime = timeToDepart 

         current.location += size + 1; 
         current.size -= size; 
         lastPlacement = newNode; 
         previous.next = newNode; 

         if (newNode.location == 0) { 
          head = newNode; 
         } 
        } 
        /* newNode.segment  = true; 
         current.next = newNode; 
         current.size = current.size - size; 
         lastPlacement = newNode;*/ 

         // If verbose == true, print the confirmation 
         if (verbose) { 
          System.out.println ("Placed segment at location: " + lastPlacement.location + "\twith size: " + lastPlacement.size + "\tdeparts at: " + lastPlacement.timeToDepart); 
         } 
         return true; 
       } 
       previous = current; 
       current = current.next; 
      } // End while 
     } 
     // If we reach this point, segment could not be placed 
     return false; 
    } 

    /** 
    * Remove segments from the list, which are ready to depart. 
    * <p>Checks the following conditions:<ul><li> 
    *  1) Head is segment and ready to depart 
    *  2) Current is segment and ready to depart 
    *  3) Previous is hole, current is hole 
    *  4) We are combining the node containing last placement, with another node</li></ul></p> 
    * 
    * @param timeOfDay time at which the removal is being done 
    */ 
    void removeSegmentsDueToDepart (int timeOfDay) { 

     // Case 1: Head is segment and ready to depart 
     if ((head.segment) && (head.timeToDepart <= timeOfDay)) { 
      head.segment = false; // Allow node to become a hole 
      //System.out.println ("Case 1."); 
     } 

     // Create reference to head node 
     Node previous = head; 

     // Begin iterating on list from 2nd node 
     while (previous.next != null) { 
      //Use this as our current position 
      Node current = previous.next; 

      // Case 2: Current is segment and ready to depart 
      if ((current.segment) && (current.timeToDepart <= timeOfDay)) { 
       //Combine 
       current.segment = false; 
       //System.out.println ("Case 2."); 

      } 

      // Case 3: previous is hole, current is hole 
      if ((!previous.segment) && (!current.segment)) { 
       // Case 4: We are combining the node containing last placement, with another node 
       if (current == lastPlacement) { 
        // Set last placement to the node to be combined to 
        lastPlacement = previous; 
        //System.out.println ("Case 4."); 
       } 
       // Combine 
       previous.size += current.size; 
       previous.next = current.next; 
      } 
      // Else we adjust our position. 
      else { 
       previous = current; 
      } 
     } // End while 
    } 

    /** 
    * Print a 3-column tab-separated list of all segments in Memory. 
    * Displayed in ascending order of location.  
    */ 
    void printLayout() { 
     Node current; 

     // Print the sorted array of nodes 
     for (current = head; current != null; current = current.next) { 
      System.out.println (current.location + "\t" + current.size + "\t" + current.timeToDepart); 
     } 
    } 

    /** 
    * Determines the empty or occupied state of the list 
    * 
    * @return Returns true if list is empty 
    * @return Returns false if nodes are in the list 
    */ 
    public boolean isEmpty() { 
     if (head == null) { 
      return true; 
     } 
     return false; 
    } 
} // End Memory class 


/** 
* Class to test Memory and Node classes. Accepts file-redirection from commandline by using the 
* scanner with System.in, can also accept file input by using scanner with new File   
*/ 
public class EVBEP1 { 

    /** 
    * Used to test implementation of Memory and Node objects. Processes commands received through 
    * either the commandline or file-input. 
    * 
    * @param args     Standard parameter for parsing commands received 
    * @throws FileNotFoundException If file is unable to be located, exception is thrown 
    */ 
    public static void main(String[] args) throws FileNotFoundException { 
     // Used for accepting command line arguments 
     //Scanner sc = new Scanner (System.in); 
     // Used for testing purposes 
     Scanner sc   = new Scanner(new File("p115sd5.txt")); 
     String line   = ""; 
     boolean done  = false; 
     Memory memory  = new Memory(0); // Memory object 
     int timeOfDay  = 0;    // Simulated wall clock, begins with value zero 
     int placements  = 0;    // Number of placements completed, begins with value zero 
     long totalSpaceTime = 0;    // Sum of placed segmentSize(i) x segmentLifetime(i)  
     float meanOccupancy = 0; 

     // Loop runs as long as done != true 
     while (!done) { 
      line = sc.nextLine();    // Store data gathered from file into String 
      String [] tokens = line.split(" "); // Split the string using space as delimiter 

      // Switch for processing commands received 
      switch (tokens[0]) { 

      // Print name followed by newline 
      case "N": { 
        System.out.println("Evan Clay Bechtol"); 
        break; 
       } 

      // Create a memory object of size s 
      case "C": { 
        memory = new Memory(Integer.parseInt(tokens[1])); // Create a new Memory object 
        break; 
       } 

      // End of data file, print newline and exit 
      case "E": { 
        System.out.println(); 
        done = true; // Break the loop, end the program 
        break; 
       } 

      // Add segment of size 'u' and lifetime 'v' and print confirmation record 
      case "A": { 
        int size = Integer.parseInt(tokens[1]); 
        int lifeTime = Integer.parseInt(tokens[2]); 
        timeOfDay++; 

        memory.removeSegmentsDueToDepart(timeOfDay); 

        // Boolean controls whether confirmation is printed. 
        while (!memory.place(size, timeOfDay, lifeTime, true)) { 
         timeOfDay++; 
         memory.removeSegmentsDueToDepart(timeOfDay); 
         } // End while 
        placements++; 

        // Print confirmation message 
        System.out.printf("Segment of size %4d", size); 
        System.out.printf("\tplaced at time %4d", timeOfDay); 
        System.out.printf("\tat location %4d", memory.lastPlacement.location); 
        System.out.printf("\tdeparts at %4d", memory.lastPlacement.timeToDepart); 
        System.out.println(); 
        break; 
       } 

      // Print the current segments in the list 
      case "P": { 
        System.out.println(); 
        memory.printLayout(); 
        break; 
       } 

      case "R": { 
        int size = Integer.parseInt(tokens[1]); // Size 
        memory = new Memory(size); 
        int minSegSize = Integer.parseInt(tokens[2]); // Minimum seg. size 
        int maxSegSize = Integer.parseInt(tokens[3]); // Maximum seg. size 
        int maxLifeTime = Integer.parseInt(tokens[4]); // Maximum lifetime of segs. 
        int numSegs = Integer.parseInt(tokens[5]);  // Number of segs. to simulate 
        timeOfDay = 0; 
        placements = 0; 
        Random ran = new Random(); // "Random" number generator 
        Scanner n = new Scanner (System.in); 
        while (placements < numSegs) { 
         //System.out.println ("Press any key to iterate.. Placements made: " + placements); 
         memory.printLayout(); 
         //System.out.println ("Loc: " + memory.lastPlacement.location + "\tSize: " + memory.lastPlacement.size + "\tdeparts at: " + memory.lastPlacement.timeToDepart); 
         /*if(memory.lastPlacement.next != null) { 
          System.out.println ("Next)" + " Loc: " + memory.lastPlacement.next.location + "\tSize: " + memory.lastPlacement.next.size + "\tdeparts at: " + memory.lastPlacement.next.timeToDepart); 
         } 
         else { 
          System.out.println ("Next = null"); 
         }*/ 
         //n.nextLine(); 

         timeOfDay++; 
         memory.removeSegmentsDueToDepart(timeOfDay); 
         int newSegSize = minSegSize + ran.nextInt(maxSegSize - minSegSize + 1); 
         int newSegLifetime = 1 + ran.nextInt(maxLifeTime); 
         totalSpaceTime += newSegSize * newSegLifetime; 

         while (!memory.place(newSegSize, timeOfDay, newSegLifetime, false)) { 
          timeOfDay++; 
          memory.removeSegmentsDueToDepart(timeOfDay); 
         } // End while 
         placements++; 
        } // End while 

        // Print final summary of execution 
        meanOccupancy = totalSpaceTime/(timeOfDay); 
        System.out.printf ("Number of placements made = %6d", placements); 
        System.out.println(); 
        System.out.printf ("Mean occupancy of memory = %8.2f", meanOccupancy); 
        System.out.println(); 
        n.close(); 
        break; 
       } 
      } // End switch 
     } // End while 
     sc.close(); 
    } // End main 
} // End EVBEP1 class 

Answer 1

Я исправил проблему путем изменения способа место на следующее:

boolean place (int size, int timeOfDay, int lifeTime, boolean verbose) { 

    // If the list is empty, we can place as head node 
    if (isEmpty()) { 
     Node current = new Node (0, size, -1, null); 
     lastPlacement = head = current; 
     return true; 
    } 
    // There are nodes in the list 
    else { 
     Node current = lastPlacement; //We start searching for a hole at our lastPlacement 

     //While there are still nodes to reverse, keep looking 
     while (current != null) { 
      // If we are looking at a hole 
      if (!current.segment && current.timeToDepart <= timeOfDay) { 

       if (current.size == size) { 
        current.segment = true; 
        current.timeToDepart = timeOfDay + lifeTime; 
       } 
       // If the hole is larger or equal to the size we need 
       if (current.size > size) { 
        Node n = new Node (current.location, size, timeOfDay + lifeTime, current.next); //timeOfDay + lifeTime = timeToDepart 
        n.segment = true; 
        current.next = n; 
        current.size = current.size - size; // Adjust size of hole after placing segment 
        lastPlacement = current = n; 

        // If verbose == true, print the confirmation 
        if (verbose) { 
         System.out.println ("Segment at location: " + lastPlacement.location + "\twith size: " + lastPlacement.size + "\tdeparts at: " + lastPlacement.timeToDepart); 
        } 
        return true; 
       } 
      } 
      current = current.next; 
     } // End while 

     current = this.head; // To traverse from start of list 

     //While there are still nodes to reverse, keep looking 
     while (current != lastPlacement) { 
      // If we are looking at a hole 
      if (!current.segment && current.timeToDepart <= timeOfDay) { 

       if (current.size == size) { 
        current.segment = true; 
        current.timeToDepart = timeOfDay + lifeTime; 
       } 
       // If the hole is larger or equal to the size we need 
       if (current.size > size) { 
        Node n = new Node (current.location + size, size, timeOfDay + lifeTime, current.next); //timeOfDay + lifeTime = timeToDepart 
        n.segment = true; 
        current.next = n; 
        current.size = current.size - size; 
        lastPlacement = current = n; 

        // If verbose == true, print the confirmation 
        if (verbose) { 
         System.out.println ("Segment at location: " + lastPlacement.location + "\twith size: " + lastPlacement.size + "\tdeparts at: " + lastPlacement.timeToDepart); 
        } 
        return true; 
       } 
      } 
      current = current.next; 
     } // End while 
    } 
    // If we reach this point, segment could not be placed 
    return false; 
}