Linked List

1. Overview

A linked list is a linear data structure where each element is a separate object. Also, each element that is also called as a node of the Left comprises two items that are data and the reference to the next node. The most important feature of the lean left is that it is of variable size.

2. Description

2.1 Difference between the linked list and array

2.1.1 Separated object

First and the most important difference between a linked list and an array is that each of the elements would here a separate object in case of a linked list. But in the case of an array, these elements are cells that are not a separate object. What a separate object means is that if the model we don't need a node within a linked list, we can delete it and still the linked list will exist. However in case of an edit to model, if you don't need this cell we can not delete this cell, of course, we can delete the value but the cell itself can never be destroyed hence the cell of an array is never a separate object.

2.1.2 Variable size

In the case of a linked list, the number of nodes is not predefined. We can all this increase or decrease the number of nodes at run time. If you don't need node 5 We can delete it or if you want one more in order node 7, We can always increase it or add it. But in the case of an array, we can not add more cells over end.

2.1.3 Random access

The random array what that means is if you want to access cell number 3, we can access this directly in an array.

# In case of array
array[3]

In the case of a linked list, we can not do that. If you want to access an order number 3, we cannot see the linked list. Normally we always have to start from node 1 and keep traversing then we find node 3. And that is one of the biggest limitations of a lined list.

2.2 Components of the linked list

2.2.1 Node

It contains Data and Reference to the next node. In the case of Node-3, it stores data 30 and reference of the next node which address is 333.

# Node class 
class Node: 
  
    # Function to initialize the node object 
    def __init__(self, data): 
        self.data = data  # Assign data 
        self.next = None  # Initialize next as null 
  
# Linked List class 
class LinkedList: 
    
    # Function to initialize the Linked List object 
    def __init__(self):  
        self.head = None

2.2.2 Head

Reference to the first node in the list. It can only have an address or data and reference like others.

2.2.3 Tail

Reference to the last node in the list. In the case of Node-6, the physical address of it is 555.

2.3 Types of linked list

2.3.1 Single linked list

In a singly linked list, each node in the list stores the data of the node and a reference to the next node in the list. It does not store any reference to the previous node. This is the most basic form of the linked list which gives the flexibility to add/remove nodes at runtime.

2.3.2 Circular single linked list

In the case of a circular single linked list, the only change that occurs is that the end of the given list is linked back to the end. This is used when we want to loop through the list indefinitely until the list exists. For instance, in a multiplayer board game, we are tracking player's turn in linked list.

2.3.3 Double linked list

In a double linked list, each node contains two references, that reference to the previous and next node. This is used when we want to move in both directions depending on requirement. For instance, a music player which has next and prev buttons.

2.3.4 Circular double linked list

In the case of a circular doubly linked list, the only change that occurs is that the end of a given list is linked back to the front of the list and vice versa. This is used when we want to loop through the list indefinitely until the list exists. We also want to move both forward and backward. For instance, the "Alt + Tab" button in windows.

2.4 How is linked list stored in Memory

2.4.1 In the case of an array

2.4.2 In the case of linked list

2.5 Operations

2.5.1 Insertion

Add a node at the front

Add a node at the middle

Add a node at the end

2.5.2 Traversal and Search node

2) Initialize a node pointer, current = head.
3) Do following while current is not NULL
    a) current->key is equal to the key being searched return true.
    b) current = current->next
4) Return false 

2.5.3 Deletion

To delete a node from linked list, we need to do following steps.
1) Find previous node of the node to be deleted.
2) Change the next of previous node.
3) Free memory for the node to be deleted.

2.5.4 Time and Space Complexity

Algorithm	Linked list	Array	Dynamic Array
Space	O(n)	0	O(n)
Indexing	O(n)	O(1)	O(1)
Insert/Delete at Beginning	O(1)	N/A	O(n)
Insert/Delete at the end	O(1)	N/A	O(1)
Insert/Delete in middle	search time + O(1)	N/A	O(n)

3. Reference

https://www.geeksforgeeks.org/data-structures/linked-list/

https://www.geeksforgeeks.org/linked-list-set-2-inserting-a-node/

https://www.geeksforgeeks.org/delete-a-linked-list-node-at-a-given-position/

https://www.geeksforgeeks.org/search-an-element-in-a-linked-list-iterative-and-recursive/

https://www.geeksforgeeks.org/linked-list-set-3-deleting-node/

https://www.cs.cmu.edu/~adamchik/15-121/lectures/Linked%20Lists/linked%20lists.html

https://www.interviewbit.com/courses/programming/topics/linked-lists/

https://www.geeksforgeeks.org/given-a-linked-list-which-is-sorted-how-will-you-insert-in-sorted-way/

https://www.geeksforgeeks.org/delete-a-given-node-in-linked-list-under-given-constraints/

https://www.geeksforgeeks.org/compare-two-strings-represented-as-linked-lists/