8.7. Linked List Get Operation

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

To access an item by index, this implementation starts at head and follows links until it reaches the desired node. The snapshots below illustrate the traversal needed for myList.get(2) in a list containing "A", "B", "C", and "D". The list has size 4, and index 2 is valid.

Each snapshot shows the state after the described step is completed. The construction code is hidden, and the models show only the fields needed for this example. String values use a compact display: each item field stores a reference value, and the corresponding String object exists separately from the node. An arrow connects each string reference box to a literal beside it.

  1. Initialize temp with a copy of the reference value stored in myList.head. Both temp and head now refer to the node at index 0, whose item is "A".

    Code visualization diagram for java/adt-and-links/linked-list-get:24 (end of main)

    After initialization, temp and head refer to the node at index 0 (A). [download] [open]

  2. Assign temp a copy of the reference value stored in the current node's next field. Now temp refers to the node at index 1, whose item is "B". This assignment changes only temp; head still refers to the first node, and all links remain unchanged.

    Code visualization diagram for java/adt-and-links/linked-list-get:41 (end of main)

    After following one link, temp refers to index 1 (B); head still refers to index 0 (A). [download] [open]

  3. Repeat the assignment to follow the next link. Now temp refers to the node at index 2, whose item is "C". This is the desired node. The get method can return with a copy of the reference value stored in temp.item. The list's head, links, and size are unchanged throughout the traversal.

    Code visualization diagram for java/adt-and-links/linked-list-get:60 (end of main)

    After following two links, temp refers to index 2 (C); head still refers to index 0 (A). [download] [open]

Compare this traversal to an array implementation, where we can directly access items[2]. The linked list must follow two links to reach index 2. Accessing an item near the end of a longer linked list requires following more links, whereas accessing an array element by index does not require traversing the preceding elements.