Get

Returns the element at the specified position in this list.

public Node get(int index) {
}

Because of how linked lists manage memory, you cannot use indices to perform lookup operations in constant time. Unlike arrays, which allow for direct element access based on index and hence has constant time, linked lists lack the capability to compute the memory address of the i-th element.

In linked lists, locating the i-th element necessitates traversing the list through its next references. Beginning from the head node, you need to sequentially follow these references until you arrive at the desired node. Consequently, lookups and search operation in a linked list have linear worst-case time complexity - O(n).

Case: Index is out of range

If index is

• less than 0 or
• equal to than linked list length or
• greater than linked list length

simply return null

public class LinkedList {
    
    public Node get(int index) {
        if (index < 0 || index >= length) return null;
    }
}

Case: Index is in range

In this case, you need to start from head and traverse through its next until desired node of index is found.

public class LinkedList {
    
    public Node get(int index) {
        if (index < 0 || index >= length) return null;
        int count = 0;
        Node node = head;
        while (count != index) {
            node = node.next; // traverse to next node, when count matches index this is the desired node
            count++; // increment count after each traverse
        }
        return node;
    }
}

Testing

public class LinkedListTest {

    @Test
    void get() {
        LinkedList linkedList = new LinkedList();
        linkedList.append(11);
        linkedList.append(12);

        // when index is out of range
        assertNull(linkedList.get(-2));
        assertNull(linkedList.get(7));

        // when index is in range
        assertEquals(11, linkedList.get(0).getValue());
        assertEquals(12, linkedList.get(1).getValue());
    }
}

Time Complexity

As discussed above this operation has worst-case time complexity of O(n).