How to randomize ArrayList without using Collections.swap()?

Question

I was asked to create a method that randomly rearranges my list which contains arrays. The list contains multiple persons and their names and surnames. My question is how do I move a person (array containing two elements name and surname inside the list) to a different index without using the method swap()? Because our list does not support that method. Sadly we do not use the "official" list and have our own one coded like this:

public class List<ContentType> {  

    private class ListNode {

        private ContentType contentObject;
        private ListNode next;

        private ListNode(ContentType pContent) {
          contentObject = pContent;
          next = null;
        }
        
        public ContentType getContentObject() {
          return contentObject;
        }

        public void setContentObject(ContentType pContent) {
          contentObject = pContent;
        }

        public ListNode getNextNode() {
          return this.next;
        }

        public void setNextNode(ListNode pNext) {
          this.next = pNext;
        }
    }


    ListNode first;   
    ListNode last;    
    ListNode current;

    public List() {
        first = null;
        last = null;
        current = null;
    }

    public boolean isEmpty() {
        return first == null;
    }

    public boolean hasAccess() {
        return current != null; 
    }

    public void next() {
        if (this.hasAccess()) {
            current = current.getNextNode();
        }
    }

    public void toFirst() {
        if (!isEmpty()) {
            current = first;
        }
    }

    public void toLast() {
        if (!isEmpty()) {
            current = last;
        }
    }

    public ContentType getContent() {
        if (this.hasAccess()) {
            return current.getContentObject();
        } else {
            return null;
        }
    }

    public void setContent(ContentType pContent) {

        if (pContent != null && this.hasAccess()) { 
            current.setContentObject(pContent);
        }
    }

    public void insert(ContentType pContent) {
        if (pContent != null) { 
            if (this.hasAccess()) { 
                ListNode newNode = new ListNode(pContent); 

                if (current != first) { 
                    ListNode previous = this.getPrevious(current);
                    newNode.setNextNode(previous.getNextNode());
                    previous.setNextNode(newNode);
                } else { 
                    newNode.setNextNode(first);
                    first = newNode;
                }
            } else {
                if (this.isEmpty()) {
                    ListNode newNode = new ListNode(pContent); 

                    first = newNode;
                    last = newNode;
                }
            }
        }
    }

    public void append(ContentType pContent) {
        if (pContent != null) {
            if (this.isEmpty()) { 
                this.insert(pContent);
            } else { 
                ListNode newNode = new ListNode(pContent); 

                last.setNextNode(newNode);
                last = newNode;    
            }
        }
    }

    public void concat(List<ContentType> pList) {
        if (pList != this && pList != null && !pList.isEmpty()) { 

            if (this.isEmpty()) { 
                this.first = pList.first;
                this.last = pList.last;
            } else { 
                this.last.setNextNode(pList.first);
                this.last = pList.last;
            }

            pList.first = null;
            pList.last = null;
            pList.current = null;
        }
    }

    public void remove() {
        if (this.hasAccess() && !this.isEmpty()) { 
            if (current == first) {
                first = first.getNextNode();
            } else {
                ListNode previous = this.getPrevious(current);
                if (current == last) {
                    last = previous;
                }
                previous.setNextNode(current.getNextNode());
            }

            ListNode temp = current.getNextNode();
            current.setContentObject(null);
            current.setNextNode(null);
            current = temp;
  
            if (this.isEmpty()) {
                last = null;
            }
        }
    }

    private ListNode getPrevious(ListNode pNode) {
        if (pNode != null && pNode != first && !this.isEmpty()) {
            ListNode temp = first;
            while (temp != null && temp.getNextNode() != pNode) {
                temp = temp.getNextNode();
            }
            return temp;
        } else {
            return null;
        }
    }

    public int length() {
        int i = 0;
        while(this.hasAccess()) {
            i++;
            next(); 
        }
        return i;
    }
}

This is my version of the wanted method it should randomly rearrange the list by swapping objects multiple times but it apparently does not work.

public static void shuffleList(final List<String[]> list) {

    int length = list.length();
    Random random = new Random();

    for (int i = 0; i < length; i++) {

        // Swap index
        int swap = i + random.nextInt(length - i);

        // Store temporarily
        String name1 = list.getContent()[0];
        String surname1 = list.getContent()[1];
        String[] temp1 = {mail1, pw1};
            
        System.out.println(temp1);
            
        for (int j = 0; j < swap; j++) {
            list.next();
        }

        String name2 = list.getContent()[0];
        String surname2 = list.getContent()[1];
        String[] temp2 = {mail2, pw2};
            
        // Set the values
        list.setContent(temp1);
            
        list.toFirst();
        for (int k = 0; k < i; k++) {
            list.next();
        }
        list.setContent(temp2);
    }
}

I would be very glad if somebody could help me find a way to swap elements inside of my list so that I can finally get my method to randomly rearrange the list.

Thank you for every answer! :)

"person (array containing two elements name and surname inside the list)" — Please don't do that. Don't represent a person with a string array. Instead, create a class Person with attributes firstname and lastname. — MC Emperor
– MC Emperor, Commented Jul 26, 2021 at 19:25
shuffling a linked list like this can be done like shuffling a card deck: imagine you split it in half and then you take one element from the left halve and then append another element from the right halve. In your doubly-linked list this doesn't require a swap method. — Thomas Jungblut
– Thomas Jungblut, Commented Jul 26, 2021 at 20:03
You are right, somehow I was not creative enough to think of that myself, thank you as well! :) — neb737
– neb737, Commented Jul 26, 2021 at 20:31

geobreze · Accepted Answer · 2021-07-26 19:56:21Z

I would suggest firstly converting your list to an array, so you have O(1) random access, then shuffle this array and after that replace values in your list.

Here is a code

public class ListUtils {

    /**
     * Shuffles a list, leaving it's pointer on the first element.
     * 
     * @param list list to shuffle
     * @param rnd random number generator
     */
    @SuppressWarnings({"unchecked"})
    public static <T> void shuffleList(List<T> list, Random rnd) {
        Object[] arr = toArray(list);

        for (int i = arr.length; i > 1; --i) {
            swap(arr, i - 1, rnd.nextInt(i));
        }

        list.toFirst();
        for (Object o : arr) {
            list.setContent((T) o);
            list.next();
        }
    }

    private static void swap(Object[] arr, int i, int j) {
        Object temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    private static Object[] toArray(List<?> list) {
        // length is O(n), makes sense to track size on every add, so it will be O(1)
        list.toFirst();
        int size = list.length();
        Object[] result = new Object[size];
        list.toFirst();
        for (int i = 0; i < size; ++i) {
            result[i] = list.getContent();
            list.next();
        }
        return result;
    }

    public static void main(String[] args) {
        List<String> l = new List<>();
        l.append("a");
        l.append("b");
        l.append("c");
        l.append("d");
        shuffleList(l, new Random());
        l.toFirst();
        while (l.hasAccess()) {
            System.out.println(l.getContent());
            l.next();
        }
    }
}

Collectives™ on Stack Overflow

How to randomize ArrayList without using Collections.swap()?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related