Replacing consecutive equal elements in a list with a new element In the code below I will replace all consecutive equal elements in a list with a new element. In this case I have chosen the new element to simply be the concatenation of all the equal elements, but I want the code to remain adaptable to other situations.

I have the following example:


  Input: ["a", "a", "b", "c", "d", "d", "d", "e", "f", "f", "f", "f", "g", "g"]
  Output: ["aa", "b", "c", "ddd", "e", "ffff", "gg"]


I furthermore want to perform this replacement in a single-pass, meaning in \$\mathcal{O}(n)\$ time complexity and also with \$\mathcal{O}(1)\$ storage complexity.

In the code below I have implemented a solution to this problem, I believe it still satisfies \$\mathcal{O}(n)\$ but I'm not exactly sure because it also iterates back through the list to remove the elements.

private static void replaceConsecutiveEqualElements(final List&lt;String&gt; list) {
    ListIterator&lt;String&gt; listIterator = list.listIterator();
    String previousElement = null;
    int consecutiveMatches = 1;

    // Loop through list
    while (listIterator.hasNext()) {
        String element = listIterator.next();
        String newElement = null;

        if (element.equals(previousElement)) {
            consecutiveMatches++;
        }
        else {
            // Replace consecutive elements with new element
            if (consecutiveMatches &gt;= 2) {
                listIterator.previous();
                for (int i = 0; i &lt; consecutiveMatches; i++) {
                    listIterator.previous();
                    listIterator.remove();
                }
                newElement = String.join("", Collections.nCopies(consecutiveMatches, previousElement));
                listIterator.add(newElement);
            }
            consecutiveMatches = 1;
        }

        previousElement = (newElement == null) ? element : newElement;
    }

    // Special case for last element
    // Replace consecutive elements with new element
    if (consecutiveMatches &gt;= 2) {
        for (int i = 0; i &lt; consecutiveMatches; i++) {
            listIterator.previous();
            listIterator.remove();
        }
        String newElement = String.join("", Collections.nCopies(consecutiveMatches, previousElement));
        listIterator.add(newElement);
    }
}


Called like:

List&lt;String&gt; data = new ArrayList&lt;&gt;(Arrays.asList("a", "a", "b", "c", "d", "d", "d", "e", "f", "f", "f", "f", "g", "g"));
replaceConsecutiveEqualElements(data);


I'm not happy at all with this code and am looking for feedback.

I have also decided to implement this in a functional programming language, in my case Clojure, though I have removed the time and storage complexity constraints.

(defn replace-consecutive-equal [seq]
  (-&gt;&gt; seq
       (partition-by identity)
       (map (partial apply str))))

(println (replace-consecutive-equal '("a", "a", "b", "c", "d", "d", "d", "e", "f", "f", "f", "f", "g", "g")))


The Clojure code roughly performs the following steps:


Take the input: ["a", "a", "b", "c", "d", "d", "d", "e", "f", "f", "f", "f", "g", "g"]
Partition it by the identify function: [["a", "a"], ["b"], ["c"], ["d", "d", "d"], ["e"], ["f", "f", "f", "f"], ["g", "g"]]
Apply the str function on the elements of the inner lists via a map on the outer list, the str function effectively joins strings: ["aa", "b", "c", "ddd", "e", "ffff", "gg"]


As you can see this would have made the implementation a whole lot easier, unfortunately this is not possible due to the listed constraints.

Note: I am aware that this may be a case of premature optimization, but I feel that it is important to know how to implement such an algorithm efficiently.
You can remove the elements directly while iterating to avoid the back-iterating which would remove most of the method body. The add-call can be combined with one of the remove-calls to allow using set instead.

To reduce the amount of data to copy in case that your list is an ArrayList, the iterator should iterate the list backwards (assuming that you don't want to have a separated version for random-access lists):

private static void replaceConsecutiveEqualElements(
        final List&lt;String&gt; list) {
    ////
    for (final ListIterator&lt;String&gt; it = list.listIterator(list.size()); it.hasPrevious();) {
        final String sentinel = it.previous();
        int c = 0;
        for (; it.hasPrevious(); c++, it.remove()) {
            if (!it.previous().equals(sentinel)) {
                it.next();
                break;
            }
        }
        if (c != 0) {
            it.next();
            it.set(String.join("", Collections.nCopies(c + 1, sentinel)));
            it.previous();
        }
    }
}