Storage:
1) Arrays are statically allocated whereas linked list are dynamically allocated and linked.
Generally, if the number of allocations are known before hand, we use arrays. Otherwise linked list
Performance:
2) Array is a high performance way of storing a group of data because each element is laid out next to it's neighbor in memory. This allows for very fast access because (a) the code can do a little math and jump quickly to any location in the array, and (b) the elements are all grouped together so they tend to be in memory at the same time (fewer page faults and cache misses).
3) If you want to index by something like a string, you could use a hash table. Lets say you have a list of players, and you want to pull an object up from each player's name. You take the string, run a hash function to convert that into a number that falls within the range of an array, and store it in that element.
Or, you can have a linked list faster by breaking it into subelements. For example, if you were storing words in a dictionary, you could have an array of linked lists with 26 entries for a-z. That way when you manipulate a list, you are manipulating a much smaller subset.
Side note:
1) Java provides arraylist (java.util.ArrayList) option to programmers. So whether ArrayList better than array ?
If the data has a known number of elements or small fixed size upper bound, or where efficiency in using primitive types is important, arrays are often the best choice. However, many data storage problems are not that simple, and ArrayList (or one of the other Collections classes) might be the right choice.
2) How Arraylist are created ?
What is linked list? Refresh the basics
Linked list problems:
18 problems, stanford.edu (pdf)
Common Questions on linked lists ?
1) What's the difference between a linked list and an array?
2) Implement a linked list. Why did you pick the method you did?
3) Implement an algorithm to sort a linked list. Why did you pick the method you did? Now do it in O(n) time.
4) Implement an algorithm to reverse a linked list. Now do it without recursion.
5) Find the middle of a linked list. Now do it while only going through the list once
6) Implement an algorithm to insert a node into a circular linked list without traversing it.
7) How would you print out the data in a binary tree, level by level, starting at the top?
8) Write code for reversing a linked list.
9 ) Reverse the words in a sentence, i.e. "My name is Chris" becomes "Chris is name My." Optimize for speed. Optimize for space.
10)Implement Insert and Delete for
--singly-linked linked list
--sorted linked list
--circular linked list
Some helpful links:
maxnoy.com
columbia.edu
sellsbrother.com