Linked list, stack ও queue: interview-এর প্যাটার্ন

Linked list, stack ও queue মৌলিক structure, তবু interviewer-রা এগুলো পছন্দ করে কারণ এগুলো pointer ও ক্রম নিয়ে সতর্ক চিন্তা পরীক্ষা করে।

Linked list

Linked list হলো node-এর শিকল। প্রতিটি node একটি মান ও পরের node-এর pointer রাখে (doubly linked list আগেরটির দিকেও নির্দেশ করে)। কোনো index নেই: ৫ম node-এ যেতে head থেকে হাঁটতে হয়।

ক্রিয়া	খরচ
অবস্থান দিয়ে access	O(n)
খোঁজা	O(n)
Head-এ যোগ বা মোছা	O(1)
হাতে থাকা node-এর পরে যোগ বা মোছা	O(1)

Array-র তুলনায়, node হাতে থাকলে linked list মাঝখানে যোগ ও মোছায় সস্তা, কিন্তু সেখানে পৌঁছানো ধীর এবং cache locality দুর্বল। বাস্তবে array সাধারণত দ্রুত, তাই linked list মূলত interview ও নির্দিষ্ট structure-এ (LRU cache, queue) গুরুত্বপূর্ণ।

class Node { constructor(val, next = null) { this.val = val; this.next = next; } }

প্যাটার্ন ১: list উল্টানো

List ধরে হাঁটুন এবং আগের node মনে রেখে প্রতিটি pointer উল্টান।

function reverse(head) {
  let prev = null, cur = head;
  while (cur) {
    const next = cur.next;   // বাকিটা মনে রাখুন
    cur.next = prev;         // উল্টান
    prev = cur;
    cur = next;
  }
  return prev;               // নতুন head
}
// সময় O(n), space O(1)

প্যাটার্ন ২: fast ও slow pointer

একটি pointer এক ধাপ, আরেকটি দুই ধাপ করে চালান।

• মাঝখান খোঁজা: fast pointer শেষে পৌঁছালে slow মাঝখানে থাকে।
• Cycle শনাক্ত: cycle থাকলে fast pointer শেষে slow-এর সাথে মিলে (Floyd-এর algorithm)।

প্যাটার্ন ৩: dummy head

Head-এর আগে একটি dummy node head নিজে বদলাতে পারে এমন ক্ষেত্রে (যেমন দুটি sorted list মিলানো বা node মোছা) বিশেষ ক্ষেত্র সরায়।

function mergeTwoLists(a, b) {
  const dummy = new Node(0);
  let tail = dummy;
  while (a && b) {
    if (a.val <= b.val) { tail.next = a; a = a.next; }
    else { tail.next = b; b = b.next; }
    tail = tail.next;
  }
  tail.next = a || b;
  return dummy.next;
}

Linked list-এর সাধারণ ভুল

• সংরক্ষণের আগে next overwrite করে list-এর বাকি অংশ হারানো।
• ফাঁকা list, একক node বা head মোছা না সামলানো।
• Cycle থাকলে অসীম loop।
• শেষ থেকে N-তম node মোছায় off-by-one (N দূরত্বের দুটি pointer ব্যবহার করুন)।

Stack

Stack হলো last in, first out (LIFO): থালার স্তূপের মতো। ক্রিয়া: push, pop, peek, প্রতিটি O(1)। অনেক ভাষায় array stack হিসেবে কাজ করে।

ব্যবহার: undo, function call stack, parsing, backtracking এবং বন্ধনী মেলানো।

প্যাটার্ন: বন্ধনী মেলানো

function isValid(s) {
  const pairs = { ")": "(", "]": "[", "}": "{" };
  const stack = [];
  for (const ch of s) {
    if (ch in pairs) {
      if (stack.pop() !== pairs[ch]) return false;
    } else {
      stack.push(ch);
    }
  }
  return stack.length === 0;
}
// সময় O(n), space O(n)

প্যাটার্ন: monotonic stack

Stack বর্ধমান বা ক্রমহ্রাসমান ক্রমে রাখুন, যে item আর উত্তর হতে পারে না তা বের করে দিন। এটি "পরবর্তী বড় element" ধাঁচের সমস্যা O(n)-এ মেটায়।

function nextGreater(nums) {
  const result = new Array(nums.length).fill(-1);
  const stack = [];                    // যাদের উত্তর এখনো নেই সেই index
  for (let i = 0; i < nums.length; i++) {
    while (stack.length && nums[stack.at(-1)] < nums[i]) {
      result[stack.pop()] = nums[i];
    }
    stack.push(i);
  }
  return result;
}

প্রতিটি index একবার push ও একবার pop হয়, তাই O(n)। সংশ্লিষ্ট সমস্যা: দৈনিক তাপমাত্রা, histogram-এ বৃহত্তম আয়তক্ষেত্র, stock span।

Queue

Queue হলো first in, first out (FIFO), দোকানের লাইনের মতো। ক্রিয়া: পেছনে enqueue ও সামনে থেকে dequeue, সঠিক বাস্তবায়নে দুটিই O(1)।

সতর্কতা: JavaScript-এ array.shift() O(n) হতে পারে। আসল queue-র জন্য index pointer, linked list বা deque library ব্যবহার করুন।

ব্যবহার: কাজের schedule, buffering এবং tree ও graph-এ breadth-first search (BFS), যা স্তর ধরে অনুসন্ধান করে।

• Deque (double-ended queue): দুই প্রান্তেই যোগ ও সরানো। Monotonic deque sliding window-এর সর্বোচ্চ O(n)-এ মেটায়।
• Priority queue (heap): সবচেয়ে ছোট বা বড়টি আগে সরায়, O(log n)-এ।

ক্লাসিক ধাঁধা

• দুটি stack দিয়ে queue, এবং দুটি queue দিয়ে stack বানান।
• Min stack: O(1)-এ ন্যূনতম ফেরত দেওয়া stack (প্রতিটি element-এর সাথে চলমান ন্যূনতম রাখুন)।
• Stack দিয়ে postfix expression হিসাব।

কোনটি বাছবেন

প্রয়োজন	ব্যবহার
সাম্প্রতিকটি আগে, undo, মেলানো, DFS	Stack
পুরোনোটি আগে, স্তর ধরে, schedule	Queue
দুই প্রান্তে দ্রুত যোগ ও সরানো	Deque
সবসময় পরবর্তী ছোট বা বড়	Heap / priority queue
node হাতে নিয়ে মাঝখানে দ্রুত যোগ	Linked list

অনুশীলনের সমস্যা

Reverse Linked List, Merge Two Sorted Lists, Linked List Cycle, Remove Nth Node From End, Valid Parentheses, Min Stack, Daily Temperatures, Implement Queue using Stacks, Sliding Window Maximum।

মূল কথা: linked list-এ pointer এঁকে নিন, dummy head ও fast/slow pointer ব্যবহার করুন। Nested বা "সাম্প্রতিক" সমস্যায় stack এবং স্তর ধরে প্রক্রিয়ায় queue ব্যবহার করুন।

---

Interview প্রস্তুতি ও DSA সিরিজ, পর্ব ২ (data structure ও আচরণ): 1 নম্বর (মোট 5)।