What is Linked List Data Structure ? | Arrays vs Linked List | Operations | Types | Applications

In this data structures tutorial post we will understand in detail the working of Linked List Data Structure. Linked list data structure is a type of linear data structure which overcomes some limitations of conventional arrays.

Definition –

A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers(entity that point to the next element)
In simple words, a linked list consists of nodes where each node contains a data field and a reference(link) to the next node in the list.

Arrays vs Linked List (All info from – GeeksforGeeks) –

• 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 un-ordered linked elements known as nodes.
• 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. In a linked list though, you have to start from the head and work your way through until you get to the fourth element.
• Accessing an element in an array is fast, while Linked list takes linear time, so it is quite a bit slower.
• 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.
• Arrays are of fixed size. In contrast, Linked lists are dynamic and flexible and can expand and contract its size.
• In an array, memory is assigned during compile time while in a Linked list it is allocated during execution or runtime.
• Elements are stored consecutively in arrays whereas it is stored randomly in Linked lists.
• 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.
• In addition memory utilization is inefficient in the array. Conversely, memory utilization is efficient in the linked list.

Some Standard Linked List Operations –

• Traverse – Iterate through the nodes in the linked list starting from the head node.
• Append – Attach a new node (to the end) of a list
• Prepend – Attach a new node (to the beginning) of the list
• Insert – attach a new node to a specific position on the list
• Delete – Remove/Delink a node from the list
• Count – Returns the no of nodes in linked list

Types of Linked List –

We will discuss each of this type in detail in separate articles.

1. Singly Linked List
2. Doubly Linked List
3. Circular Linked List

Some Applications of Linked List DS –

• Linked Lists can be used to implement Stacks , Queues.
• Linked Lists can also be used to implement Graphs. (Adjacency list representation of Graph).
• Implementing Hash Tables :- Each Bucket of the hash table can itself be a linked list. (Open chain hashing).
• Undo functionality in Photoshop or Word . Linked list of states.

YouTube video tutorials –