Qualcomm Interview Question
Country: United States
Interview Type: Phone Interview
What do you mean by contiguous memory locations? Physical or Virtual ?
AFAIK, it might as well be virtual.
So I am not able to justify why they should be faster. One index of the array could be in one page and the other in another page mbs away. So why would that make it any faster or result in better cache behavior?
First, there is no requirement for random access, only iterate one by one.
In this case, continuous memory does not matter so much.
It really depends on the Link List implementation and the size.
If it is a normal size data, array will be a little faster.
But if it is a really big size, link list may be faster because it does not need allocate the big continuous memory block for data loading.
Arrays are continous memory blocks hence indexing and searching is faster than linked list
linked lists are nodes pointing to other nodes so to find the 200th node in a linked list of 10,000 nodes you would have to traverse 200 nodes
it is easier to faster to add a node anywhere in the linked list and push the right half of the nodes by 1 place since it involves just changing the prev nodes pointer and pointing the new node to next node hence it is of constant time O(1)
same goes for deleting
Though the question suggests that we just need to iterate in a for loop and print it, saying that it would almost be the same in either case and that the difference would be at the assembly level like prem has suggested would probably be correct. But pointing out that if we are allowed only a Singly Linked list and we are to iterate from the last element to the first then Array would be faster, would fetch additional points from the interviewer I suppose.
Well we all know that Array Access is faster of course .. The main reason is as follows
As it is just to iterate the loop , many may get confused as we need loop in both case but the main question here is..
Struct Node *ptr=node -> next;
and
array[counter+1].
Now if you beak this into assembly language, it is sure that array would hv lesser Instruction to execute than LL (people may try writing the assembly to verify).
Now as we knw the each instruction may take 1 / 2 / 3 CPU cycles to execute .. then you can verify why Array access always results faster than LL
Plz correct me if i am wrong.
in array, it is done by Increamenting the pointer by a fixed known amount.
whereas in case of ll first it will have to access the amount to be increased by accessing the
->next value.
so, in case of array accessing time is saved. So it would be faster.
in an array since u know the index in the continuous memory block, u can directly access the element in O(1)
I wonder not to see a basic difference discussed...
array is on stack & Link list is on heap. Access to stack memory is predictable and faster... while with link list it is not...
I hold reservation about the answer. Value of an array can be accessed by offset, too. See the discussion here. h-t-t-p://stackoverflow.com/questions/5445131/why-are-linked-lists-faster-than-arrays
In an array, the values are stored contiguously, and therefore there should be fewer memory ops and fewer cache misses as well. Generally this is likely to trump the cost of a pointer addition. Besides, in the linked list, even things like list = list->next can involve an arithmetic calculation for the address (internally it becomes something like list = contents of memory ( list + offset of field named "next").
I didn't thought of cache misses. That looks like more prominent reason for arrays to be faster.
Array Elements are stored in contiguous memory locations. Hence they will be faster to retrieve.
- devenster March 15, 2013