(double) link list get() complexity

Question

Why in double link list complexity of get(index) is equal O(n) not O(1)? Why it isn't like in array O(1) ? Is it because we have to traverse through previous nodes to get one ?

Answer 1

Yes, having to "traverse through previous nodes to get one" is exactly it.

In a linked list, to find element # n, you would use something like:

def getNodeNum (n):
    node = head
    while n > 0 and node != NULL:
        n = n - 1
        node = node.next
    return node

The reason an array is O(1) is because all the elements are laid out in contiguous memory. To get the address of element 42, you simply multiply 42 by the element size and then add the array base. This has the same cost for element number 3 as it does for element number 999.

You can't do that with a list because the elements are not necessarily contiguous in memory, hence you have to walk the list to find the one you desire. Thus the cost for finding element number 3 is actually far less than the cost for finding element number 999.

Answer 2

This is by definition. As you suspected, to get to the i-th element in the list, all previous items must be traversed.

As an exercise, implement a linked list for yourself.