Become Expert in Linked List

date
Apr 18, 2024
slug
linked-list
status
Published
tags
Linked List
DSA
Data Structure Algorithm
Java
Interview
Prince
linked list in data structure
summary
Master linked lists with our comprehensive guide! Learn the basics, implementation, advanced operations, applications, and problem-solving techniques. Start your journey to becoming a linked list expert today!
type
Post
notion imagenotion image
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 Linked List
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 Linked List
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
 

Introduction

What 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.
notion imagenotion image
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!
notion imagenotion image
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 access
Real-life Application's :-
  1. Previous - n - next page in browser
  1. Image Viewer
  1. Music Player

Type's of Linked list


There are 4 type's of linked list, but in general we use 3 type's only:-
  1. Singly-linked list: linked list in which each node points to the next node and the last node points to null
    1. notion imagenotion image
  1. 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
    1. notion imagenotion image
  1. Circular-linked list: linked list in which each node points to the next node and the last node points back to the first node
    1. notion imagenotion image
  1. Circular-Doubly-linked list:
    1. notion imagenotion image

Time Complexity

Access: O(n) Search: O(n) Insert: O(1) Remove: O(1)

Let's see how to create a linked list

Code :-
notion imagenotion image
Therefore,
notion imagenotion image
Output:-
-------- -------- -------- | 10 | --> | 20 | --> | 30 | -------- -------- --------

Let's see how we traverse in linked list

Code:-
notion imagenotion image
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, 30

Let's see how to insert an element[node] in linked list

Code:-
notion imagenotion image
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 :-
notion imagenotion image
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 practice

Problem list is in order from EASY to HARD in a sequence. And all question's are available on LeetCode!
  1. Reverse a Linked List
  1. Middle of the Linked List
  1. Delete Node in a Linked List
  1. Merge Two Sorted Linked List
  1. Remove duplicates from sorted list
  1. Intersection of two linked list
  1. Linked List Cycle
  1. Palindrome Linked List
  1. Swapping Nodes in a Linked List
  1. Odd Even Linked List
  1. Remove nth node from Linked List
  1. Add Two Numbers
  1. Swap Nodes in Pairs
  1. Split Linked List in Parts
  1. Insertion sort on Linked List
  1. Merge sort on Linked List
  1. Copy list with random pointers
  1. Remove zero sum from consecutive nodes from linked list
  1. Merge k sorted Linked List
  1. Reverse nodes in k group
  1. Doubly Linked List
  1. Adding a node at the front, at the end, after a node or before a node
  1. Deleting a node from the front, from the end, after a node or before a node
  1. Circular Doubly Linked List
  1. Adding a node at the front, at the end, after a node or before a node
  1. Deleting a node from the front, from the end, after a node or before a node
  1. LRU Cache
  1. LFU Cache

I highly recommend you to solve these question's & few of them I will solve as well.

206. Reverse Linked List
Problem 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.
notion imagenotion image
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 List
Problem 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
notion imagenotion image
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 Cycle
Problem 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!!
notion imagenotion image
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 List
Problem 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.
notion imagenotion image
notion imagenotion image
notion imagenotion image
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 Lists
Problem 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.
notion imagenotion image
notion imagenotion image
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

 
இந்த உரையைப் பற்றிய எந்த கேள்விகள் உள்ளன, என்னுடைய தொடர்புக்கு தொடரவும்.