Amazon Wipro Technologies Interview Question
Software Engineer / DevelopersO(1) time to add an element to a linked list...also, linked list doesn't have a fixed size, so there will be no need to copy elements (like when you run out of space in a fixed-sized array), which is a very costly operation.
I think saying arrays should be used always would be wrong. One should make a choice depending on the requirements:
Both arrays and linked lists are for storing objects of the same type.
Arrays:
- you know the number of elements before hand. If size is dynamic choice, arrays are a wrong (or costly) choice.
- element access time is importanta. It is O(1) for arrays and O(n) for linked lists
linked lists:
- when number of elements is unknown or dynamic
- suitable for representing trees and so on
Use arrayList in .net and have best of both. (Ok keeping in mind that capacity is well planned).
I really can't agree with you that an arraylist is the best of both worlds. Sure, an arraylist beats an array (one that's dynamic anyway), but it doesn't necessarily beat a linked list. A crucial difference is that element can be inserted in sorted order into a linked list quickly and efficiently.
It's also somewhat misleading to say that linked lists are suitable for representing trees. Although the data structures have some things in common, they are different data structures. A linked list cannot represent a tree.
Agreed. linked list is not suitable for a tree (an adjacency list is more approp)...I was thinking in terms of a binary tree where each node maintains a list of parent/ child etc...same with inserting into an ArrayList. Usually I have a wrapper around arrayList which provides me sorted insert and so on. Thanks for your comments.
Linked List:
? They allow a new element to be inserted or deleted at any position in a constant number of operations (changing some references) O(1).
? Easy to delete a node (as it only has to rearrange the links to the different nodes).
? To find the nth node, will need to recurse through the list till it finds [linked lists allow only sequential access to elements. ]
Array
? Insertion or deletion of element at any position require a linear (O(n)) number of operations.
? Poor at deleting nodes (or elements) as it cannot remove one node without individually shifting all the elements up the list by one.
? Poor at inserting as an array will eventually either fill up or need to be resized, an expensive operation that may not even be possible if memory is fragmented. Similarly, an array from which many elements are removed may become wastefully empty or need to be made smaller
? easy to find the nth element in the array by directly referencing them by their position in the array.[ arrays allow random access ]
Array Linked list
Indexing O(1) O(n)
Inserting O(n) O(1)
Deleting O(n) O(1)
Apart from the above differences, one important use of linked lists is to store persistent data (be able to access old data after new data is added) easily. If there is an array, and some changes are made to this array but you still want to be able to see the old array, the only way you can do this is by copying the entire array into a new array and making changes to the copy.
In a linked list, lets say you just want to change the front portion of a linked list, then you create a new front portion and at the end of this front portion, point to the old back portion (In effect, this lets you share the back portion).
If the change is random, you can come up with operations, which will point to appropriate old portions.
Hi Gayle,
Inserting elements in sorted order will take O(n) in both arrays and linked-list. This is so because in arrays you have to move O(N) elements elements while in linked-list you have travel through O(N) nodes.
In fact, moving elements can be faster because of locality-of-reference of arrays.
Please correct me where I a wrong.
hi all..
answers i found here are good. i wanna give my answer here itself
in my view:
Mainly there are 4 importent factors which are responsible to use any array.
1.accessing time. If your application needs faster speed, then elements insertion(if array is empty and if no need to insert in the middle of an array) or extraction data. This gives advantage over linked-list.
2.if there are fixed number of elements you want to enter.
3. if ur program is for small applications and needs some what acceptible memory.(as for larger application there may not be that much of memory available serially)
4. Dealing with arrays are much easier logically than Liked-List.
so if my application needs
faster execution,
limitted and known number of elements
for easy logic,
i prefer to use Array than linked list..
Deleting/inserting a node in an array is not O(1) if the node is targeted at the front or in the middle. Deletion: the array contents would have to be shifted and the last node deallocated. Insertion: allocate a node and shift contents.
This is for a vector. For a deque, insertion/deletion in the middle is not O(1), but O(1) at front/back.
A linked list has O(1) deletion/insertion anywhere.
In case of link list while allocating nodes worst case possible scenario may be that memory gets allocated in various pages , which may result in significant page faults , degarding the performance . Whereas it may not be the same case with Array as is it a contigous allocation , provided array data elements are not of page size .
I think most people forget to think about the Hardware aspect of things, remember that Arrays give much better locality as in caching is so much better when data is in consecutive blocks with the prefetch stuff in processors etc... im sure an ECE guy would be able to better ellaborate on that point ( sorry im CS :) )
- Muhariz Jabeer April 14, 2006