Question

In JAVA Implement the moveMinToFront method in IntSinglyLinkedList. The moveMinToFront method looks through the list to find the element with the minimum value. It moves that element to the front of the list.

Before abstract view: [7, 3, 2]

After Abstract view: [2,7,3]

Before Abstract view: [4,1,7]

After Abstract view: [1,4,7]

public void moveMinToFront() {

}

Test:

package net.datastructures;

import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertTrue;

import java.util.Random;

public class IntSinglyLinkedListTest {
    @Test
    public void moveMinToFrontTestEmpty() {
        IntSinglyLinkedList s = new IntSinglyLinkedList();
        s.moveMinToFront();
        assertTrue(s.isEmpty());
    }

    @Test
    public void moveMinToFrontTest1() {
        IntSinglyLinkedList s = new IntSinglyLinkedList();
        s.addLast(10);
        s.addLast(20);
        s.addLast(30);
        s.addLast(40);
        s.addLast(50);
        s.moveMinToFront();
        assertEquals(10, (int)s.first());
        assertEquals(5, (int)s.size());
        assertEquals(50, (int)s.last());
    }

    @Test
    public void moveMinToFrontTest2() {
        IntSinglyLinkedList s = new IntSinglyLinkedList();
        s.addLast(20);
        s.addLast(15);
        s.addLast(30);
        s.addLast(40);
        s.addLast(50);
        s.addLast(60);
        s.addLast(70);
        s.addLast(80);
        s.moveMinToFront();
        assertEquals(15, (int)s.first());
        assertEquals(8, (int)s.size());
        assertEquals(80, (int)s.last());
    }

    @Test
    public void moveMinToFrontTest3() {
        IntSinglyLinkedList s = new IntSinglyLinkedList();
        s.addFirst(10);
        s.addFirst(20);
        s.addFirst(30);
        s.addFirst(40);
        s.addFirst(50);
        s.moveMinToFront();
        assertEquals(10, (int)s.first());
        assertEquals(5, (int)s.size());
        assertEquals(20, (int)s.last());
    }

    @Test
    public void moveMinToFrontTest4() {
        IntSinglyLinkedList s = new IntSinglyLinkedList();
        s.addFirst(20);
        s.addFirst(15);
        s.addFirst(30);
        s.addFirst(40);
        s.addFirst(50);
        s.addFirst(60);
        s.addFirst(70);
        s.addFirst(80);
        s.moveMinToFront();
        assertEquals(15, (int)s.first());
        assertEquals(8, (int)s.size());
        assertEquals(20, (int)s.last());
    }

    @Test
    public void moveMinToFrontTest5() {
        IntSinglyLinkedList s = new IntSinglyLinkedList();
        Random r = new Random(111);
        int min = Integer.MAX_VALUE;
        int last = Integer.MAX_VALUE;
        final int lengthOfList = 100;
        for (int i=0; i<lengthOfList; i++) {
            int x = r.nextInt(2000);
            min = Math.min(x, min);
            s.addLast(x);
            last = x;
        }
        s.moveMinToFront();
        assertEquals(min, (int)s.first());
        assertEquals(lengthOfList, (int)s.size());
        assertEquals(last, (int)s.last());
    }
}

Answer 1

If you have any doubts, please give me comment...

class Node{

    private int data;

    private Node next;

    public Node(){}

    public Node(int val){

        data = val;

        next = null;

    }

    public Node(int val, Node _next){

        data = val;

        next = _next;

    }

    /**

     * @return the data

     */

    public int getData() {

        return data;

    }

    /**

     * @return the next

     */

    public Node getNext() {

        return next;

    }

    /**

     * @param data the data to set

     */

    public void setData(int data) {

        this.data = data;

    }

    /**

     * @param next the next to set

     */

    public void setNext(Node next) {

        this.next = next;

    }

}

public class IntSinglyLinkedList{

    private Node start;

    public IntSinglyLinkedList(){

        start = null;

    }

    // some other methods...

    public void moveMinToFront() {

        Node temp = start;

        Node prev = null;

        Node minNode = start;

        Node prevMin = null;

        while(temp!=null){

            if(minNode.getData() > temp.getData()){

                minNode = temp;

                prevMin = prev;

            }

            prev = temp;

            temp = temp.getNext();

        }

        if(temp!=start){

            prevMin.setNext(minNode.getNext());

            minNode.setNext(start);

            start = minNode;

        }

    }

}