Linked lists and arrays are similar since they both store collections of data. Array is the
most common data structure used to store collections of elements. Arrays are
convenient to declare and provide the easy syntax to access any element by its index
number.Once the array is set up, access to any element is convenient and fast.
The disadvantages of array:
- The size of the array is fixed. Most often this size is specified at compile
time. This makes the programmers to allocate arrays, which seems “large
enough” than required.
- Inserting new elements at the front is potentially expensive because existing
elements need to be shifted over to make room.
- Deleting an element from an array is not possible.
Linked lists have their own strengths and weaknesses, but they happen to be strong
where arrays are weak. Generally array’s allocates the memory for all its elements in
one block whereas linked lists use an entirely different strategy. Linked lists allocate
memory for each element separately and only when necessary.
Difference between Linkedlist and Array
1) Size of an array is fixed
2) Memory is allocated from stack
3) It is necessary to specify the number of
elements during declaration (i.e., during
4) It occupies less memory than a linked
list for the same number of elements.
5) Inserting new elements at the front is
potentially expensive because existing
elements need to be shifted over to
6) Deleting an element from an array is
1) Size of a list is not fixed
2) Memory is allocated from heap
3) It is not necessary to specify the
number of elements during declaration
(i.e., memory is allocated during run
4) It occupies more memory.
5) Inserting a new element at any position
can be carried out easily.
6) Deleting an element is possible.
Trade offs between linked lists and arrays:
Overhead per elements
1 or 2 links
Based on the above differences, we can use either Array or Linkedlist according to our requirement.