fork download
copy 
  1. import java.util.AbstractList;
  2. import java.util.Iterator;
  3. import java.util.Random;
  4.  
  5. import java.util.NoSuchElementException;
  6.  
  7. /**
  8.   * A singly linked null-terminated list implementation.
  9.   */
  10. class LinkedList<E> extends AbstractList<E> {
  11.     private Node<E> head = null;
  12.     private Node<E> tail = null;
  13.     private int size = 0;
  14.  
  15.     /**
  16.      * In-place O(NlgN) shuffle.
  17.      */
  18.     public void shuffle(Random random) {
  19.         head = shuffle(0, size(), head, random);
  20.         tail = head;
  21.         while (tail.next != null) {
  22.             tail = tail.next;
  23.         }
  24.     }
  25.  
  26.     /**
  27.      * Shuffles the specified sublist starting from the lo's index
  28.      * and ending right before the hi's index. Requires you to
  29.      * pass a reference to the element at the lo index, so that
  30.      * the method wouldn't have to search for that element by itself.
  31.      * @return head element of the shuffled null-terminated sublist.
  32.      */
  33.     private Node<E> shuffle(int lo, int hi,
  34.             Node<E> loElement, Random random) {
  35.         if (hi - lo == 1) {
  36.             // null-terminate a single-element list
  37.             loElement.next = null;
  38.             return loElement;
  39.         }
  40.         int mid = (lo + hi) >>> 1;
  41.         Node<E> midElement = loElement;
  42.         for (int i = lo; i < mid; i++) {
  43.             midElement = midElement.next;
  44.         }
  45.  
  46.         loElement = shuffle(lo, mid, loElement, random);
  47.         midElement = shuffle(mid, hi, midElement, random);
  48.         return mergeShuffledLists(
  49.             lo, loElement,
  50.             mid, midElement, 
  51.             hi, random
  52.         );
  53.     }
  54.  
  55.     /**
  56.      * Merges two shuffled halves of the list into a single one
  57.      * in a way that the resulting list is uniformly shuffled
  58.      * (given that the specified sublists are uniformly shuffled).
  59.      * @return  head element of the merged null-terminated list.
  60.      */
  61.     private Node<E> mergeShuffledLists(
  62.             int iLeftSublist, Node<E> leftSublistIter,
  63.             int iRightSublist, Node<E> rightSublistIter,
  64.             int hi, Random random) {
  65.         int mid = iRightSublist;
  66.         double sublistSize = hi - iLeftSublist;
  67.         // initialize with dummy node to avoid both copy-paste code,
  68.         // when initializing newHead with the initial value,
  69.         // and excessive not-null checks inside the loop
  70.         Node<E> newHead = new Node<>(null, null);
  71.         Node<E> newListIter = newHead;
  72.  
  73.         while (leftSublistIter != null || rightSublistIter != null) {
  74.             double decision = random.nextDouble();
  75.             if (rightSublistIter == null
  76.                     || decision < (mid - iLeftSublist) / sublistSize) {
  77.                 newListIter.next = leftSublistIter;
  78.                 leftSublistIter = leftSublistIter.next;
  79.                 iLeftSublist++;
  80.             } else {
  81.                 newListIter.next = rightSublistIter;
  82.                 rightSublistIter = rightSublistIter.next;
  83.                 iRightSublist++;
  84.             }
  85.             newListIter = newListIter.next;
  86.         }
  87.         // null-terminate reassembled list
  88.         newListIter.next = null;
  89.         // skip the dummy node
  90.         return newHead.next;
  91.     }
  92.  
  93.     @SuppressWarnings("unchecked")
  94.     /**
  95.      * Linear time shuffle that uses O(N) extra memory
  96.      */
  97.     public void linearShuffle(Random random) {
  98.         if (size() > 1) {
  99.             Object[] nodes = new Object[size()];
  100.             shuffle(nodes, random);
  101.             head = (Node<E>) nodes[0];
  102.             tail = head;
  103.             for (int i = 1; i < nodes.length; i++) {
  104.                tail.next = (Node<E>) nodes[i];
  105.                tail = tail.next;
  106.             }
  107.         }
  108.     }
  109.  
  110.     /**
  111.      * Uniformly shuffles the array using the specified {@code random}
  112.      * instance.
  113.      */
  114.     private static void shuffle(Object[] array, Random random) {
  115.         final int n = array.length;
  116.         for (int i = 0; i < n - 1; i++) {
  117.             swap(array, i, i + random.nextInt(n - i - 1) + 1);
  118.         }
  119.     }
  120.  
  121.     /**
  122.      * Swaps the elements at the specified indices of the {@code array}.
  123.      * @throws  IndexOutOfBoundsException if either of the specified
  124.      *          indices is out of range.
  125.      */
  126.     public static void swap(Object[] array, int i, int j) {
  127.         if (!rangeCheck(array, i) || !rangeCheck(array, j)) {
  128.             throw new IndexOutOfBoundsException(String.format(
  129.                 "Got: i = %d, j = %d meanwhile = len(array) = %d",
  130.                 i, j, array.length
  131.             ));
  132.         }
  133.         Object swap = array[i];
  134.         array[i] = array[j];
  135.         array[j] = swap;
  136.     }
  137.  
  138.     @Override
  139.     /**
  140.       * Returns the element at the specified position in the list.
  141.       * This method runs at O(N) time since it has to go from
  142.       * the head of the list to the target element.
  143.       */
  144.     public E get(int index) {
  145.         if (index < 0 || index >= size()) {
  146.             throw new IndexOutOfBoundsException(String.format(
  147.                 "Got: index = %d, size = %d", index, size()
  148.             ));
  149.         }
  150.         int iCurrent = 0;
  151.         Node<E> current = head;
  152.         while (iCurrent != index) {
  153.             current = current.next;
  154.             iCurrent++;
  155.         }
  156.         return current.value;
  157.     }
  158.  
  159.     /**
  160.      * Checks, if the specified index belongs to the array.
  161.      * @return  {@code false} in case the index is out of range
  162.      *          or the {@code array} argument is null.
  163.      */
  164.     private static boolean rangeCheck(Object[] array, int index) {
  165.         if (array == null) {
  166.             return false;
  167.         }
  168.         if (index < 0 || index >= array.length) {
  169.             return false;
  170.         }
  171.         return true;
  172.     }
  173.  
  174.     @Override
  175.     /**
  176.       * Appends the specified element to the end of the list.
  177.       * @return {@code true} in case the collection changed
  178.       *         as a result of the call.
  179.       */
  180.     public boolean add(E value) {
  181.         assert (head == null) == (tail == null);
  182.  
  183.         if (value == null) {
  184.             throw new NullPointerException(
  185.                 "Null elements are not allowed"
  186.             );
  187.         }
  188.  
  189.         if (head == null) {
  190.             head = new Node<>(value, null);
  191.             tail = head;
  192.         } else {
  193.             tail.next = new Node<>(value, null);
  194.             tail = tail.next;
  195.         }
  196.         size++;
  197.         return true;
  198.     }
  199.  
  200.     @Override
  201.     /**
  202.       * Inserts a new element at the specified position.
  203.       */
  204.     public void add(int index, E value) {
  205.         assert (head == null) == (tail == null);
  206.  
  207.         if (value == null) {
  208.             throw new NullPointerException(
  209.                 "Null elements are not allowed"
  210.             );
  211.         }
  212.         if (index < 0 || index > size()) {
  213.             throw new IndexOutOfBoundsException(String.format(
  214.                 "Got: index = %d, size = %d", index, size()
  215.             ));
  216.         }
  217.  
  218.         if (index == 0) {
  219.             head = new Node<>(value, head);
  220.             if (tail == null) {
  221.                 tail = head;
  222.             }
  223.         } else {
  224.             int iCurrent = 0;
  225.             Node<E> current = head;
  226.             while (iCurrent < index - 1) {
  227.                 current = current.next;
  228.                 iCurrent++;
  229.             }
  230.             current.next = new Node<>(value, current.next);
  231.             if (index == size()) {
  232.                 tail = current.next;
  233.             }
  234.         }
  235.         size++;
  236.     }
  237.  
  238.     @Override
  239.     /**
  240.       * Returns the size of the array.
  241.       * The implementation is based on just keeping a {@code size}
  242.       * variable which is being updated after every list mutation.
  243.       * Thus the returned value does not depend on whether the
  244.       * list is null-terminated or not.
  245.       */
  246.     public int size() {
  247.         return size;
  248.     }
  249.  
  250.     @Override
  251.     /**
  252.       * Clears the list.
  253.       */
  254.     public void clear() {
  255.         head = null;
  256.         tail = null;
  257.         size = 0;
  258.     }
  259.  
  260.     @Override
  261.     /**
  262.       * Removes the element with the specified index from the list
  263.       */
  264.     public E remove(int index) {
  265.         if (index < 0 || index >= size()) {
  266.             throw new IndexOutOfBoundsException(String.format(
  267.                     "Got: index = %d, size = %d", index, size()
  268.             ));
  269.         }
  270.         E value = null;
  271.         if (index == 0) {
  272.             value = head.value;
  273.             head = head.next;
  274.             if (head == null) {
  275.                 tail = null;
  276.             }
  277.         } else {
  278.             int iCurrent = 0;
  279.             Node<E> current = head;
  280.             while (iCurrent < index - 1) {
  281.                 current = current.next;
  282.                 iCurrent++;
  283.             }
  284.             value = current.next.value;
  285.             current.next = current.next.next;
  286.             if (index == size() - 1) {
  287.                 tail = current;
  288.             }
  289.         }
  290.         size--;
  291.         return value;
  292.     }
  293.  
  294.     @Override
  295.     public boolean isEmpty() {
  296.         return size() == 0;
  297.     }
  298.  
  299.     @Override
  300.     public E set(int index, E value) {
  301.         if (value == null) {
  302.             throw new NullPointerException(
  303.                 "Null elements are not allowed"
  304.             );
  305.         }
  306.         if (index < 0 || index >= size()) {
  307.             throw new IndexOutOfBoundsException(String.format(
  308.                 "Got: index = %d, size = %d", index, size
  309.             ));
  310.         }
  311.  
  312.         int iCurrent = 0;
  313.         Node<E> current = head;
  314.         while (iCurrent < index) {
  315.             current = current.next;
  316.             iCurrent++;
  317.         }
  318.         E previousValue = current.value;
  319.         current.value = value;
  320.         return previousValue;
  321.     }
  322.  
  323.     @Override
  324.     public Iterator<E> iterator() {
  325.         return new LinkedListIterator(head);
  326.     }
  327.  
  328.     @Override
  329.     public String toString() {
  330.         StringBuilder sb = new StringBuilder("[ ");
  331.         for (E element : this) {
  332.             sb.append(String.format("%s ", element));
  333.         }
  334.         sb.append("]");
  335.         return sb.toString();
  336.     }
  337.  
  338.     private static class Node<T> {
  339.         private T value;
  340.         private Node<T> next = null;
  341.  
  342.         public Node(T value, Node<T> next) {
  343.             this.value = value;
  344.             this.next = next;
  345.         }
  346.     }
  347.  
  348.     /**
  349.       * An iterator that sequentially returns the elements in order.
  350.       * Works in a null-termination manner, so you must
  351.       * make sure that the list is null-terminated.
  352.       */
  353.     private class LinkedListIterator implements Iterator<E> {
  354.         private Node<E> current;
  355.  
  356.         private Node<E> beforePrevious = null;
  357.         private int iBeforePrevious = -2;
  358.         private boolean removeCalled = false;
  359.  
  360.         public LinkedListIterator(Node<E> head) {
  361.             current = head;
  362.         }
  363.  
  364.         @Override
  365.         public boolean hasNext() {
  366.             return current != null;
  367.         }
  368.  
  369.         @Override
  370.         public E next() {
  371.             if (current == null) {
  372.                 throw new NoSuchElementException("The list is empty");
  373.             }
  374.             E value = current.value;
  375.             iBeforePrevious++;
  376.             if (iBeforePrevious > 0) {
  377.                 beforePrevious = current;
  378.             } else if (iBeforePrevious == 0) {
  379.                 beforePrevious = head;
  380.             }
  381.             current = current.next;
  382.             return value;
  383.         }
  384.  
  385.         @Override
  386.         public void remove() {
  387.             if (!removeCalled) {
  388.                 if (iBeforePrevious >= 0) {
  389.                     beforePrevious.next = beforePrevious.next.next;
  390.                     size--;
  391.                 } else if (iBeforePrevious == -1) {
  392.                     head = current;
  393.                     size--;
  394.                 } else {
  395.                     throw new IllegalStateException(
  396.                         "next() has not yet been called"
  397.                     );
  398.                 }
  399.             } else {
  400.                 throw new IllegalStateException(
  401.                     "remove() has already been called once after"
  402.                     + "the next() call."
  403.                 );
  404.             }
  405.         }
  406.     }
  407.  
  408.     public static void main(String[] args) {
  409.         LinkedList<Integer> list = new LinkedList<>();
  410.         for (int i = 0; i < 10; i++) {
  411.             list.add(i);
  412.         }
  413.         System.out.println(list);
  414.         list.shuffle(new Random());
  415.         System.out.println(list);
  416.     }
  417. }
Success #stdin #stdout 0.08s 34420KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[ 0 1 2 3 4 5 6 7 8 9 ]
[ 3 6 8 5 9 7 1 2 4 0 ]
https://ideone.com/Jm2E0I
language:
Java (HotSpot 12)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!