Advertisement
jtentor

List.java [lista simple]

Oct 22nd, 2016
313
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. public class List<E> {
  3.     /**
  4.      * Campos en la estructura interna o privada de la clase
  5.      */
  6.     private Node head;
  7.     private int count;
  8.     private Node tail;
  9.  
  10.     /**
  11.      * Getter para count
  12.      *
  13.      * @return cantidad de elementos en la lista
  14.      */
  15.     public int getCount() {
  16.         return this.count;
  17.     }
  18.  
  19.     /**
  20.      * Constructor por defecto
  21.      */
  22.     public List() {
  23.         this.head = null;
  24.         this.count = 0;
  25.         this.tail = null;
  26.     }
  27.    
  28.     /**
  29.      * Agrega al principio
  30.      * Este código puede y debe mejorarse
  31.      *
  32.      * @param item elemento que se agrega a la lista
  33.      */
  34.     public void AddFirst(E item) {
  35.         // si esta vacía
  36.         if (this.count == 0) {
  37.             // se crea un nodo con el elemento a agregar
  38.             // el nuevo nodo es el primero y el último
  39.             this.head = this.tail = new Node(item, null);
  40.             // incrementa la cuenta de elementos
  41.             ++this.count;
  42.         }
  43.         else {
  44.             // se crea un nodo con el elemento a agregar
  45.             Node temp = new Node(item, null);
  46.             // el siguiente del nuevo nodo es el actual primero
  47.             temp.next = this.head;
  48.             // el nuevo nodo se convierte en el primero
  49.             this.head = temp;
  50.             // incrementa la cuenta de elementos
  51.             ++this.count;
  52.         }
  53.     }
  54.  
  55.    
  56.     public void Better_AddFirst(E item) {
  57.         Node temp = new Node(item, this.head);
  58.         if (this.count == 0) {
  59.             this.tail = temp;
  60.         }
  61.         this.head = temp;
  62.         ++this.count;
  63.     }
  64.  
  65.    
  66.     /**
  67.      * Agrega al final
  68.      * Este código puede y debe mejorarse
  69.      *
  70.      * @param item elemento que se agrega a la lista
  71.      */
  72.     public void AddLast(E item) {
  73.         if (this.count == 0) {
  74.             this.head = this.tail = new Node(item, null);
  75.             ++this.count;
  76.         }
  77.         else {
  78.             Node temp = new Node(item, null);
  79.             this.tail.next = temp;
  80.             this.tail = temp;
  81.             ++this.count;
  82.         }
  83.     }
  84.  
  85.    
  86.     public void Better_AddLast(E item) {
  87.         Node temp = new Node(item, null);
  88.         if (this.count == 0) {
  89.             this.head = temp;
  90.         }
  91.         else {
  92.             this.tail.next = temp;
  93.         }
  94.         this.tail = temp;
  95.         ++this.count;
  96.     }
  97.    
  98.  
  99.     /**
  100.      * Extrae y devuelve el primer elemento de la lista
  101.      *
  102.      * @return el elemento que se encuentra al principio de la lista
  103.      * @exception Lista vacía
  104.      */
  105.     public E RemoveFirst() {
  106.         if (this.count == 0) {
  107.             throw new RuntimeException("La lista está vacía...");
  108.         }
  109.  
  110.         // toma el elemento que está en el primer nodo
  111.         E item = this.head.item;
  112.         // avanza el primer nodo al siguiente
  113.         this.head = this.head.next;
  114.         // si no hay mas nodos
  115.         if (this.head == null) {
  116.             // vaciar la lista
  117.             this.tail = null;
  118.         }
  119.         // decrementa la cuenta de elementos
  120.         --this.count;
  121.         // regresar el elemento
  122.         return item;
  123.     }
  124.  
  125.     /**
  126.      * Extrae y devuelve el último elemento de la lista
  127.      *
  128.      * @return el elemento que se encuentra al final de la lista
  129.      * @exception Lista vacía
  130.      */
  131.     public E RemoveLast() {
  132.         if (this.count == 0) {
  133.             throw new RuntimeException("La lista está vacía...");
  134.         }
  135.  
  136.         E item = this.tail.item;
  137.  
  138.         // si es el único nodo
  139.         if (this.head.next == null) {
  140.             // vacía la lista
  141.             this.head = this.tail = null;
  142.         } else {
  143.             // esta implementación tiene Orden lineal O(n)
  144.             // comienza con el primer nodo
  145.             Node skip = this.head;
  146.             // recorre la lista mientras haya dos nodos más
  147.             for ( ; skip.next.next != null; skip = skip.next) { }
  148.             // skip es el penúltimo nodo que ahora será el último
  149.             this.tail = skip;
  150.             // anula la referencia al siguiente nodo
  151.             this.tail.next = null;
  152.         }
  153.         // decrementa la cuenta de elementos
  154.         --this.count;
  155.         // regresa el elemento
  156.         return item;
  157.        
  158.     }
  159.    
  160.     /**
  161.      * Muestra en la salida estándar todos los elementos de la lista
  162.      *
  163.      * Para evitar código como este, se aconseja implementar interfaces
  164.      * que permitan recorrer la lista, como ser Iterable e Iterator
  165.      *  
  166.      */
  167.     public void Mostrar() {
  168.         for (Node skip = this.head; skip != null; skip = skip.next) {
  169.             System.out.printf("%s ", skip.toString());
  170.         }
  171.     }
  172.    
  173.  
  174.    
  175.    
  176.    
  177.    
  178.  
  179.    
  180.    
  181.    
  182.    
  183.    
  184.    
  185.    
  186.    
  187.  
  188.     /**
  189.      * Clase privada para los nodos de la lista
  190.      */
  191.     private class Node {
  192.         /**
  193.          * Campos en la estructura interna o privada de la clase
  194.          */
  195.         public E item;
  196.         public Node next;
  197.        
  198.         /**
  199.          * Constructor por defecto
  200.          */
  201.         public Node() {
  202.             this(null, null);
  203.         }
  204.  
  205.         /**
  206.          * Constructor especializado
  207.          *
  208.          * @param item elemento a mantener en el nodo
  209.          */
  210.         public Node(E item) {
  211.             this(item, null);
  212.         }
  213.        
  214.         /**
  215.          * Constructor especializado
  216.          *
  217.          * @param item elemento a mantener en el nodo
  218.          * @param next referencia al siguiente nodo
  219.          */
  220.         public Node(E item, Node next) {
  221.             this.item = item;
  222.             this.next = next;
  223.         }
  224.  
  225.         /**
  226.          * Devuelve una cadena de texto que representa el contenido
  227.          * del elemento que está en el nodo
  228.          *
  229.          * Esto es un ejemplo de "delegación"
  230.          */
  231.         public String toString() {
  232.             return this.item.toString();
  233.         }
  234.     }
  235.  
  236.    
  237.    
  238. }
Advertisement
RAW Paste Data Copied
Advertisement