5.3: Adding to the end of a LinkedList

Adding elements at the beginning is one of the operations where we expect LinkedList to be faster than ArrayList.

Figure \(\PageIndex{1}\): Profiling results: run time versus problem size for adding n elements at the beginning of a LinkedList.

But for adding elements at the end, we expect LinkedList to be slower. In my implementation, we have to traverse the entire list to add an element to the end, which is linear. So we expect the total time for n adds to be quadratic.

Well, it’s not. Here’s the code:

public static void profileLinkedListAddEnd() {
    Timeable timeable = new Timeable() {
        List<String> list;
        
        public void setup(int n) {
            list = new LinkedList<String>();
        }
        
        public void timeMe(int n) {
            for (int i=0; i<n; i++) {
                list.add("a string");
            }
        }
    };
    int startN = 64000;
    int endMillis = 1000;
    runProfiler("LinkedList add end", timeable, startN, endMillis);
}

Here are the results:

64000, 9
128000, 9
256000, 21
512000, 24
1024000, 78
2048000, 235
4096000, 851
8192000, 950
16384000, 6160

Figure \(\PageIndex{2}\) shows the graph of these results.

Figure \(\PageIndex{2}\): Profiling results: runtime versus problem size for adding n elements at the end of a LinkedList.

Again, the measurements are noisy and the line is not perfectly straight, but the estimated slope is 1.19, which is close to what we got adding elements at the beginning, and not very close to 2, which is what we expected based on our analysis. In fact, it is closer to 1, which suggests that adding elements at the end is constant time. What’s going on?