What is the difference between linked list and Array and which is better?

Answer 1

An array is a consecutive chunk of memory with a fixed size that can be accessed directly and randomly.

A linked list has no fixed size (it can grow or shrink) and does not fit in a block of memory the way an array does.

Depending on your usage requirements either might be better than the other. If you require fast, random, direct access to an element and don't have to worry about changing the size of a list than an array may work out better for you than a linked list.

If you don't know the maximum number of elements in your list, or it can grow or shrink, and you don't need to access any elements directly or randomly in a frequent manner, than perhaps the linked list will work out better for you.

Answer 2

An ArrayList is a variable-length array, much like a vector in C++.

As with a fixed-length array, an ArrayList gives us constant-time, random-access to any element in the array but, unlike a fixed-length array, the array can grow or shrink to cater for any number of elements. This is useful when we cannot predict the number of elements we need at compile time.

The downside of an ArrayList is that there is a runtime cost whenever we expand the array to cater for new elements when there is no free memory to expand into. When this happens, the entire array must be reallocated to new memory which means every element must be copied to that new memory. To reduce the inefficiencies of expansion, we can reserve space at the end of the array to allow some moderate growth. By default, an ArrayList will reserve twice as much memory as it needs upon each reallocation, however we can also specify the reserve if we have sufficient knowledge regarding the number of elements we are likely to need. This is not unlike using a fixed-length array to cater for the worst-case, but if the worst-case is itself a variable then a variable-length array is clearly the better option.

Another downside is that insertions and extractions are best performed at the end of the array. If we insert into the middle of an array or, worse, at the beginning of the array, every element from the insertion point to the end of the array must be physically moved forwards to make room. Similarly, if we extract an element from anywhere but the end of the array, all elements that follow it must be moved backwards in the array to remove the gap.

If we plan to perform a lot of insertions or extractions from anywhere but the end of an array, an array may not be the best choice of container. A linked-list may be a better option. However, a linked-list consumes more memory per element because of the need to store elements within nodes, where each node points to the next element. We also lose constant-time random-access because elements are not stored contiguously. In some cases, a deque (double-ended queue, pronounced 'deck') may prove a better option as it gives us the best of both worlds (a list of fixed-length arrays).

Generally speaking, an ArrayList should be considered the default container type unless you have good reason to use another container type. In many cases, the advantages of a variable-length array will outweigh its disadvantages. However you should never assume that one container type will be better than another without actually testing that assumption. What works well for one particular application may not work quite so well for another. Knowing the underlying implementation of each container can help inform your design choices, but only testing can confirm whether they are the correct choices.

Answer 3

"Better" depends on whether or not you intend to change the number of elements at runtime. Each method, array vs linked-list, has its pros and its cons.