MOISES_QUISPE_ROJAS

Estructura Datos 2021 - SimpleLinkedList

Oct 27th, 2021
788
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //
  2. // Created by Julio Tentor <jtentor@fi.unju.edu.ar>
  3. //
  4. package List;
  5.  
  6. import java.util.Iterator;
  7. import java.lang.Comparable;
  8.  
  9. public class SimpleLinkedList<ELEMENT> implements ILinkedList<ELEMENT> {
  10.  
  11.     //region Node Class
  12.     private class Node<ELEMENT> {
  13.  
  14.         public ELEMENT item;
  15.         public Node<ELEMENT> next;
  16.  
  17.         public Node() {
  18.             this(null, null);
  19.         }
  20.  
  21.         public Node(ELEMENT item) {
  22.             this(item, null);
  23.         }
  24.  
  25.         public Node(ELEMENT item, Node<ELEMENT> next) {
  26.             this.item = item;
  27.             this.next = next;
  28.         }
  29.  
  30.         @Override
  31.         public String toString() {
  32.             return this.item.toString();
  33.         }
  34.     }
  35.     //endregion
  36.  
  37.     //region Attributes
  38.     protected Node<ELEMENT> head;
  39.     protected int count;
  40.     protected Node<ELEMENT> tail;
  41.     //endregion
  42.  
  43.     //region Constructors
  44.     public SimpleLinkedList() {
  45.         this.head = null;
  46.         this.count = 0;
  47.         this.tail = null;
  48.     }
  49.     //endregion
  50.  
  51.     @Override
  52.     public ELEMENT peekFirst() {
  53.         Node<ELEMENT> p = this.head;
  54.         return p.item;
  55.     }
  56.  
  57.     //region Linked List Methods
  58.     // Returns the number of elements in this list.
  59.     public int size() {
  60.         return this.count;
  61.     }
  62.  
  63.     public void addFirstRookieVersion(ELEMENT item) {
  64.         if (this.count == 0) {
  65.             this.head = this.tail = new Node<ELEMENT>(item, null);
  66.             ++this.count;
  67.         } else {
  68.             Node<ELEMENT> temp = new Node<ELEMENT>(item, null);
  69.             temp.next = this.head;
  70.             this.head = temp;
  71.             ++this.count;
  72.         }
  73.     }
  74.  
  75.     // Inserts the specified element at the beginning of this list.
  76.     public void addFirst(ELEMENT item) {
  77.         Node<ELEMENT> temp = new Node<ELEMENT>(item, this.head);
  78.         if (this.count == 0) {
  79.             this.tail = temp;
  80.         }
  81.         this.head = temp;
  82.         ++this.count;
  83.     }
  84.  
  85.     public void addLastRookieVersion(ELEMENT item) {
  86.         if (this.count == 0) {
  87.             this.head = this.tail = new Node<ELEMENT>(item, null);
  88.             ++this.count;
  89.         } else {
  90.             Node<ELEMENT> temp = new Node<ELEMENT>(item, null);
  91.             this.tail.next = temp;
  92.             this.tail = temp;
  93.             ++this.count;
  94.         }
  95.     }
  96.  
  97.     // Appends the specified element to the end of this list.
  98.     public void addLast(ELEMENT item) {
  99.         Node<ELEMENT> temp = new Node<ELEMENT>(item, null);
  100.         if (this.count == 0) {
  101.             this.head = temp;
  102.         } else {
  103.             this.tail.next = temp;
  104.         }
  105.         this.tail = temp;
  106.         ++this.count;
  107.     }
  108.  
  109.     // Removes and returns the first element from this list.
  110.     public ELEMENT removeFirst() {
  111.         if (this.count == 0) {
  112.             throw new RuntimeException("La lista está vacía...");
  113.         }
  114.         ELEMENT item = this.head.item;
  115.         this.head = this.head.next;
  116.         if (this.head == null) {
  117.             this.tail = null;
  118.         }
  119.         --this.count;
  120.         return item;
  121.     }
  122.  
  123.     // Removes and returns the last element from this list.
  124.     public ELEMENT removeLast() {
  125.         if (this.count == 0) {
  126.             throw new RuntimeException("La lista está vacía...");
  127.         }
  128.         ELEMENT item = this.tail.item;
  129.         if (this.head.next == null) {
  130.             this.head = this.tail = null;
  131.         } else {
  132.             Node<ELEMENT> skip = this.head;
  133.             while (skip.next.next != null) {
  134.                 skip = skip.next;
  135.             }
  136.             this.tail = skip;
  137.             this.tail.next = null;
  138.         }
  139.         --this.count;
  140.         return item;
  141.     }
  142.     //endregion
  143.  
  144.     //region Object Methods
  145.     @Override
  146.     public String toString() {
  147.  
  148.         if (this.size() <= 0) {
  149.             return "";
  150.         }
  151.  
  152.         // from https://docs.oracle.com/en/java/javase/15/docs/api/java.base/java/lang/StringBuilder.html
  153.         StringBuilder sb = new StringBuilder();
  154.  
  155.         sb.append("[" + this.head.item.toString());
  156.         for (Node<ELEMENT> skip = this.head.next; skip != null; skip = skip.next) {
  157.             sb.append(", " + skip.item.toString());
  158.         }
  159.         sb.append("]");
  160.  
  161.         return sb.toString();
  162.     }
  163.     //endregion
  164.  
  165.     //region Iterable Methods
  166.     @Override
  167.     public Iterator<ELEMENT> iterator() {
  168.         return new SimpleLinkedListIterator(this.head);
  169.     }
  170.  
  171.     private class SimpleLinkedListIterator implements Iterator<ELEMENT> {
  172.  
  173.         private Node<ELEMENT> current;
  174.  
  175.         public SimpleLinkedListIterator(Node<ELEMENT> current) {
  176.             this.current = current;
  177.         }
  178.  
  179.         @Override
  180.         public boolean hasNext() {
  181.             return this.current != null;
  182.         }
  183.  
  184.         @Override
  185.         public ELEMENT next() {
  186.             if (!this.hasNext()) {
  187.                 throw new RuntimeException("La lista está vacía...");
  188.             }
  189.             ELEMENT item = this.current.item;
  190.             this.current = this.current.next;
  191.             return item;
  192.         }
  193.  
  194.     }
  195.  
  196.     public class SimpleLinkedOrderedList<ELEMENT extends Comparable<ELEMENT>> extends SimpleLinkedList<ELEMENT> implements ILinkedOrderedList<ELEMENT> {
  197.  
  198.         //region Constructors
  199.         public SimpleLinkedOrderedList() {
  200.             super();
  201.         }
  202.         //endregion
  203.  
  204.         //region Ordered List Methods
  205.         @Override
  206.         public void addInOrder(ELEMENT item) {
  207.             if (this.size() == 0) {
  208.                 this.head = this.tail = new Node<ELEMENT>(item, null);
  209.                 ++this.count;
  210.             } else {
  211.                 if (item.compareTo(this.head.item) <= 0) {
  212.                     this.addFirst(item);
  213.                 } else {
  214.                     if (item.compareTo(this.tail.item) > 0) {
  215.                         this.addLast(item);
  216.                     } else {
  217.                         Node<ELEMENT> skip = this.head;
  218.                         while ((skip != null) && (skip.next != null) && (item.compareTo(skip.next.item) > 0)) {
  219.                             skip = skip.next;
  220.                         }
  221.                         if (skip == null) {
  222.                             throw new RuntimeException("Algo está mal en el orden de los elementos de la lista...");
  223.                         } else {
  224.                             Node<ELEMENT> temp = new Node<ELEMENT>(item, skip.next);
  225.                             skip.next = temp;
  226.                             ++this.count;
  227.                         }
  228.                     }
  229.                 }
  230.             }
  231.  
  232.         }
  233.     }
  234. }
  235.  
RAW Paste Data