Let me give you a quick introduction about myself.
I'm a 3 year Student studying Computer Science as a major
I'm just an average person like other's.I'm not talented enough, but I work hard & what I know is "Hard work always beats talent, when talent doesn't work Hard!!”
It's not an language specific article. Trust me, you will learn a lot. Right now it's written in Java but trust me it will never be a issue.
So, with that let's start.
Hello, my fellow programmer's today I'm going to teach you how you can become master's in LinkedList
If you want to become master, then you have to follow some rules, only after that you can become Magician or called Master's in LinkedList
Rules:
- Bring up your pen and a fresh new notebook where you have to write all of these thing's which I will teach you right now.
- If you had started learning linked list, then don't quit. Here's why, ask yourself this question when you feel about to quit,
"If you had to leave, then why you had start?" - Look back again at above 2 rule's
Remember : Practice makes a men perfect
#IntroductionWhat is linked list ?
Linked list is an linear data structure, which consists of a group of nodes in a sequence [OR] Linked list in which we store data in linear from!
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
Let's say:-
int arr[] = new int[8]
Array :- [10, 20, 15, 18, 16, 10, 20, 16]And each bit has it's memory address, where 1 bit size = 4, therefore 8 bit = 8 * 4 = 32 bit.
But linked list is dynamic, we don't have to define it's size.
In linked list we can add element as many as we want. But, in array size is fixed. So, to add new element we have to create a new array!
Advantages DisAdvantages
1. Dynamic Nature 1. More memory usage due to address pointer
2. Optimal insertion & deletion 2. Slow traversal compared to arrays
3. Stack's & queues can be easily implemented 3. No reverse traversal in singly linked list
4. No memory wastage 4. No random accessReal-life Application's :-
- Previous - n - next page in browser
- Image Viewer
- Music Player
#Type's of Linked listThere are 4 type's of linked list, but in general we use 3 type's only:-
-
Singly-linked list:linked list in which each node points to the next node and the last node points to null
-
Doubly-linked list:linked list in which each node has two pointers, p and n, such that p points to the previous node and n points to the next node; the last node's n pointer points to null
-
Circular-linked list:linked list in which each node points to the next node and the last node points back to the first node
-
Circular-Doubly-linked list:
Time Complexity:
Access: O(n)
Search: O(n)
Insert: O(1)
Remove: O(1)Let's see how to create a linked list
Code :-
Therefore,
Output:-
-------- -------- --------
| 10 | --> | 20 | --> | 30 |
-------- -------- --------Let's see how we traverse in linked list
Code:-
Output:-
-------- -------- --------
| 10 | --> | 20 | --> | 30 | --> X
-------- -------- --------
curr^
print:- 10
**************************************************
-------- -------- --------
| 10 | --> | 20 | --> | 30 | --> X
-------- -------- --------
curr^
print:- 10, 20
**************************************************
-------- -------- --------
| 10 | --> | 20 | --> | 30 | --> X
-------- -------- --------
curr^
print:- 10, 20, 30
**************************************************
-------- -------- --------
| 10 | --> | 20 | --> | 30 | --> X
-------- -------- --------
curr^
print & return answer :- 10, 20, 30Let's see how to insert an element[node] in linked list
Code:-
Key Point :- Never miss your node reference! Otherwise, you will lose your linked list;
Output:-
Given :-
-------- -------- -------- -------- --------
| 5 | --> | 10 | --> | 5 | --> | 24 | --> | 40 |
-------- -------- -------- -------- --------
Insert 30 at 3 index
head˅
-------- -------- -------- -------- --------
| 5 | --> | 10 | --> | 5 | --| |--> | 24 | --> | 40 |
-------- -------- -------- | | -------- --------
prev^ prev^ ˅ |
--------
| 30 |
--------
toAdd^Let's delete an element[node] from linked list
Code :-
Key point:- In java, if there is no reference to a node in linked list, garbage collector will take it off.
Ouput :-
Given :-
-------- -------- -------- -------- --------
| 5 | --> | 10 | --> | 15 | --> | 12 | --> | 14 | --> X
-------- -------- -------- -------- --------
delete 3rd element from linked list
-------- -------- -------- -------- --------
| 5 | --> | 10 | --> | 15 | |-X- | 12 | |----> | 14 | --> X
-------- -------- --------| -------- | --------
|-----------------| Best Question's to practiceProblem list is in order from EASY to HARD in a sequence. And all question's are available on LeetCode!
- Reverse a Linked List
- Middle of the Linked List
- Delete Node in a Linked List
- Merge Two Sorted Linked List
- Remove duplicates from sorted list
- Intersection of two linked list
- Linked List Cycle
- Palindrome Linked List
- Swapping Nodes in a Linked List
- Odd Even Linked List
- Remove nth node from Linked List
- Add Two Numbers
- Swap Nodes in Pairs
- Split Linked List in Parts
- Insertion sort on Linked List
- Merge sort on Linked List
- Copy list with random pointers
- Remove zero sum from consecutive nodes from linked list
- Merge k sorted Linked List
- Reverse nodes in k group
- Doubly Linked List
- Adding a node at the front, at the end, after a node or before a node
- Deleting a node from the front, from the end, after a node or before a node
- Circular Doubly Linked List
- Adding a node at the front, at the end, after a node or before a node
- Deleting a node from the front, from the end, after a node or before a node
- LRU Cache
- LFU Cache
I highly recommend you to solve these question's & few of them I will solve as well.
206. Reverse Linked ListProblem Statement :-
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
Explanation :-
We use 3 pointer's prev = previous, curr = current, forw = forward. Where prev will point to the previous pointer, curr will point to the current pointer & forw will point to the next pointer.
-
Prev will hold the previous value becuase, if we break the link. So, we will not lose our linked list
-
Similarly forw will point to the next pointer after curr. So, that once link is broken we will not lose our remaining linked list.
-
Once curr reaches null our prev will be on our new head. So, we will return our prev as the answer.
Solution :-
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
ListNode forw = null;
while(curr != null){
forw = curr.next;
curr.next = prev;
prev = curr;
curr = forw;
}
return prev;
}
}
876. Middle of the Linked ListProblem Statement :-
Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation:-
We will create 2 pointer's fast & slow
-
Fast pointer will move at the speed of 2X
-
Slow pointer will move at the speed of 1X
-
If fast pointer reaches null or fast.next is null we will return our slow pointer which mean's our slow pointer is pointing at mid of linked list
Solution:-
class Solution {
public ListNode middleNode(ListNode head) {
// Base Condition
if(head.next == null) return head;
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
}
141. Linked List CycleProblem Statement :-
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation:-
We will create 2 pointer's fast & slow
-
Fast pointer will move at the speed of 2X
-
Slow pointer will move at the speed of 1X
-
If fast pointer & slow pointer meet each other we will return true otherwise they there is no cycle we will return false!!
Solution:-
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if(fast == slow) return true;
}
return false;
}
}
234. Palindrome Linked ListProblem Statement :-
Input: head = [1,2,2,1]
Output: true
Explanation:-
- First we will get the mid so, that we can divide a linked list into two.
- After that, we will reverse the half of the linked list
- Then we have our slow pointer on new head & we will compare the value with old head i.e. head
- We will check these value & move both the pointer's slow & head until slow reaches null.
- If slow reaches null we will return true, otherwise false.
Solution:-
class Solution {
public ListNode reverse(ListNode head){
ListNode prev = null;
ListNode curr = head;
ListNode forw = null;
while(curr != null){
forw = curr.next;
curr.next = prev;
prev = curr;
curr = forw;
}
return prev;
}
public boolean isPalindrome(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
slow= reverse(slow);
while(slow != null && (slow.val == head.val)){
head = head.next;
slow = slow.next;
}
return slow == null;
}
}
160. Intersection of Two Linked ListsProblem Statement :-
Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Intersected at '8'
Explanation:-
So, what we doing is
-
Take 2 pointer's: pointer A walks through List A and List B (since once it hits null, it goes to List B's head).
-
Pointer B also walks through List B and List A.
-
Regardless of the length of the two lists, the sum of the lengths are the same (i.e. a+b = b+a), which means that the pointers sync up at the point of intersection.
-
If the lists never intersected, it's fine too, because they'll sync up at the end of each list, both of which are null.
Notice that if list A and list B have the same length, this solution will terminate in no more than 1 traversal; if both lists have different lengths,
this solution will terminate in no more than 2 traversals -- in the second traversal, swapping a and b synchronizes a and b before the end of the
second traversal.
By synchronizing a and b I mean both have the same remaining steps in the second traversal so that it's guaranteed for them to reach the
first intersection node, or reach null at the same time (technically speaking, in the same iteration)
-- see Case 2 (Have Intersection & Different Len) and Case 4 (Have No Intersection & Different Len).
PS: There are many great explanations of this solution for various cases, I believe to visualize it can resolve most of your doubts!Solution:-
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode a = headA;
ListNode b = headB;
while(a != b){
a = a == null ? headB : a.next;
b = b == null ? headA : b.next;
}
return b;
}
}Alright, guy's I hope you like my work! If do, then stay tuned. Because i'll post few more solution's**
Last Update :- 28th-Feb-2022