Data Structures
पाठ · #2 / 11

लिंक्ड लिस्ट (Linked Lists)

मेमोरी में बिखरे नोड, पॉइंटरों से सिले हुए

Singly linked list · head → tail

init

खुद आज़माएँ: किसी इंडेक्स की ओर head पॉइंटर का पीछा करने के लिए walk दबाइए — छलाँगें गिनिए। फिर उसी जगह पर insert या delete कीजिए — पॉइंटरों को दोबारा जोड़ना O(1) है, पर उस जगह तक पहुँचना तो आपको फिर भी पड़ेगा।

यह क्यों मायने रखता है

लिंक्ड लिस्ट आपको पॉइंटरों में सोचना सिखाती है — कंप्यूटर साइंस की एक बुनियादी अवधारणा। व्यवहार में ये अक्सर ऐरे से धीमी होती हैं, फिर भी पेड़ों (trees), ग्राफ़ों (graphs) और मेमोरी प्रबंधन को समझने का दरवाज़ा यही खोलती हैं।

मूल विचार

एक खोज-यात्रा (scavenger hunt) की कल्पना कीजिए। हर सुराग़ आपको बताता है कि अगला सुराग़ कहाँ मिलेगा। आप सीधे सुराग़ #5 पर नहीं कूद सकते — आपको शुरुआत से ही ज़ंजीर का पीछा करना होगा।

यही एक लिंक्ड लिस्ट है। हर नोड (node) में डेटा और अगले नोड का एक पॉइंटर (pointer) होता है।

यहाँ अदला-बदली ऐरे से उलटी है:

जब आपको बार-बार शुरुआत में या किसी ज्ञात नोड के बाद डालना/हटाना हो, तो लिंक्ड लिस्ट जीतती है। जब आपको रैंडम एक्सेस चाहिए, तो ऐरे जीतता है।

मुख्य बातें

और गहराई में

सिंगली बनाम डबली बनाम सर्कुलर

| रूप | हर नोड में होता है | ख़ास बात | |---|---|---| | सिंगली-लिंक्ड | सिर्फ़ next | सबसे कम मेमोरी; सिर्फ़ आगे की ओर चल सकती है | | डबली-लिंक्ड | next + prev | नोड संदर्भ दिए जाने पर O(1) delete (prev ढूँढने की ज़रूरत नहीं); दोनों दिशाओं में चल सकती है | | सर्कुलर (सिंगली या डबली) | tail → next = head | राउंड-रॉबिन शेड्यूलिंग; iterator कभी ख़त्म नहीं होता | | XOR लिस्ट (जिज्ञासावश) | एक पॉइंटर = prev XOR next | डबली-लिंक्ड वाली ताक़त सिंगली वाली मेमोरी लागत पर। कैश prefetch तोड़ देती है — विशुद्ध शैक्षणिक। |

डबली-लिंक्ड लिस्ट की सबसे जानदार ख़ूबी है O(1) splice: जिस नोड n का पॉइंटर आपके पास पहले से है, उसे आप सिर्फ़ दो पॉइंटर लिखकर लिस्ट से हटा सकते हैं:

n.prev.next = n.next;
n.next.prev = n.prev;

कोई traversal नहीं। यही वजह है कि दुनिया की हर LRU कैश इम्प्लीमेंटेशन एक हैश टेबल के पीछे डबली-लिंक्ड लिस्ट लगाती है: हैश टेबल key से नोड का O(1) lookup देती है; और डबली-लिंक्ड लिस्ट हर बार पहुँच पर उस नोड को O(1) में सबसे आगे ले आने देती है।

सर्कुलर रूप राउंड-रॉबिन शेड्यूलरों की रीढ़ हैं — हर OS प्रोसेस शेड्यूलर जो हर चलने-योग्य थ्रेड को एक समय-टुकड़ा देता है, उसमें कहीं न कहीं एक सर्कुलर लिस्ट होती है। आख़िरी थ्रेड का "next" पॉइंटर वापस पहले की ओर इशारा करता है; आप बस चलते रहिए।

मेमोरी का अतिरिक्त बोझ — असली आँकड़े

64-बिट सिस्टम पर एक int32 रखने वाला सिंगली-लिंक्ड लिस्ट नोड:

[ 4 bytes data ][ 4 bytes padding ][ 8 bytes next pointer ] = 16 B

डेटा 4 बाइट का है, पर भंडारण 16 बाइट का — हर तत्व पर 4 गुना बोझ। उसी डेटा की डबली-लिंक्ड लिस्ट:

[ 4 bytes data ][ 4 bytes padding ][ 8 bytes next ][ 8 bytes prev ] = 24 B

6 गुना बोझ। और ये नोड मेमोरी में क्रमवार नहीं होते — हर एक अलग heap आवंटन है, इसलिए लिस्ट को घुमाना कैश-मिस का मेला बन जाता है। वही int32 अगर Vec<i32> में हों तो हर एक 4 बाइट में, लगातार, और CPU द्वारा prefetch किए हुए ठुँसे रहते हैं। दस लाख तत्वों के लूप में, एक जैसी Big-O के बावजूद ऐरे 50–100 गुना तेज़ हो सकता है।

सबक़: लिंक्ड लिस्ट तभी सही हैं जब आपको सचमुच किसी ज़िंदा नोड संदर्भ के साथ O(1) splice चाहिए (LRU कैश, OS शेड्यूलर, कर्नेल डेटा स्ट्रक्चर में intrusive लिस्ट)। बाक़ी हर चीज़ के लिए ऐरे को तरजीह दीजिए — देखिए ऐरे वाले पाठ का कैश-लोकैलिटी हिस्सा।

गणितीय ब्यौरा

Time Complexity
Access by index: O(n)
Insert at head: O(1)
Insert after node: O(1)
Delete node (given prev): O(1)
Search: O(n)
Space
हर नोड में डेटा + पॉइंटर रखे जाते हैं
Memory per node: sizeof(T) + sizeof(pointer)

क्रियान्वयन (Implementation)

लिंक्ड लिस्ट नोड

struct Node<T> {
    data: T,
    next: Option<Box<Node<T>>>,
}

// Insert at head: O(1)
fn push_front(head: &mut Option<Box<Node<T>>>, data: T) {
    let new_node = Box::new(Node {
        data,
        next: head.take(),
    });
    *head = Some(new_node);
}

कब इस्तेमाल करें

अभ्यास

तीन चिर-परिचित लिंक्ड-लिस्ट सवाल, हर एक अलग पॉइंटर पैटर्न उजागर करता है:

→ सभी अभ्यास सवाल देखें