সিঙ্গলি লিংক্ড লিস্ট কী এবং আপনি এটি কখন ব্যবহার করবেন?

Question

Accepted Answer

একটি **সিঙ্গলি লিংক্ড লিস্ট** হল **নোড**গুলির একটি শৃঙ্খল, যেখানে প্রতিটি নোড একটি মান এবং **পরবর্তী** নোডের একটি পয়েন্টার ধারণ করে। একটি অ্যারের বিপরীতে, নোডগুলি সংলগ্ন নয় — তারা মেমরিতে যেকোনো জায়গায় থাকতে পারে, রেফারেন্স দ্বারা সংযুক্ত।

## কাঠামো

```text
head
  |
  v
[10|*]--->[20|*]--->[30|null]
 val next   val next  val next
```

## উদাহরণ

```python
class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

# Insert at head -> O(1)
def push_front(head, val):
    node = Node(val)
    node.next = head     # point new node at old head
    return node          # new head

# Search -> O(n): must walk the chain
def find(head, target):
    cur = head
    while cur:
        if cur.val == target:
            return cur
        cur = cur.next
    return None
```

## জটিলতা

| অপারেশন | সময় |
|---|---|
| শুরুতে সন্নিবেশ/মুছুন | O(1) |
| সূচক দ্বারা অ্যাক্সেস | O(n) |
| অনুসন্ধান | O(n) |

## ট্রেড-অফ

- **শক্তি:** সামনে O(1) সন্নিবেশ/মুছুন; পুনরায় বরাদ্দ ছাড়াই বৃদ্ধি; কোনো নষ্ট ক্ষমতা নেই।
- **দুর্বলতা:** কোনো এলোমেলো অ্যাক্সেস নেই; প্রতিটি নোড পয়েন্টার ওভারহেড বহন করে; দুর্বল ক্যাশ স্থানীয়তা (ছড়িয়ে ছিটিয়ে মেমরি)।

## এটি কেন গুরুত্বপূর্ণ

লিংক্ড লিস্টগুলি দুর্দান্ত হয় যখন আপনি প্রায়শই শেষে যোগ বা সরান এবং খুব কমই মাঝ দিকে সূচিত করেন — উদাহরণস্বরূপ, স্ট্যাক, কিউ এবং সংলগ্ন তালিকার মেরুদণ্ড হিসাবে।

এখানে পয়েন্টার ম্যানিপুলেশন বোঝা গাছ, গ্রাফ এবং অনেক সাক্ষাত্কার সমস্যার জন্য ভিত্তিমূলক।

অপারেশন	সময়
শুরুতে সন্নিবেশ/মুছুন	O(1)
সূচক দ্বারা অ্যাক্সেস	O(n)
অনুসন্ধান	O(n)