DSA Linked List – This article is about DSA Linked List that describes an Introduction to Linked List with its advantages & disadvantages much more in DSA.
Before moving ahead, let’s take a look at Data Structure Algorithm: Introduction to Queue.
Table of Contents
Linked List
Linked List is the collection of linear data structure. It contains nodes that divide into two parts, i.e., data and pointer. Each node store data of the current node, and the pointer stores the reference (Address) to the next node.
Unlike arrays with a fixed size and contiguous memory allocation, linked lists are dynamic and can grow or shrink as needed. The data element of the first node is called HEAD.
Why is Array necessary?
The linear data structure can be performed over a Linked List as well. Let’s discuss a few advantages of the Array, the solution over the Linked List.
Advantages of Array
- Access Element: Since array elements are stored in contiguous memory locations, accessing any element with its index number is easy. This makes arrays efficient for scenarios that require frequent random access, such as searching or retrieving elements by index.
- Less Memory: Unlike Linked List, an array does not need to acquire the extra memory. Arrays have a smaller memory overhead compared to linked lists. Linked lists require extra memory to store the references or links between nodes, which can increase overall memory usage. Arrays only require memory for the elements themselves, making them more memory-efficient regarding storage requirements.
- Cache Efficiency: Arrays have better cache locality compared to linked lists. Since an array stores the elements in nearby locations, fetching multiple elements at once makes it easy. In contrast, linked lists have nodes scattered throughout memory, which can result in more cache misses and slower access times.
Why is Linked List necessary?
Linked List can also be performed in an Array, but there are a few limitations of the Array which create problems for the Linked List.
Disadvantages of Array
- Fixed Size: An array contains a fixed size, which means it cannot exceed the size limit. If a new data element is inserted and the size is full, then a new array is to be taken.
- Difficult in insertion: It is difficult to insert a new data element in the Array since the Array cannot make space between the data elements. E.g., If the data element is to be inserted into the 2nd position, then all data elements from the current 2nd position have to move to the right position to create the space.
- Difficult in Deletion: If the data element at index 3 is to be deleted, then the rest must be moved to the right position.
Since an array is not fully functional to store the data elements, therefore, Linked List is necessary to store the data elements over an array.
Advantages of Linked Lists
- Dynamic size: Linked List is Dynamic, meaning it grows as a new data element is inserted.
- Efficient Insertion and Deletion: Since the Linked List is dynamic in size; therefore deleting or inserting in Linked List is easy.
- Memory Flexibility: Linked lists can be created with nodes scattered throughout memory, unlike arrays that require continuous memory allocation. This flexibility allows efficient memory management and utilization.
Disadvantages of Linked Lists
- Random Access: Linked List is not much efficient in accessing the element as much as an array. If an element has to access in Linked List, we have to move sequentially throughout the nodes, which takes more time than the Array.
- Extra Memory: Linked List requires more memory as it stores each node’s reference (Address). This can put pressure on overall memory usage compared to an array.
Fundamental Operations
The basic operations supported by a list are –
- Insertion: At the beginning of the List, add an element.
- Deletion: Deletes an item at the beginning of the List.
- Display: Shows the List in full.
- Search: Use the given key to search for an element.
- Delete: Using the given key, delete an element.
