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".

    Java program memory state. 1 stack frame; 5 heap objects.Stack frame: main:8 LinkedBasedList myList: reference to object 592 Node temp: reference to object 593 Heap object 593: Node@593 String item: reference to object 557, "A" Node next: reference to object 594 Heap object 594: Node@594 String item: reference to object 556, "B" Node next: reference to object 595 Heap object 595: Node@595 String item: reference to object 559, "C" Node next: reference to object 596 Heap object 596: Node@596 String item: reference to object 597, "D" Node next: null Heap object 592: LinkedBasedList@592 int size: 4 Node head: reference to object 593{"summary":"Java program memory state. 1 stack frame; 5 heap objects.","sections":[{"heading":"Stack frame: main:8","items":["LinkedBasedList myList: reference to object 592","Node temp: reference to object 593"]},{"heading":"Heap object 593: Node@593","items":["String item: reference to object 557, \"A\"","Node next: reference to object 594"]},{"heading":"Heap object 594: Node@594","items":["String item: reference to object 556, \"B\"","Node next: reference to object 595"]},{"heading":"Heap object 595: Node@595","items":["String item: reference to object 559, \"C\"","Node next: reference to object 596"]},{"heading":"Heap object 596: Node@596","items":["String item: reference to object 597, \"D\"","Node next: null"]},{"heading":"Heap object 592: LinkedBasedList@592","items":["int size: 4","Node head: reference to object 593"]}]}main:8LinkedBasedListmyList592Nodetemp593Node@593Stringitem557"A"Nodenext594Node@594Stringitem556"B"Nodenext595Node@595Stringitem559"C"Nodenext596Node@596Stringitem597"D"NodenextnullLinkedBasedList@592intsize4Nodehead593

    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.

    Java program memory state. 1 stack frame; 5 heap objects.Stack frame: main:9 LinkedBasedList myList: reference to object 596 Node temp: reference to object 597 Heap object 598: Node@598 String item: reference to object 541, "A" Node next: reference to object 597 Heap object 597: Node@597 String item: reference to object 545, "B" Node next: reference to object 599 Heap object 599: Node@599 String item: reference to object 548, "C" Node next: reference to object 600 Heap object 600: Node@600 String item: reference to object 601, "D" Node next: null Heap object 596: LinkedBasedList@596 int size: 4 Node head: reference to object 598{"summary":"Java program memory state. 1 stack frame; 5 heap objects.","sections":[{"heading":"Stack frame: main:9","items":["LinkedBasedList myList: reference to object 596","Node temp: reference to object 597"]},{"heading":"Heap object 598: Node@598","items":["String item: reference to object 541, \"A\"","Node next: reference to object 597"]},{"heading":"Heap object 597: Node@597","items":["String item: reference to object 545, \"B\"","Node next: reference to object 599"]},{"heading":"Heap object 599: Node@599","items":["String item: reference to object 548, \"C\"","Node next: reference to object 600"]},{"heading":"Heap object 600: Node@600","items":["String item: reference to object 601, \"D\"","Node next: null"]},{"heading":"Heap object 596: LinkedBasedList@596","items":["int size: 4","Node head: reference to object 598"]}]}main:9LinkedBasedListmyList596Nodetemp597Node@598Stringitem541"A"Nodenext597Node@597Stringitem545"B"Nodenext599Node@599Stringitem548"C"Nodenext600Node@600Stringitem601"D"NodenextnullLinkedBasedList@596intsize4Nodehead598

    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.

    Java program memory state. 1 stack frame; 5 heap objects.Stack frame: main:10 LinkedBasedList myList: reference to object 615 Node temp: reference to object 616 Heap object 617: Node@617 String item: reference to object 541, "A" Node next: reference to object 619 Heap object 619: Node@619 String item: reference to object 545, "B" Node next: reference to object 616 Heap object 616: Node@616 String item: reference to object 548, "C" Node next: reference to object 618 Heap object 618: Node@618 String item: reference to object 601, "D" Node next: null Heap object 615: LinkedBasedList@615 int size: 4 Node head: reference to object 617{"summary":"Java program memory state. 1 stack frame; 5 heap objects.","sections":[{"heading":"Stack frame: main:10","items":["LinkedBasedList myList: reference to object 615","Node temp: reference to object 616"]},{"heading":"Heap object 617: Node@617","items":["String item: reference to object 541, \"A\"","Node next: reference to object 619"]},{"heading":"Heap object 619: Node@619","items":["String item: reference to object 545, \"B\"","Node next: reference to object 616"]},{"heading":"Heap object 616: Node@616","items":["String item: reference to object 548, \"C\"","Node next: reference to object 618"]},{"heading":"Heap object 618: Node@618","items":["String item: reference to object 601, \"D\"","Node next: null"]},{"heading":"Heap object 615: LinkedBasedList@615","items":["int size: 4","Node head: reference to object 617"]}]}main:10LinkedBasedListmyList615Nodetemp616Node@617Stringitem541"A"Nodenext619Node@619Stringitem545"B"Nodenext616Node@616Stringitem548"C"Nodenext618Node@618Stringitem601"D"NodenextnullLinkedBasedList@615intsize4Nodehead617

    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.