Advertisement
jtentor

List.java [lista ordenada]

Oct 22nd, 2016
367
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 7.77 KB | None | 0 0
  1. import java.lang.Comparable;
  2. import java.util.Iterator;
  3.  
  4. public class List<E extends Comparable<E>> implements Iterable<E> {
  5.     /**
  6.      * Campos en la estructura interna o privada de la clase
  7.      */
  8.     private Node head;
  9.     private int count;
  10.     private Node tail;
  11.  
  12.     /**
  13.      * Getter para count
  14.      *
  15.      * @return cantidad de elementos en la lista
  16.      */
  17.     public int getCount() {
  18.         return this.count;
  19.     }
  20.  
  21.     /**
  22.      * Constructor por defecto
  23.      */
  24.     public List() {
  25.         this.head = null;
  26.         this.count = 0;
  27.         this.tail = null;
  28.     }
  29.  
  30.    
  31.     /**
  32.      * Agrega al principio
  33.      * Este código puede y debe mejorarse
  34.      *
  35.      * @param item elemento que se agrega a la lista
  36.      */
  37.     public void AddFirst(E item) {
  38.         // si esta vacía
  39.         if (this.count == 0) {
  40.             // se crea un nodo con el elemento a agregar
  41.             // el nuevo nodo es el primero y el último
  42.             this.head = this.tail = new Node(item, null, null);
  43.             // incrementa la cuenta de elementos
  44.             ++this.count;
  45.         }
  46.         else {
  47.             // se crea un nodo con el elemento a agregar
  48.             Node temp = new Node(item, null, null);
  49.             // el siguiente del nuevo nodo es el actual primero
  50.             temp.next = this.head;
  51.             // el anterior del actual primero es el nuevo nodo
  52.             this.head.prev = temp;
  53.             // el nuevo nodo se convierte en el primero
  54.             this.head = temp;
  55.             // incrementa la cuenta de elementos
  56.             ++this.count;
  57.         }
  58.     }
  59.  
  60.        
  61.     public void BetterAddFirst(E item) {
  62.         Node temp = new Node(item, this.head, null);
  63.         if (this.count == 0) {
  64.             this.tail = temp;
  65.         }
  66.         else {
  67.             this.head.prev = temp;
  68.         }
  69.         this.head = temp;
  70.         ++this.count;
  71.     }
  72.  
  73.  
  74.     /**
  75.      * Agrega al final
  76.      * Este código puede y debe mejorarse
  77.      *
  78.      * @param item elemento que se agrega a la lista
  79.      */
  80.     public void AddLast(E item) {
  81.         if (this.count == 0) {
  82.             // se crea un nodo con el elemento a agregar
  83.             // el nuevo nodo es el primero y el último
  84.             this.head = this.tail = new Node(item, null, null);
  85.             // incrementa la cuenta de elementos
  86.             ++this.count;
  87.         }
  88.         else {
  89.             // se crea un nodo con el elemento a agregar
  90.             Node temp = new Node(item, null, null);
  91.             // el anterior del nuevo nodo es el actual último
  92.             temp.prev = this.tail;
  93.             // el siguiente del actual último es el nuevo nodo
  94.             this.tail.next = temp;
  95.             // el nuevo es ahora el último
  96.             this.tail = temp;
  97.             // incrementa la cuenta de elementos
  98.             ++this.count;
  99.         }
  100.     }
  101.    
  102.  
  103.     public void BetterAddLast(E item) {
  104.         Node temp = new Node(item, null, this.tail);
  105.         if (this.count == 0) {
  106.             this.head = temp;
  107.         }
  108.         else {
  109.             this.tail.next = temp;
  110.         }
  111.         this.tail = temp;
  112.         ++this.count;
  113.     }
  114.    
  115.  
  116.     public void AddInOrder(E item) {
  117.         if (this.count == 0) {
  118.             // se crea un nodo con el elemento a agregar
  119.             // el nuevo nodo es el primero y el último
  120.             this.head = this.tail = new Node(item, null, null);
  121.             // incrementa la cuenta de elementos
  122.             ++this.count;
  123.         }
  124.         else {
  125.             if (item.compareTo(this.head.item) <= 0) {
  126.                 // es menor o igual que el primero
  127.                 this.AddFirst(item);
  128.             }
  129.             else {
  130.                 if (item.compareTo(this.tail.item) > 0) {
  131.                     // es mayor que el último
  132.                     this.AddLast(item);
  133.                 }
  134.                 else {
  135.                     Node skip = this.head;
  136.                     for ( ; (skip != null) && (item.compareTo(skip.item) > 0); skip = skip.next) { }
  137.                     // skip es null o el nodo cuyo valor es mas grande que item
  138.                     if (skip == null) {
  139.                         // esto no debería ocurrir por las dudas hacemos programación defensiva
  140.                         throw new RuntimeException("Algo está mal en el orden de los elementos de la lista...");
  141.                     }
  142.                     else {
  143.                         // se debe insertar antes de skip
  144.                         Node temp = new Node(item, skip, skip.prev);
  145.                         skip.prev.next = temp;
  146.                         skip.prev = temp;
  147.                         ++this.count;
  148.                     }
  149.                 }
  150.             }
  151.         }
  152.        
  153.     }
  154.  
  155.     /**
  156.      * Extrae y devuelve el primer elemento de la lista
  157.      *
  158.      * @return el elemento que se encuentra al principio de la lista
  159.      * @exception Lista vacía
  160.      */
  161.     public E RemoveFirst() {
  162.         if (this.count == 0) {
  163.             throw new RuntimeException("La lista está vacía...");
  164.         }
  165.  
  166.         // toma el elemento que está en el primer nodo
  167.         E item = this.head.item;
  168.         // avanza el primer nodo al siguiente
  169.         this.head = this.head.next;
  170.         // si no hay mas nodos
  171.         if (this.head == null) {
  172.             // vaciar la lista
  173.             this.tail = null;
  174.         }
  175.         else {
  176.             // suprimir la referencia al anterior en el actual primero
  177.             this.head.prev = null;
  178.         }
  179.         // decrementa la cuenta de elementos
  180.         --this.count;
  181.         // regresar el elemento
  182.         return item;
  183.     }
  184.    
  185.    
  186.    
  187.     /**
  188.      * Extrae y devuelve el último elemento de la lista
  189.      *
  190.      * @return el elemento que se encuentra al final de la lista
  191.      * @exception Lista vacía
  192.      */
  193.     public E RemoveLast() {
  194.         if (this.count == 0) {
  195.             throw new RuntimeException("La lista está vacía...");
  196.         }
  197.  
  198.         E item = this.tail.item;
  199.  
  200.         // si es el único nodo
  201.         if (this.head.next == null) {
  202.             // vacía la lista
  203.             this.head = this.tail = null;
  204.         } else {
  205.             // accede al penúltimo nodo que ahora será el último
  206.             this.tail = this.tail.prev;
  207.             // anula la referencia al siguiente nodo
  208.             this.tail.next = null;
  209.         }
  210.         // decrementa la cuenta de elementos
  211.         --this.count;
  212.         // regresa el elemento
  213.         return item;
  214.        
  215.     }
  216.    
  217.    
  218.     public boolean FindAndRemove(E item) {
  219.         if (this.count == 0) {
  220.             return false;
  221.         }
  222.  
  223.         Node skip = this.head;
  224.         for ( ; (skip != null) && !(item.compareTo(skip.item) == 0); skip = skip.next) { }
  225.         // skip es null o el nodo cuyo valor es igual que item
  226.         if (skip == null) {
  227.             // no esta
  228.             return false;
  229.         }
  230.         else {
  231.             // se debe extraer el nodo skip
  232.             if (skip.prev == null) {
  233.                 // es el primero
  234.                 this.RemoveFirst();
  235.                 return true;
  236.             }
  237.             else {
  238.                 if (skip.next == null) {
  239.                     // es el último
  240.                     this.RemoveLast();
  241.                     return true;
  242.                 }
  243.                 else {
  244.                     skip.prev.next = skip.next;
  245.                     skip.next.prev = skip.prev;
  246.                     skip.prev = skip.next = null;
  247.                     return true;
  248.                 }
  249.             }
  250.         }
  251.     }
  252.  
  253.  
  254.    
  255.    
  256.    
  257.    
  258.    
  259.  
  260.    
  261.     /**
  262.      * Clase privada para los nodos de la lista
  263.      */
  264.     private class Node {
  265.         /**
  266.          * Campos en la estructura interna o privada de la clase
  267.          */
  268.         public E item;
  269.         public Node next;
  270.         public Node prev;
  271.        
  272.         /**
  273.          * Constructor por defecto
  274.          */
  275.         public Node() {
  276.             this(null, null, null);
  277.         }
  278.  
  279.         /**
  280.          * Constructor especializado
  281.          *
  282.          * @param item elemento a mantener en el nodo
  283.          */
  284.         public Node(E item) {
  285.             this(item, null, null);
  286.         }
  287.  
  288.         /**
  289.          * Constructor especializado
  290.          *
  291.          * @param item elemento a mantener en el nodo
  292.          * @param next referencia al siguiente nodo
  293.          */
  294.         public Node(E item, Node next) {
  295.             this(item, next, null);
  296.         }
  297.        
  298.         /**
  299.          * Constructor especializado
  300.          *
  301.          * @param item elemento a mantener en el nodo
  302.          * @param next referencia al siguiente nodo
  303.          * @param prev referencia al nodo anterior
  304.          */
  305.         public Node(E item, Node next, Node prev) {
  306.             this.item = item;
  307.             this.next = next;
  308.             this.prev = prev;
  309.         }
  310.  
  311.         /**
  312.          * Devuelve una cadena de texto que representa el contenido
  313.          * del elemento que está en el nodo
  314.          *
  315.          * Esto es un ejemplo de "delegación"
  316.          */
  317.         public String toString() {
  318.             return this.item.toString();
  319.         }
  320.     }
  321.  
  322.  
  323.    
  324.     @Override
  325.     public Iterator<E> iterator() {
  326.         return new MyIterator(this.head);
  327.     }
  328.  
  329.     /**
  330.      * Implementación de un iterador para la clase List
  331.      *
  332.      */
  333.     private final class MyIterator implements Iterator<E> {
  334.         private Node current;
  335.        
  336.         public MyIterator(Node start) {
  337.             this.current = start;
  338.         }
  339.        
  340.         @Override
  341.         public boolean hasNext() {
  342.             return this.current != null;
  343.         }
  344.  
  345.         @Override
  346.         public E next() {
  347.             if (!this.hasNext()) {
  348.                 throw new RuntimeException("La lista está vacía...");
  349.             }
  350.             E item = this.current.item;
  351.             this.current = this.current.next;
  352.             return item;
  353.         }
  354.        
  355.     }
  356.    
  357.    
  358.  
  359. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement