Question

Data Structures ( Recursion )

Assignment

Write a recursive method removeMiddle that receives an array list which has odd number of elements, then it deletes the element in the middle only. The method should receive only one parameter (the array list)

The base case is when the array list has only one element, just remove that, otherwise, you need to remove the first one and the last one then call the method, then you need to add them again after the recursive call.

java language

Answer 1

import java.util.*;
public class RemoveMiddle{
    
public static void removeMidRecursive(ArrayList<Integer> Arrlist) {
    System.out.println("recursive: " + Arrlist);
    if (Arrlist.size() % 2 == 0) {
        System.out.println("list size is even, no middle element to remove");
    } else if (Arrlist.size() == 1) {
        int mid = Arrlist.remove(0);
        System.out.println("removed mid element: " + mid);
    } else {
        // find indexes of min and max elements
        int minId = 0;
        int maxId = 0;
        for (int i = 1; i < Arrlist.size(); i++) {
            int val = Arrlist.get(i);
            if (val < Arrlist.get(minId)) {
                minId = i;
            } else if (val >= Arrlist.get(maxId)) {
                maxId = i;
            }
        }

        // sort the indexes
        int tMin = Math.min(minId, maxId);
        int tMax = Math.max(minId, maxId);
        // start removing from bigger index and store the value
        // using `E remove(int index)`
        Integer atMax = Arrlist.remove(tMax);
         System.out.printf("removed Arrlist[%d]=%d%n", tMax, atMax);
        Integer atMin = Arrlist.remove(tMin);
         System.out.printf("removed Arrlist[%d]=%d%n", tMin, atMin);
        
        removeMidRecursive(Arrlist);

        // restore the values by insertig at appropriate index with a correction
        if (tMin > 0) Arrlist.add(tMin - 1, atMin); else Arrlist.add(0, atMin);
        if (tMax > 0) Arrlist.add(tMax - 1, atMax); else Arrlist.add(0, atMax);
        
        System.out.println("restored: " + Arrlist);
    }
    
}
public static void main(String[] args)
    {   
        ArrayList<Integer> li = new ArrayList<Integer>();
        li.add(1);
        li.add(2);
        li.add(3);
        li.add(4);
        li.add(5); 
            
        removeMidRecursive(li);
    }

}

output:
recursive: [1, 2, 3, 4, 5]
removed Arrlist[4]=5
removed Arrlist[0]=1
recursive: [2, 3, 4]
removed Arrlist[2]=4
removed Arrlist[0]=2
recursive: [3]
removed mid element: 3
restored: [2, 4]
restored: [1, 2, 4, 5]