Data Strucrures
A linked list is linear data structure in which each node is divided into two parts, data and address of next node. Like an array these can be character or integers. Each element in a linked list is stored in the form of a node.
Node:
A node is a collection of two sub-elements or parts. A data part that stores the element and a next part that stores the link to the next node.
Example of singly linked list is
Why Linked List?
Arrays can be used to store linear data of similar types, but arrays have following limitations.
1) The size of the arrays is fixed: That is array size can be define at compile time. for example if we declare array size int arr[100], and if our requirement is more that 100 bytes then we can not insert elements more than 100, similarly if our need is only 5 bytes then unnecessarily waste memory. It means sometimes we waste memory and sometimes memory is insufficient.
2) When we want to insert element into array then we need to forward shift all elements by one and when we want to delete element the we need to backward shift all elements by one.
Linked List Vs Array:
Both Array and Linked List can be used to store linear data of similar types, but they both have some advantages and disadvantages over each other.
Key Differences Between Array and Linked List
1. An array is the data structure that contains a collection of similar type data elements whereas the Linked list is considered as non-primitive data structure contains a collection of unordered linked elements known as nodes.
2. In the array the elements belong to indexes, i.e., if you want to get into the fourth element you have to write the variable name with its index or location within the square bracket.
3. In a linked list though, you have to start from the head and work your way through until you get to the fourth element.
4. Accessing an element in an array is fast, while Linked list takes linear time, so it is quite a bit slower.
5. Operations like insertion and deletion in arrays consume a lot of time. On the other hand, the performance of these operations in Linked lists is fast.
6. Arrays are of fixed size. In contrast, Linked lists are dynamic and flexible and can expand and contract its size.
7. In an array, memory is assigned during compile time while in a Linked list it is allocated during execution or runtime.
9. Elements are stored consecutively in arrays whereas it is stored randomly in Linked lists.
10. The requirement of memory is less due to actual data being stored within the index in the array. As against, there is a need for more memory in Linked Lists due to storage of additional next and previous referencing elements.
11. In addition memory utilization is inefficient in the array. Conversely, memory utilization is efficient in the linked list.