Skip to main content
Engineering LibreTexts

5.2: Profiling LinkedList methods

  • Page ID
    12751
  • In the previous exercise you also profiled the performance of adding new elements at the beginning of a LinkedList. Based on our analysis, we expect each add to take constant time, because in a linked list, we don’t have to shift the existing elements; we can just add a new node at the beginning. So we expect the total time for n adds to be linear.

    Here’s a solution:

    public static void profileLinkedListAddBeginning() {
        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(0, "a string");
                }
            }
        };
        int startN = 128000;
        int endMillis = 2000;
        runProfiler("LinkedList add beginning", timeable, startN, endMillis);
    } 
    

    We only had a make a few changes, replacing ArrayList with LinkedList and adjusting startN and endMillis to get a good range of data. The measurements were noisier than the previous batch; here are the results:

    128000, 16
    256000, 19
    512000, 28
    1024000, 77
    2048000, 330
    4096000, 892
    8192000, 1047
    16384000, 4755
    

    Figure 5.3.1 shows the graph of these results.

    It’s not a very straight line, and the slope is not exactly 1; the slope of the least squares fit is 1.23. But these results indicate that the total time for n adds is at least approximately \( O(n) \), so each add is constant time.