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
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
compile time).
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
make room.
6) Deleting an element from an array is
not possible.
LINKED LIST
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
time).
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:
FEATURE
Sequential access
Random access
Resigning
Element rearranging
Overhead per elements
ARRAYS
efficient
efficient
inefficient
inefficient
none
LINKED LISTS
efficient
inefficient
efficient
efficient
1 or 2 links
Based on the above differences, we can use either Array or Linkedlist according to our requirement.