8.5. Linked List Get Operation

In this section, we will take a closer look at the get(int index) operation with a linked list implementation.

The main drawback of a linked list implementation is that elements are slower to access. Each access requires the program to traverse from the head of the list to the desired index. The images below demonstrate how this might be accomplished if the instruction myList.get(2) is executed.

  1. A reference, temp, is assigned to the head of the list (index 0).

    first get image

  2. We move temp to the next node in the list. Now, temp is located at index 1. We avoid modifying head as to not change the list itself. If we were to lose the head reference, we would lose access to the first node in the list.

    second get image

  3. We move temp to the next node in the list. Now, temp is located at index 2, which is our desired destination. At this point, we can return value from the Node object referenced by temp as that is the value we want.

    third get image

Compare this method to arrays where we would simply return array[2]. With an array implementation, the program can directly access the requested index (one of the benefits of arrays). Traversing the links in a linked list implementation is more costly. Especially when the desired element is located toward the end of a long linked list.