# 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

**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.

*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 access`

**Real-life Application's :-***Previous - n - next page in browser*

*Image Viewer*

*Music Player*

#### Type's of Linked list

**There are 4 type's of linked list, but in general we use 3 type's only:-**

linked list in which each node points to the next node and the last node points to null**Singly-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**Doubly-linked list:**

linked list in which each node points to the next node and the last node points back to the first node**Circular-linked list:**

**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**

**Let's see how to create a linked list**

**Code :-**

**Therefore,**

**Output:-**

`-------- -------- -------- | 10 | --> | 20 | --> | 30 | -------- -------- --------`

**Let's see how we traverse in linked list**

**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, 30`

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

**Let'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**

**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 practice

Problem 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 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.*

`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

`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!!

`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.

`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.

*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*