Difference between array and linked list
This is completely theoretical question, however answer to this helps enhance rationale behind selection of efficient data structure in solutions to problems. “Difference between array and linked list” are usually asked to test waters about candidates understanding of basic data structures, their internal implementation,use cases and complexity of various operations on them.
In this post I will not go with usual dumping of differences. I will follow a different approach where I have categorized differences between linked list and arrays into six categories, varying from obvious to subtle. These six categories are :
- Memory allocation
- Nature or way of memory allocation
- Space required for storing data or payload
- Complexity of insert, delete and search
- Use cases
- Caching effects
Difference between array and linked list : Memory allocation
First difference between linked list and array is the way memory is allocated to these two. For arrays, memory is allocated statically and at the time of compilation. Memory allocated in the data if array is global or stack if array is local section of program. Two drawbacks follow this : One, one must be aware the size of data it will be working on, there is no provision to add additional space once program is compiled and executable build. Second, one needs to keep the entire memory allocated from start to end of scope of program in which it is allocated, as space cannot be dynamically deleted from arrays.
To see the gravity of situation here, take an example where we are designing a system which can bring at most 1000 students records from file system or database. If we use arrays, we need to allocated an array with size 1000, even if our queries mostly result in one or two records being fetched from underlying source. We will wasting space worth 998 records 99 percent of the time to handle 1 percent cases where 100o records are being fetched.
On the other hand, linked list solve these two problems. Memory for linked list is allocated at the run time from heap as oppose to compile time for arrays. Memory can be allocated and deallocated as and when required. There is no need to upfront declare amount of memory required. In above example, we will be allocating memory for 1000 records only 1 percent time, rest all the time, only memory worth 2 records will be used.
All in all, an array can have several blocks unused which are already allocated where in linked list only required number of blocks are allocated.
Having said that, there is a possibility that arrays being allocated at run time from heap as shown below. This gives flexibility of random access (discuss below) and run time allocation of size.
int * dynamicArr = (int *)malloc(sizeof(int)*N);Difference between array and linked list
Difference between array and linked list :Nature or way of memory allocation
Second difference comes from the way in which linked list and arrays are stored on memory.
Arrays are stored on contiguous locations in memory. The entire chunk of memory is allocated upfront. Any random element of array can be accessed if base address of array is known by adding offset, because all element are adjacent to each other.
On the other hand, memory for linked list is allocated randomly. So, even if head pointer of a linked list known, we cannot directly access 5th node of linked list without going through 2,3,and 4th node of it. No random access for linked list.
Space required for storing data or payload
Coming from the second point, we need extra information to be stored with payload to figure out other nodes in linked list. This fields is called next pointer, this pointer points to the next node in the list. So, to reach 3rd node from first, we go to second node using next pointer and then from second node to third using next pointer of second node. Since a pointer needs 4 bytes (32 – bit), extra space required each node to store this meta data. This meta data is not required when data is store in arrays.
If you want to store N integers in an array, you need only 4 * N bytes of memory (size of integer being 4 bytes) where as when storing it in linked list you need 4 * N + 4 * N (extra 4 * N for pointer). Going in deep, memory needed is slightly more than 8 * N due to house keeping space for each node. More on this in other post!
Complexity of insert, delete and search
Any data structure under consideration for application is judged on its complexity on these three operations : Insert, delete and search.
For array, insert operation at the end is O(1), at the start it is O(N) (need to move N-1 elements already in array by one position), where as insert in between is again O(N), same for the delete operation. Search in array is O(N), which reduces to O(log N) if data is in sorted order. Accessing any random element in array has O(1) complexity.
Coming on to linked list, insertion at start or head of linked list is O(1) operation where as insert at end or tail is O(N) (need to scan all N-1 nodes to reach at the end). Deleting head node is O(1), where deleting any other node is O(N), because we need to scan list to reach node before deleting it. Search and random access is also O(N).
Difference between array and linked list :Use cases
There are specific use cases when one of the two provides better utility and efficient implementation. Consider this, you always want to add an element into a store and then remove them in reverse order (Typical stack order LIFO), linked lists are best suited. Why? You can dynamically allocate and delete node as an when elements are removed from store. Second, keep the most recently added element on the head of linked list. Removal of last added element becomes O(1) operation. This store when implemented using array faces challenge of contracting and expanding array as and when new element is added to stored.
Now, consider a case where you need to store 100 records which should be accessed very fast in random fashion. There is no variation in number of records. This warrants use of arrays as there is no addition or deletion of records and random access is required which is O(1) arrays while O(N) in linked list.
If there are frequent searches done on data, then it would be preferable to use arrays. If there are lot of insertions/deletions, then linked list.
As we saw in point ‘space required’ section, when payload to be store is of size considerably bigger than size of pointer, then extra space required by linked list is ignored if other operation are more efficient.
Difference between array and linked list : Caching effects
As per Spatial Locality principle, if the data in location ‘n’ is accessed, there’s a high chance that the data in location ‘n+1’ will be accessed soon. Therefore, several contiguous memory blocks are loaded onto the machine’s cache to speed up the data access. Since arrays are stored in a contiguous manner, they are best suited for this and thereby improving performance, which is not possible with linked list which are stored in random fashion in physical memory.
These are the some difference between array and linked list which I tried to explain as simply as possible. Please leave a comment or mail me if something is missing and can be added.