Linked List

Linked List is one of the data structures which is linear in nature in which each node has some data and the address of the next node in the list. While arrays are data structures which store elements in contiguous memory regions, linked lists do not. On the other hand, each element is connected to the next one forming a chain or a list as it were.

Key Concepts of Linked Lists

1. Node: The basic component of a linked list is called node. A node typically contains two components:

• Data: The data or content which the node is supposed to contain or the data it can provide.
• Pointer: A reference to something that comes after the given sequence in question.

Some of the variations of linked lists are that a node may also contain a pointer to the past node.

2. Head: In the list, the head is the first node in a list. This acts as the starting level from which the user can be able to access the whole list. If the list is empty, the head may be set to null in many cases or it may be set to None.

3. Tail: The tail is the last element of a linked list. In singly linked list, the tail node has its next pointer pointing to NULL or None, and this mark the end of the list. In a doubly linked list the tail may contain the reference to the previous node as well as the next node.

4. Pointer/Link: In linked list, every node contain a link or pointer to the next node. This pointer is vital since it helps to establish the order of the position of elements in the list and facilitates movement from one node to the next.

Types of Linked Lists

1. Singly Linked List: In singly linked list each node have a link to the next node in the list. traverse in singly linked list is one directional that is you can only move forward towards the next node.

2. Doubly Linked List: A doubly linked list has each of the link nodes with two links, one link points to the next node while the other points the previous node. This makes the traversal bidirectional that is one can traverse in the forward as well as in the backward direction.

3. Circular Linked List: In circular linked list the last node links to the first node that is why it is called circular linked list. Circular linked list may either be singly linked list or doubly linked list.

4. Doubly Circular Linked List: A doubly circular linked list is a list which has the characteristics of both doubly linked list and circular linked list. The last node points back to the first node and the first node has pointer to previous pointing to the last node.

Common Operations on Linked Lists

1. Traversal: Traversal of linked list means accessing each node of the list sequentially from the head node till the last node in case of singly linked list or starting from head node and going till the last node and then reaching to head again in case of circular linked list. Traversal is important in an attempt to access or display the elements contained in the list.

2. Insertion: In linked list insertion can be made at the start, end or at any position in between the list.

• At the beginning: The next pointer of the new node is then pointed to the current head and then the head is changed to new node.
• At the end: The last node points to the new node and the new node points to null as the last node’s next node.
• ‍At a specific position: A new node is added between two nodes where the node’s next pointer points to the next node in the sequence and previous node’s pointer re-directed to the new node.

3. Deletion: Deletion on the other hand is the process of eliminating a node from the list. The node can be deleted from the first, last or any specific location depending on the user’s desire.

• From the beginning: The head is then updated to the next node thus erasing the first node.
• ‍From the end: The second last node’s next pointer is then set to ‘null’ thus eliminating the last node.
• ‍From a specific position: The next pointer of the previous node is adjusted to skip over the node to be removed and instead point to the node which follows it.

4. Searching: In searching we are looking for an element which has a particular key in the list and to do this we need to start at the root node and traverse the tree till the desired key is found. If the value is there then the corresponding node is returned otherwise the search continues on till the end of the list.

5. Reversing: Reversing a linked list is simply a process of making the latter node to become the first node and the first node becoming the last node.

Advantages of Linked Lists

1. Dynamic Size: As opposed to arrays, linked lists are not homogeneous in size. It can be extended and reduced anytime depending on the number of items that are to be incorporated or omitted.

2. Efficient Insertions/Deletions: The insertion and deletion in linked list takes less time as compared to the array especially when the operations are to be performed at the starting or in between the list. These operations does not involve moving elements as it is the case with arrays.

3. Memory Efficiency: Linked list consumes less memory as compared to arrays because of the fact that it does not occupy continuous memory slots. Memory management is also optimized to the extent that nodes are allocated as they are needed and this may be especially advantageous where a data structure is likely to undergo frequent changes in size.

4. Flexibility: Linked lists are dynamic data structures which can easily model other data structures like stacks, queues and even other complicated structures like adjacency list for graphs.

Disadvantages of Linked Lists

1. No Random Access: Unlike arrays it is not possible to access the elements of a linked list directly using their index. To gain access to an element, one has to start from the head and then search through the list and this can be time consuming especially where one needs to access elements at particular positions frequently.

2. Extra Memory Usage: Every node in a linked list also contains pointer(s) which consumes more memory for every node than an array, thereby increasing memory overheads.

3. Complexity: The manipulation of an array is easier to implement than that of a linked list especially for the new learners. It has to handle pointers and make sure that they point towards the linked lists and also when to link and unlink the nodes increase the complexity.

4. Cache Unfriendliness: The use of linked lists does not have the advantage of the locality of reference which arrays have. By linked list data elements are not stored in the consecutive memory locations and therefore, access to elements is slower because of more cache misses.

Conclusion

Therefore, a Linked List is a linear data structure made of nodes which is distinguished by the connection of the nodes in the list. Some of the benefits of using linked lists include; dynamic sizing, efficient insertions and deletions and flexibility. They can be of different types such as singly linked list, doubly linked list, circular linked list and many more. Nevertheless, there are some disadvantages of using linked list such as, they do not support direct access, more memory is required for pointers and also, it is comparatively difficult to implement. Nevertheless, linked list is one of the most essential data structure which is employed in many applications especially where there is a need for dynamic memory allocation, efficient insertion or deletion.