How to shift array list elements to the right with some index at fixed position in java

Question

I have an array list with a size of 10 elements. What I am trying to achieve here is that when I add an element at any index, the element which is next to it should get shifted except at some fixed indexes.

For example, Let's say my array list is as follows

[10, 20, 30, 40, 50,60,70,80,90,100]

indexes are {0,1,2,3,4,5,6,7,8,9}

fixed indexes{4,6}

when I remove an element from index 10 and add an index 3 the output should be as follows

[10, 20, 30, 100, 50, 40,70,60,80,90,]

if you notice the values at indexes {4,6} did not change after adding 10 th element at index 3.

    List<Integer> values = new ArrayList<>();
    values.add(10);
    values.add(20);
    values.add(30);
    values.add(40);
    values.add(50);
    values.add(60);
    values.add(70);
    values.add(80);
    values.add(90);
    values.add(100);
    System.out.println(values);

    values.removeAt(9)
    values.add(3,100);
    System.out.println(values);

    # Output
    [10, 20, 30, 40, 50,60,70,80,90,100]
    [10, 20, 30, 100, 40,50,60,70,80,90]

If anyone can Suggest any sorting method or collections to achieve this it will be really helpful.

Sample input and outputs:

int[] a= [7, 4, 3, 2, 1, 5, 6, 4, 8, 9] and fixed indexes are {1,2}

Remove 6th index element (6) and add at index 0 The output should be as follows:

[6, 4, 3, 7, 2, 1, 5, 4, 8, 9]

Answer 1

There'is a special trick to do it in place and O(n) time.

[0,1,2,3,4,5,6,7,8,9] // init -> swapt 3 positions to the right
[9,8,7,6,5,4,3,2,1,0] // 1st rotate
[7,8,9,6,5,4,3,2,1,0] // 2nd rotate
[7,8,9,0,1,2,3,4,5,6] // 3rd rotate

---

public static void rotate(int[] arr, int k) {
    if ((k %= arr.length) != 0) {
        k = k < 0 ? arr.length + k : k;
        swapSubArr(arr, 0, arr.length);
        swapSubArr(arr, 0, arr.length - k);
        swapSubArr(arr, arr.length - k, arr.length);
    }
}

private static void swapSubArr(int[] arr, int from, int to) {
    for (int i = from, j = to - 1; i < j; i++, j--)
        swap(arr, i, j);
}

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

Answer 2

Here's my simple solution making use of the existing ArrayList class, though it might be best if you define your own implementation to meet your needs. Note that you may need to override more methods if you want to be sure they adhere to the rules you define:

public static class FixableArrayList<T> extends ArrayList<T> {

    // ascending and descending views of the fixed indices
    private final SortedSet<Integer> fixedAsc;
    private final SortedSet<Integer> fixedDec;

    public FixableArrayList() {
        TreeSet<Integer> treeSet = new TreeSet<>();
        fixedAsc = treeSet;
        fixedDec = treeSet.descendingSet();
    }

    public boolean addFixedIndex(int ind) { return fixedAsc.add(ind); }
    public boolean removeFixedIndex(int ind) { return fixedAsc.remove(ind); }

    public void move(int fromInd, int toInd) {
        if (fromInd == toInd) {
            return;
        }
        if (fixedAsc.contains(fromInd)) {
            throw new IllegalArgumentException("Cannot remove from fixed index: " + fromInd);
        }
        if (fixedAsc.contains(toInd)) {
            throw new IllegalArgumentException("Cannot add to fixed index: " + toInd);
        }

        super.add(toInd, super.remove(fromInd));

        if (toInd < fromInd) {
            // all between `from` and `to` shifted up, swap fixed indices down back into position
            // iterate from low (toInd) to high (fromInd)
            for (int i : fixedAsc.subSet(toInd, fromInd)) {
                super.add(i, super.remove(i + 1));
            }
        } else {
            // all between `from` and `to` shifted down, swap fixed indices up back into position
            // iterate from high (toInd) to low (fromInd)
            for (int i : fixedDec.subSet(toInd, fromInd)) {
                super.add(i, super.remove(i - 1));
            }
        }
    }
}

public static void main(String[] args) {
    FixableArrayList<Integer> values = new FixableArrayList<>();
    values.addAll(Arrays.asList(10, 20, 30, 40, 50, 60, 70, 80, 90, 100));

    // set the indices that you want to remain fixed
    values.addFixedIndex(3);
    values.addFixedIndex(5);
    values.addFixedIndex(9);

    System.out.println(values);

    values.move(0, 8);
    System.out.println(values);

    values.move(8, 0);
    System.out.println(values);
}

Answer 3

I think the only possible way is to loop through the list and create a new list and have a check for the two indices that when they occur then don't replace them and put the same value from the older list.

You can have a method in which you pass your parameters for the change you want and the indices those are fixed and in that method you can create a new list based on the passed parameters.