What is Linked List

A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations or Linked list is an linear data structure, which consists of a group of nodes in a sequence .

But, Array also stores data in linear form. Then what's the difference! In array we have to first define the size of the Array. linked list is dynamic, we don't have to define it's size

There are commonly three types of linked list;

-Singly linked list: linked list in which each node points to the next node and the last node points to null

In singly linked list there is only a single link. In this list, only forward traversal is possible; we cannot traverse in the backward direction as it has only one link in the list.

---

-Doubly linked list: The doubly linked list contains two pointers. Here each node contains two node ,one node points to previous node and second node points to next node

Here in this example, Consider node A so previous node of A node points to null and next node points to node B

---

-Circular linked list: A circular linked list is that in which the last node contains the pointer to the first node of the list. Simply it's singly linked where last node points to first node.

Here in this example next node of last node 10 points to first node. keep in mind that we can not traverse backward in the Circular linked list.

---

There is another more complex type of linked-list which is not used commonly

-Doubly Circular linked list:The doubly circular linked list has the features of both the circular linked list and doubly linked list.

---

Let's see how we can traverse in linked list

Here we have assigned curr node = head(first node) and then in while loop we will going to next node until we don't reach null.

Cycles Detection

In some of the question of linked list we require to detect cycle so how we can detect cycle in linked list?
Here, we can use fast and slow pointer approach.

  while(fast!=null && fast.next!=null){
             fast=fast.next.next;
             slow=slow.next;
           if(fast==slow) return true;

            }

While traversing in linked list if fast pointer == slow pointer that means cycle exist in linked list. Because fast pointer will never point to null since cycle is present in Linked list.

Here is the some LeetCode Questions that you can practice!

1. Reverse a Linked List
   
2. Middle of linked list
   
3. Remove duplicates from sorted list
   
4. Merge two sorted list
   
5. Linked List cycle
   
6. Sort list
   
7. Reverse Linked list II
   
8. Palindrome Linked list
   
9. Reorder List
   
10. Reverse nodes in k group
    
11. Rotate list
    

Solutions of these questions : https://github.com/Sujansinh-thakor/Linked-List-questions-/tree/main

That's all folks, Hope this help you to understand Linked list better.
👋 Follow me on Twitter

---