Clase de Lista de Pedidos personalizados con la clase ordenada anidada -- java campo con linked-list camp codereview Relacionados El problema

Custom OrderedLinkedList class with nested OrderedListNode class


2
vote

problema

Español

Todo funciona con este programa. Sin embargo, toma ambas cuerdas y ints, siento que mi método ADD es simplemente demasiado verboso. ¿Alguien cree que puedo implementar una versión más corta de esto, o es bueno como es?

nota : nada se puede cambiar en cualquiera de las firmas de métodos o parámetros. Lo único que puedo cambiar es el código dentro de los métodos ADD y Eliminar, así como la clase de List de Pedidos anidados personalizados.

      public class OrderedLinkedList {  static Comparable temp; //this will be used to reference an element that was removed  public static void main(String[] args) {      /*     TEST STRINGS      */     OrderedLinkedList list = new OrderedLinkedList();     modCount = 0;     list.add("Dog");     list.add("Bird");     list.add("dog");     list.add("bird");     list.add("Cat");     System.out.println("Before removal");     System.out.println(list);     list.remove("Dog");     System.out.println("Removed " + temp);     list.remove("bird");     System.out.println("Removed " + temp);     System.out.println("After removal");     System.out.println(list);     System.out.println("Total modifications = " + modCount); //make sure modification count is correct     System.out.println("Size of Ordered List = " + theSize); //make sure size is correct     System.out.println();      /*     TEST INTEGERS      */     OrderedLinkedList integerList = new OrderedLinkedList();     modCount = 0;     integerList.add(1);     integerList.add(233);     integerList.add(42);     integerList.add(100);     System.out.println("Before removal");     System.out.println(integerList);     integerList.remove(1);     System.out.println("Removed " + temp);     integerList.add(232);     System.out.println("After removal of " + temp + " and addition of another element");     System.out.println(integerList);     System.out.println("Total modifications = " + modCount); //make sure modification count is correct     System.out.println("Size of Ordered List = " + theSize); //make sure size is correct } /**************************************************************************  * Constants  *************************************************************************/  /**  * return value for unsuccessful searches  */ private static final OrderedListNode NOT_FOUND = null;  /**************************************************************************  * Attributes  *************************************************************************/  /**  * current number of items in list  */ private static int theSize;  /**  * reference to list header node  */ private OrderedListNode head;  /**  * reference to list tail node  */ private OrderedListNode tail;  /**  * current number of modifications to list  */ private static int modCount;   /**************************************************************************  * Constructors  *************************************************************************/  /**  * Create an instance of OrderedLinkedList.  */ public OrderedLinkedList() {     // empty this OrderedLinkedList     clear(); }   /**************************************************************************  * Methods  *************************************************************************/   /*  *  Add the specified item to this OrderedLinkedList.  *  *  @param  obj     the item to be added  */ public boolean add(Comparable obj) {     // TODO: Implement this method (8 points)      //FOR REFERENCE - public OrderedListNode(Comparable item, OrderedListNode before, OrderedListNode next) {      OrderedListNode newElement = NOT_FOUND;      if(head.next == tail) { //if the list contains only the head and tail (head.next being the tail) place item between the two.         newElement = new OrderedListNode(obj, head, tail);         head.next = newElement; // [HEAD -> newElement -> TAIL]         tail.before = newElement;         modCount++; //         theSize++; //if size is not increased, output will not print correctly         return true;     }     for(OrderedListNode element = head.next; element != tail; element = element.next) { //loop through each node of the list, stopping at the tail          if(element.before == head && obj.compareTo(element.dataItem) < 0) { //if head is before inserted element and less than element at cursor             newElement = new OrderedListNode(obj, head, element);              head.next = newElement; //swap cursors             element.before = newElement;             modCount++; //another modification             theSize++; //increase size by 1             return true;         }         if(obj.compareTo(element.dataItem) > 0 && element.next == tail) { //if inserted element is greater than dataItem and next is tail             newElement = new OrderedListNode(obj, element, tail);              element.next = newElement;             tail.before = newElement;             modCount++; //another modification             theSize++; //increase size by 1             return true;         }         if(obj.compareTo(element.dataItem) > 0 && obj.compareTo(element.next.dataItem) < 0) { //if inserted element is greater than element at cursor, but less than current element              OrderedListNode elementBefore = element;             OrderedListNode elementAfter = element.next;              newElement = new OrderedListNode(obj, element, element.next);             elementBefore.next = newElement;             elementAfter.before = newElement;             modCount++; //another modification             theSize++; //increase size by 1             return true;         }     }     return false; }  /*  *  Remove the first occurrence of the specified item from this OrderedLinkedList.  *  *  @param  obj     the item to be removed  */ public boolean remove(Comparable obj) {     // TODO: implement this method (7 points)      for(OrderedListNode element = head.next; element != tail; element = element.next) {          if(obj.equals(element.dataItem)) { //if element being removed is at the cursor             OrderedListNode previousNode = element.before;             OrderedListNode nextNode = element.next;             temp = obj; //temp will be used to access element that was removed              nextNode.before = previousNode; //places next element that's after before to the element after current element [prev -> current -> next]              previousNode.next = nextNode; //places prev of next element to the element before current              element.dataItem = (Comparable)NOT_FOUND; //removed element is now null              modCount++; //another modification             theSize--; //reduce the size by 1             return true; //if remove is successful         }     }     return false; //otherwise, not successful removal }  /**  * Empty this OrderedLinkedList.  */ public void clear() {      // reset header node     head = new OrderedListNode("HEAD", null, null);      // reset tail node     tail = new OrderedListNode("TAIL", head, null);      // header references tail in an empty LinkedList     head.next = tail;      // reset size to 0     theSize = 0;      // emptying list counts as a modification     modCount++; }  /**  * Return true if this OrderedLinkedList contains 0 items.  */ public boolean isEmpty() {     return theSize == 0; }  /**  * Return the number of items in this OrderedLinkedList.  */ public int size() {     return theSize; }  /*  *  Return a String representation of this OrderedLinkedList.  *  *  (non-Javadoc)  *  @see java.lang.Object#toString()  */ @Override public String toString() {     String s = "";      OrderedListNode currentNode = head.next;      while (currentNode != tail) {         s += currentNode.dataItem.toString();          if (currentNode.next != tail) {             s += ", ";         }          currentNode = currentNode.next;     }     return s; }  /************************************************************************** * Inner Classes *************************************************************************/  /**  * Nested class OrderedListNode.  * <p>  * Encapsulates the fundamental building block of an OrderedLinkedList  * contains a data item, and references to both the next and before nodes  * in the list  */ // TODO: Implement the nested class OrderedListNode (5 points).  This nested class // should be similar to the nested class ListNode of the class LinkedList, but // should store a data item of type Comparable rather than Object.  public static class OrderedListNode {      /**      * FOR REFERENCE      * <p>      * private static class Node<E> {      * E item;      * Node<E> next;      * Node<E> prev;      * <p>      * Node(Node<E> prev, E element, Node<E> next) {      this.item = element;      this.next = next;      this.prev = prev;      * }      * }      */     Comparable dataItem;     OrderedListNode next;     OrderedListNode before;      public OrderedListNode(Comparable item, OrderedListNode before, OrderedListNode next) {         this.dataItem = item;         this.next = next;         this.before = before;     } }//end nested class }   

Salida:

  Before removal Bird, Cat, Dog, bird, dog Removed Dog Removed bird After removal Bird, Cat, dog Total modifications = 7 Size of Ordered List = 3  Before removal 1, 42, 100, 233 Removed 1 After removal of 1 and addition of another element 42, 100, 232, 233 Total modifications = 6 Size of Ordered List = 4   
Original en ingles

Everything works with this program. It takes both Strings and ints, however, I feel like my add method is simply too verbose. Does anyone believe I can implement a shorter version of this, or is it good as is?

Note: Nothing can be changed in any of the method signatures or parameters. The only thing I can change is the code within the add and remove methods, as well as the custom nested OrderedListNode class.

    public class OrderedLinkedList {  static Comparable temp; //this will be used to reference an element that was removed  public static void main(String[] args) {      /*     TEST STRINGS      */     OrderedLinkedList list = new OrderedLinkedList();     modCount = 0;     list.add("Dog");     list.add("Bird");     list.add("dog");     list.add("bird");     list.add("Cat");     System.out.println("Before removal");     System.out.println(list);     list.remove("Dog");     System.out.println("Removed " + temp);     list.remove("bird");     System.out.println("Removed " + temp);     System.out.println("After removal");     System.out.println(list);     System.out.println("Total modifications = " + modCount); //make sure modification count is correct     System.out.println("Size of Ordered List = " + theSize); //make sure size is correct     System.out.println();      /*     TEST INTEGERS      */     OrderedLinkedList integerList = new OrderedLinkedList();     modCount = 0;     integerList.add(1);     integerList.add(233);     integerList.add(42);     integerList.add(100);     System.out.println("Before removal");     System.out.println(integerList);     integerList.remove(1);     System.out.println("Removed " + temp);     integerList.add(232);     System.out.println("After removal of " + temp + " and addition of another element");     System.out.println(integerList);     System.out.println("Total modifications = " + modCount); //make sure modification count is correct     System.out.println("Size of Ordered List = " + theSize); //make sure size is correct } /**************************************************************************  * Constants  *************************************************************************/  /**  * return value for unsuccessful searches  */ private static final OrderedListNode NOT_FOUND = null;  /**************************************************************************  * Attributes  *************************************************************************/  /**  * current number of items in list  */ private static int theSize;  /**  * reference to list header node  */ private OrderedListNode head;  /**  * reference to list tail node  */ private OrderedListNode tail;  /**  * current number of modifications to list  */ private static int modCount;   /**************************************************************************  * Constructors  *************************************************************************/  /**  * Create an instance of OrderedLinkedList.  */ public OrderedLinkedList() {     // empty this OrderedLinkedList     clear(); }   /**************************************************************************  * Methods  *************************************************************************/   /*  *  Add the specified item to this OrderedLinkedList.  *  *  @param  obj     the item to be added  */ public boolean add(Comparable obj) {     // TODO: Implement this method (8 points)      //FOR REFERENCE - public OrderedListNode(Comparable item, OrderedListNode before, OrderedListNode next) {      OrderedListNode newElement = NOT_FOUND;      if(head.next == tail) { //if the list contains only the head and tail (head.next being the tail) place item between the two.         newElement = new OrderedListNode(obj, head, tail);         head.next = newElement; // [HEAD -> newElement -> TAIL]         tail.before = newElement;         modCount++; //         theSize++; //if size is not increased, output will not print correctly         return true;     }     for(OrderedListNode element = head.next; element != tail; element = element.next) { //loop through each node of the list, stopping at the tail          if(element.before == head && obj.compareTo(element.dataItem) < 0) { //if head is before inserted element and less than element at cursor             newElement = new OrderedListNode(obj, head, element);              head.next = newElement; //swap cursors             element.before = newElement;             modCount++; //another modification             theSize++; //increase size by 1             return true;         }         if(obj.compareTo(element.dataItem) > 0 && element.next == tail) { //if inserted element is greater than dataItem and next is tail             newElement = new OrderedListNode(obj, element, tail);              element.next = newElement;             tail.before = newElement;             modCount++; //another modification             theSize++; //increase size by 1             return true;         }         if(obj.compareTo(element.dataItem) > 0 && obj.compareTo(element.next.dataItem) < 0) { //if inserted element is greater than element at cursor, but less than current element              OrderedListNode elementBefore = element;             OrderedListNode elementAfter = element.next;              newElement = new OrderedListNode(obj, element, element.next);             elementBefore.next = newElement;             elementAfter.before = newElement;             modCount++; //another modification             theSize++; //increase size by 1             return true;         }     }     return false; }  /*  *  Remove the first occurrence of the specified item from this OrderedLinkedList.  *  *  @param  obj     the item to be removed  */ public boolean remove(Comparable obj) {     // TODO: implement this method (7 points)      for(OrderedListNode element = head.next; element != tail; element = element.next) {          if(obj.equals(element.dataItem)) { //if element being removed is at the cursor             OrderedListNode previousNode = element.before;             OrderedListNode nextNode = element.next;             temp = obj; //temp will be used to access element that was removed              nextNode.before = previousNode; //places next element that's after before to the element after current element [prev -> current -> next]              previousNode.next = nextNode; //places prev of next element to the element before current              element.dataItem = (Comparable)NOT_FOUND; //removed element is now null              modCount++; //another modification             theSize--; //reduce the size by 1             return true; //if remove is successful         }     }     return false; //otherwise, not successful removal }  /**  * Empty this OrderedLinkedList.  */ public void clear() {      // reset header node     head = new OrderedListNode("HEAD", null, null);      // reset tail node     tail = new OrderedListNode("TAIL", head, null);      // header references tail in an empty LinkedList     head.next = tail;      // reset size to 0     theSize = 0;      // emptying list counts as a modification     modCount++; }  /**  * Return true if this OrderedLinkedList contains 0 items.  */ public boolean isEmpty() {     return theSize == 0; }  /**  * Return the number of items in this OrderedLinkedList.  */ public int size() {     return theSize; }  /*  *  Return a String representation of this OrderedLinkedList.  *  *  (non-Javadoc)  *  @see java.lang.Object#toString()  */ @Override public String toString() {     String s = "";      OrderedListNode currentNode = head.next;      while (currentNode != tail) {         s += currentNode.dataItem.toString();          if (currentNode.next != tail) {             s += ", ";         }          currentNode = currentNode.next;     }     return s; }  /************************************************************************** * Inner Classes *************************************************************************/  /**  * Nested class OrderedListNode.  * <p>  * Encapsulates the fundamental building block of an OrderedLinkedList  * contains a data item, and references to both the next and before nodes  * in the list  */ // TODO: Implement the nested class OrderedListNode (5 points).  This nested class // should be similar to the nested class ListNode of the class LinkedList, but // should store a data item of type Comparable rather than Object.  public static class OrderedListNode {      /**      * FOR REFERENCE      * <p>      * private static class Node<E> {      * E item;      * Node<E> next;      * Node<E> prev;      * <p>      * Node(Node<E> prev, E element, Node<E> next) {      this.item = element;      this.next = next;      this.prev = prev;      * }      * }      */     Comparable dataItem;     OrderedListNode next;     OrderedListNode before;      public OrderedListNode(Comparable item, OrderedListNode before, OrderedListNode next) {         this.dataItem = item;         this.next = next;         this.before = before;     } }//end nested class } 

Output:

Before removal Bird, Cat, Dog, bird, dog Removed Dog Removed bird After removal Bird, Cat, dog Total modifications = 7 Size of Ordered List = 3  Before removal 1, 42, 100, 233 Removed 1 After removal of 1 and addition of another element 42, 100, 232, 233 Total modifications = 6 Size of Ordered List = 4 
     
       
       

Lista de respuestas

1
 
vote
vote
La mejor respuesta
 

Preocupaciones

Aunque escribiste:

No se puede cambiar nada en cualquiera de las firmas de métodos o parámetros. Lo único que puedo cambiar es el código dentro de los métodos ADD y QUITE, así como el 9988776655544330 personalizado.

Sin embargo, en un comentario, confirmó otros cambios que realizó, como private static int theSize; .

Como no está muy claro lo que realmente se le dio, me gustaría señalar algunos puntos problemáticos.

  1. tipo de seguridad. Una colección sinquipo de elementos comparables es una idea disfuncional. Dicha colección aceptará "algunos texto" y el número 7, y si intenta comparar los dos, el programa se bloqueará en tiempo de ejecución. Algo de lo que el compilador podría haber protegido.

  2. Llamar clear() En un constructor: En la hora de construcción, esto no tiene ningún sentido, el objeto es vacío. Si su programa no funciona correctamente sin esto, no está usando OOP correctamente.

  3. El comentario en theSize++; //if size is not increased, output will not print correctly es preocupante: el comportamiento durante la salida no debe ser la razón para incrementar el tamaño. La razón para incrementar el tamaño debe ser que se agregue un nuevo elemento.

  4. El nombre "ordenado" no tiene sentido al hablar de listas: las listas están ordenadas por definición . Es el pedido que establece un List Aparte de un Collection . Creo que el término que estás buscando es "ordenado".

Simplificación add

Su pregunta principal fue cómo acortar el método add . La lógica actual está revisando demasiados casos, innecesariamente. Puede simplificar utilizando este algoritmo:

  • Set node a head
  • bucle sobre los nodos hasta private static int theSize;0 es private static int theSize;1
    • Comparar private static int theSize;2 Con private static int theSize;3
    • Si son iguales, entonces no hay necesidad de insertar, private static int theSize;4
    • Si private static int theSize;5 es menor que private static int theSize;6 , luego rompe del bucle
  • Inserte el nuevo nodo antes de private static int theSize;7
    • Tenga en cuenta que en este punto, private static int theSize;8 tiene un valor más grande que private static int theSize;9 , o es 99887776655443320
    • Configurar los enlaces correctamente ( clear()1 - & gt; nuevo - & gt; 99887766555443322 ), el tamaño del incremento y el recuento de modificación

algo como esto:

  clear()3  
 

Concerns

Although you wrote:

Nothing can be changed in any of the method signatures or parameters. The only thing I can change is the code within the add and remove methods, as well as the custom nested OrderedListNode class.

However, in a comment you confirmed other changes you made, such as private static int theSize;.

As it's not very clear what was really given, I'd like to point out some troubling points.

  1. Type safety. An untyped collection of comparable elements is a dysfunctional idea. Such a collection will accept both "some text" and the number 7, and if you try to compare the two the program will crash at runtime. Something from which the compiler could have protected.

  2. Calling clear() in a constructor: at construction time, this doesn't make any sense, the object is empty. If your program doesn't work correctly without this, then you're not using OOP correctly.

  3. The comment in theSize++; //if size is not increased, output will not print correctly is troubling: behavior during output should not be the reason for incrementing the size. The reason for incrementing the size should be that a new element is being added.

  4. The name "ordered" doesn't make sense when talking about lists: lists are ordered by definition. It's the ordering that sets a List apart from a Collection. I think the term you're looking for is "sorted".

Simplifying add

Your main question was how to shorten the add method. The current logic is checking too many cases, unnecessarily. You can simplify using this algorithm:

  • Set node to head
  • Loop over the nodes until node.next is tail
    • Compare obj with node.next
    • If they are equal, then no need to insert, return false
    • If obj is less than node.next, then break out of the loop
  • Insert the new node before node.next
    • Note that at this point, node.next either has a larger value than obj, or it is tail
    • Setup the links correctly (node -> new -> node.next), increment size and modification count

Something like this:

public boolean add(Comparable obj) {      OrderedListNode node = head;      for (; node.next != tail; node = node.next) {          int cmp = obj.compareTo(node.next.dataItem);          if (cmp == 0) {             return false;         }          if (cmp < 0) {             // obj is less than next, so should be inserted before next             break;         }     }      OrderedListNode newNode = new OrderedListNode(obj, node, node.next);     newNode.next.before = newNode;     node.next = newNode;      modCount++;     theSize++;     return true; } 
 
 
     
     

Relacionados problema

7  Simulando una lista enlazada lineal usando una matriz  ( Simulating a linear linked list using an array ) 
Un programa para simular una lista enlazada lineal usando una matriz: Especificaciones: A Y: cree un nuevo nodo con el valor de datos y, y agregue este...

5  Destructor para una lista vinculada  ( Destructor for a linked list ) 
El código completo se encuentra aquí: https://gist.github.com/4521540 < / p> Es un maniquí List en C ++. Mi preocupación es para liberar la memoria. No s...

14  Implementando una lista relacionada adecuada para un entorno profesional  ( Implementing a proper linked list for a professional environment ) 
Tengo algunas preocupaciones: ¿Es normal que la clase tenga al menos un nodo? En otras palabras, esta implementación no puede tener una lista vinculada va...

1  DEQUEUE () en la implementación de la cola que utiliza una lista circular vinculada  ( Dequeue in queue implememtation that uses a circular linked list ) 
Utilizo una lista de enlaces circulares para implementar un queue , y solo sostiene un 99887776665544332 (Tenga en cuenta que 99887776655443333 enlaces a...

4  ADT Pila con Linkedlist  ( Adt stack with linkedlist ) 
Actualmente estoy preparando para mi examen y estoy tratando de implementar algunos tipos de datos abstractos con listas vinculadas como preparación para el e...

5  Cola de bloqueo con la exactitud de la lista doblemente vinculada  ( Lock free queue with doubly linked list correctness ) 
Necesito una cola de bloqueo que se implementa mediante la lista doblemente vinculada. es mi código correcto? ¿Hay algún error? ¿Hay alguna mejoras a realiz...

3  Lista doblemente vinculada en óxido usando los punteros crudos  ( Doubly linked list in rust using raw pointers ) 
Estoy practicando la oxidación escribiendo una lista doblemente vinculada usando los punteros crudos, 9988776655544330 Para asignar datos en el montón, 998...

10  Lista vinculada de objetos de conejito  ( Linked list of bunny objects ) 
El ejercicio es el ejercicio de la lista de conejitos vinculados; El último ejercicio para principiantes de aquí . Estoy buscando comentarios sobre absolut...

0  Agregando dos números extremadamente grandes usando una estructura de datos personalizada  ( Adding two extremely large numbers using a custom data structure ) 
Tengo una implementación para agregar 2 números extremadamente grandes, mayor que el techo proporcionado por long , por ejemplo, 1238913893838383813813813813...

4  Eliminar nodos alternativos de una lista vinculada  ( Delete alternate nodes of a linked list ) 
Si la lista vinculada es 1- & gt; 2- & gt; 3- & gt; 4 entonces la salida debe ser 1- & gt; 3. Si la lista vinculada es 1- & gt; 2- & gt; 3- & gt; 4- & gt; 5,...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos