Поиск наиболее частой строки в отсортированном списке ArrayList без использования HashMap

What is the easiest way to find the most common element without using Hashmaps?

Я бы сказал (Java 8+), что это довольно просто:

String str = list.stream()
                 .distinct()
                 .max(Comparator.comparing(e -> Collections.frequency(list, e)))
                 .get();

Это создаст Stream из List и найдет элемент с наибольшей частотой в List.

And what are the advantages, if there are any, of having a sorted ArrayList when we need we need to find the most common element?

Представьте себе несортированный List:

[dog, cat, turtle, cat, dog, snake]

Для каждого элемента вам придется поискать остальную часть List, чтобы узнать, сколько раз он встречается.

Однако с отсортированным List:

[dog, dog, cat, cat, snake, turtle]

У вас должен быть только счетчик, чтобы отслеживать самый длинный подсписок, содержащий те же элементы. Затем он превращается в нечто вроде (псевдокода):

//T being the type of the List
T element
int count = 0;
int biggestCount = 0;
for(every element in the list) {
   if the item is the same as previous
      count++
   else 
      //Only check when we're about to change elements
      if count > biggestCount
          biggestCount = count
          element = current element of List
      //Starting over with a new element
      count = 1
}
return element