Linked List

Node + next

हर node एक मान और अगले node का संदर्भ रखता है:

[10|·]-> [20|·]-> [30|null]

तत्व मेमोरी में बिखरे होते हैं। कोई इंडेक्स गणित नहीं, इसलिए स्थिति k तक पहुँचना O(k) है, पर node जोड़ना/हटाना O(1)।

खज़ाने की खोज

हर सुराग सिर्फ़ बताता है कि अगला सुराग कहाँ है। आप सीधे सुराग 5 पर नहीं जा सकते — श्रृंखला का अनुसरण करते हैं। पर सुराग जोड़ने में सिर्फ़ दो नोट बदलने होते हैं।

head पर insert, reverse

Reverse करना classic है: एक बार चलें, हर next पॉइंटर को पीछे मोड़ें।

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

def reverse(head):
    prev = None
    while head:
        nxt = head.next   # save
        head.next = prev   # flip
        prev = head        # advance
        head = nxt
    return prev            # new head

प्रकार और पैटर्न

Singly, doubly (prev वाला), और circular (tail head की ओर)। Fast/slow पॉइंटर cycle पहचानते हैं और मध्य खोजते हैं; dummy head node हटाते समय किनारे के मामले हटाता है।