Exploring Linked Lists: Your Beginner's Guide to Understanding Node Connections

Concept

Definition:

-> Linear data structure with dynamic memory allocation.

Time Complexity:

-> Access -> at O(n).

-> Deletion -> at O(1).

-> Searching -> at O(n).

-> Insertion -> at O(1).

Types:

Singly Linked List: Can only be iterated from beginning.

Doubly linked list: Can be iterated from both beginning and end.

eg: https://www.geeksforgeeks.org/count-triplets-sorted-doubly-linked-list-whose-sum-equal-given-value-x/

Circular linked list:

eg: https://leetcode.com/problems/design-circular-queue/

Common Operations:

1. Delete a node

     -> Delete by value is O(N).

     -> Delete by address O(1).

         https://www.geeksforgeeks.org/delete-a-node-from-linked-list-without-head-pointer/

2. Find kth node from beginning / end O(K)

https://leetcode.com/problems/remove-nth-node-from-end-of-list/

3. Find cycle in a linked list

https://leetcode.com/problems/linked-list-cycle/

4. Reverse

https://leetcode.com/problems/reverse-linked-list

5. Swap nodes

https://leetcode.com/problems/swap-nodes-in-pairs/

6. Copy linked list

https://www.geeksforgeeks.org/a-linked-list-with-next-and-arbit-pointer/

Where a linked list is useful?

• Doubly linked list is used as a queue
• Linked list with other data structures

Linked list & Map

https://www.geeksforgeeks.org/lru-cache-implementation/

https://www.geeksforgeeks.org/find-first-non-repeating-character-stream-characters/

Linked list & Priority queue

https://leetcode.com/problems/merge-k-sorted-lists/

So this is it for this article. I hope it helped you somewhere.Feel free to book 1: 1 session with me where we can discuss thing at the length.

Thank you, Have a nice day !!