Linked list as array
Difference between Array and Linked ListBoth Linked List and Array are used to store linear data of similar type, but an array consumes contiguous memory locations allocated at compile time, i.e. at the time of declaration of array, while for a linked list, memory is assigned as and when data is added to it, which means at runtime. Show Before we proceed further with the differences between Array and Linked List, if you are not familiar with Array or Linked list or both, you can check these topics first:
This is the basic and the most important difference between a linked list and an array. In the section below, we will discuss this in details along with highlighting other differences. Linked List vs. ArrayArray is a datatype which is widely implemented as a default type, in almost all the modern programming languages, and is used to store data of similar type. But there are many usecases, like the one where we don't know the quantity of data to be stored, for which advanced data structures are required, and one such data structure is linked list. Let's understand how array is different from Linked list.
Below we have a pictorial representation showing how consecutive memory locations are allocated for array, while in case of linked list random memory locations are assigned to nodes, but each node is connected to its next node using pointer. On the left, we have Array and on the right, we have Linked List. Why we need pointers in Linked List? [Deep Dive]In case of array, memory is allocated in contiguous manner, hence array elements get stored in consecutive memory locations. So when you have to access any array element, all we have to do is use the array index, for example arr[4] will directly access the 5th memory location, returning the data stored there. But in case of linked list, data elements are allocated memory at runtime, hence the memory location can be anywhere. Therefore to be able to access every node of the linked list, address of every node is stored in the previous node, hence forming a link between every node. We need this additional pointer because without it, the data stored at random memory locations will be lost. We need to store somewhere all the memory locations where elements are getting stored. Yes, this requires an additional memory space with each node, which means an additional space of O(n) for every n node linked list.
|