All You Need To Know About Linked List

Photo by Glenn Carstens-Peters on Unsplash

A linked list, conversely, would be a necklace. When you find you don’t like that blue jewel anymore, take it out of the sequence and tie the resulting two ends together. No need to loop through each pearl and displace it just so you can fix your necklace.

What is Linked List

• LinkedList are linear data structure that hold Value and pointer to the next Node.
• In Linked List element are not stored in contiguous memory locations.
• Linked list is compose of nodes which are connected with each other Using Pointers.
• Below is an example of linked list. Here A is head of linked list and it’s store the value and pointer to the next node B. Last node store pointer value to be null.

Why Linked List

• Array is also a linear data structure, But array size is fixed, Means we cannot increase the size of array in runtime. Also the allocated memory to array is fixed whether we store single element or up to the upper limit of array. To overcome this we use Linked List.
• Insertion in array is expensive because we have to shift element to make room for the element.
• Deletion in array is expensive .
• Size of Linked list is not defined allowing the linked list to increase or decrease in size as the program runs
• Fast Insertion and Deletion Time in compare to array

Cons Of Linked List

• Slower Search Time
• Array allow random access to the element, A linked list allow sequential access to the element.
• Linked list also use more memory in compare to array if we know the size of the Data which we want to store in the data structure. As linked list required additional storage for pointer
• Arrays have better cache locality that can make a pretty big difference in performance.

Time And space complexity of Linked List

+------------+--------------+----------------+
|            | Worst case   |   Average Case
+------------+--------------+----------------+
| Search     |    O(N)      |       O(N)     |
| Insert     |    O(1       |       O(1)     |
| Delete     |    O(1)      |       O(1)     |
+------------+--------------+----------------+

Application of linked list

• Image viewer
• Music Player
• Previous and next page in web browser