Like arrays, the Linked List is a linear data structure. Unlike arrays, linked list elements are not stored at a contiguous location; the elements are linked using pointers.
Why use a Linked List over an Array?
Arrays can be used to store linear data of similar types, but arrays have the following limitations:
1) Arrays have a fixed size – so we must know the upper limit (ceiling) on the number of elements in advance. Additionally, in most implementations, the memory allocation is equal to the upper limit regardless of usage.
2) Inserting new elements into an array is expensive because space has to be created for the new elements and to create space, existing elements have to be shifted.
For example, in a system, if we maintain a sorted list of IDs in an array nums[].
nums[] = [100, 101, 105, 200, 206].
And if we want to insert a new ID 104, then to maintain the sorted order, we have to move all the elements after 100 (excluding 100).
Deletion is also expensive with arrays. For example, to delete 101 in nums[], everything after 101 has to be shifted.
Advantages over arrays:
- Dynamic size
- Ease of insertion/deletion
Disadvantages:
- Random access is disallowed. We must access elements sequentially starting from the first node and then traverse the list until we reach the element we are seeking. So an efficient binary search is not an option with linked lists in their default implementation.
- The more segments a list is broken into the more overhead there is for locating the next linked element.
- Extra memory space for a pointer is required with each element of the list.
- Not cache friendly. Since array elements are contiguous locations, there is locality of reference which is not the case for linked lists.
Representation
A linked list is represented by a pointer to the first node of the linked list. The first node is called the head. If the linked list is empty, then the value of the head is NULL.
Each node in a list consists of at least two parts:
1) Data
2) Pointer (Or Reference) to the next node
