JP Morgan Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
There are very big differences between a linked list and array list. As you said in a linked list every element or Node is linked together. The advantage is that to add an element to the list, lets say the beginning, has a run time of O(1). In an array list, you would need to move every element back a position, thus O(n). Array list has quicker access time O(1), while linkedlist is O(n).
ArrayList internally uses an array whereas Linkedlist uses a chain of nodes. So, ArrayList are faster for random search whereas LinkedList are more suitable for insert/delete as we only need to update the nodes in the LinkedList. Searching is slow in LinkedList as we need to do a sequential scan of all the nodes. Arraylist can use the get method for quick random access. Arraylist for insertion is good only when it is inserted at the end of the list. For inserting at the beginning or anywhere in the middle, all the relevant position of elements from the insertion point, needs to be shifted.
to sum it up, adding and deleting at the start and middle of the ArrayList is slow, because all the later elements have to be copied forward or backward. Linked lists are faster for inserts and deletes anywhere in the list, since all you do is update a few next and previous pointers of a node.
A LinkedList is ordered by index position, like ArrayList, except
that the elements are doubly-linked to one another. This linkage gives you new
methods (beyond what you get from the List interface) for adding and removing
from the beginning or end, which makes it an easy choice for implementing a stack
or queue. Keep in mind that a LinkedList may iterate more slowly than an ArrayList,
but it's a good choice when you need fast insertion and deletion. As of Java 5, the
LinkedList class has been enhanced to implement the java.util.Queue interface. As
such, it now supports the common queue methods: peek(), poll(), and offer().
ArrayList allows for O(1) lookup time since its accessible via index just like arrays. Linkedlist requires you to traverse through the list to find the element so O(n) lookup time. ArrayLists are basically arrays that automatically resize. Resizing is expensive so typically an optimized solution is to double to the size as soon as the array gets full. Deletion is faster in Linkedlists though since unlike ArrayLists, you're not using contiguous memory.
Both are similar, though slightly different in terms of goal and implementation. In a LinkedList, each element is linked to its previous and next element making it easier to delete or insert in the middle of the list. A ArrayList is more as its name subjects used as an array.
- TechTycoon February 23, 2012Performance is similar, though LinkedList is optimized when inserting elements before the end of the list, where ArrayList is optimized when adding elements at the end.