Difference between linked list and Arrays

What is the difference between Linked List and Arrays?

Answer:

Before talking about the differences, lets see the similarities:

How arrays are similar to linked Lists

1. Both are collection of elements.

2. Both Linked List and Arrays are homogenous collection of elements. i.e all the elements in a linked list (or an Array) has to be of the same type. All Nodes in linked list have same data type. (You may argue, that we can have an array of void pointers each of which can point to element of different data type, like below:

    char ch;
    int ivar;
    void * arr[2] = {&ch, &ivar};

but in the above case also the data type of both the elements in array is same (void *).

Next: Differences ... Differences:

Array is an indexed collection of elements. i.e arr[i] represents elements at i'th index in the array arr. Linked list's element cannot be accessed using index, rather you have to traverse to that particular element.

Hence, accessing i'th element in the array is constant-time operation (memory look-up) while accessing i'th element in a linked list requires i steps (moving to the i'th node) and is hence O(i) time operation.

Next: Storage ...

All the elements in an array are stored contiguously in memory (as a single block). Elements of linked list may be scattered in memory (that's why need a pointer to access the next element).

Next: Size  ...

You can apply sizeof operator on an array to get the size of entire array. No such thing can be applied on Linked List.

Next: Expanding (Dynamic Size) ...

Array's cannot be expanded. Even if you have an array on heap or a variable length array on stack (C99 feature), it cannot be expanded once the memory is allocated. (You may counter argue, that we have realloc, but believe me that's not what we mean by expanding at the same place). The size of Linked list can be increased by allocating more nodes and adjusting the pointers.

Next: Searching ...

You can apply both linear and binary search in an array (for binary search, the array must be sorted though). For linked list, you have to rely on linear search only (even if it is sorted).

Next: Insertion ...

Inserting an element in a Linked List is easy, but in an array it may be time consuming. For example: if we have a sorted array (of size 10) like below (last 4 positions are empty which are represented by _):

2 4 6 8 10 15 _ _ _ _

and we want to insert 7 in this sorted array, then we have to shift 3 elements by one position.

2 4 6 7 8 10 15 _ _ _

In case of linked list pointers could have been manipulated and no shifting would have been required.

Next: Deleting element ...

Similar to insertion, deletion of an element in an array is also time consuming O(n).

Next: Memory requirement ...

In Linked List extra pointer is required to store the address of head node of the array. In case of array, the name does not take physical memory like pointers.

Next: Locality of reference ...

Locality of reference is very good in arrays. Suppose if you are reading an array of size 100, then all the elements will be adjacent to each other, If that array is stored on hard disk, then the head does not need to be moved much, but in case of linked list, the physical location of elements may be scattered and hence lot of head movement may require (for externally stored list).

Next: Sorting ...

Sorting is easy in arrays, there are multiple algorithms which can be used (even the non-comparison sorting algorithms like counting sort). To sort a lined list, we don't have much optimized options.

I hope you, Enjoyed the differences and similarities..