لیستی بەستراو (Linked List)

پێناسە و چەمکی سەرەکی

لیستی بەستراو (Linked List) پێکهاتەیەکی داتایە کە کۆمەڵێک نۆد (Node) لەخۆدەگرێت کە بە شێوەیەکی زنجیرەیی پەیوەندییان پێکەوە هەیە. هەر نۆدێک دوو بەشی سەرەکی هەیە:

• بەشی داتا: بەهاکە هەڵدەگرێت
• بەشی ئاماژە (Pointer): ئاماژە بۆ نۆدی داهاتوو دەکات

بەپێچەوانەی ئەڕەی (Array)، نۆدەکانی لیستی بەستراو پێویست ناکات بەشێوەیەکی بەردەوام لە بیرگەدا هەڵبگیرێن، بەڵکو دەکرێت لە هەر شوێنێکی بیرگەدا هەڵبگیرێن و لە ڕێگەی ئاماژەکانەوە پەیوەندییان پێکەوە هەبێت.

جۆرەکانی لیستی بەستراو

1. لیستی بەستراوی یەک لایەن (Singly Linked List)

• هەر نۆدێک تەنها یەک ئاماژەی هەیە کە بەرەو نۆدی داهاتوو دەڕوات
• نۆدی کۆتایی ئاماژە بۆ NULL دەکات
• تەنها بەرەو پێشەوە دەتوانرێت بەستنەوە بکرێت

2. لیستی بەستراوی دوو لایەن (Doubly Linked List)

• هەر نۆدێک دوو ئاماژەی هەیە:
  • یەکێک بۆ نۆدی داهاتوو (next)
  • یەکێک بۆ نۆدی پێشوو (previous)
• دەکرێت بەرەو پێشەوە و بەرەو دواوە پەیمان بکرێت

٣. لیستی بەستراوی بازنەیی (Circular Linked List)

• نۆدی کۆتایی ئاماژە بۆ نۆدی سەرەتا دەکات لە جیاتی NULL
• دەکرێت یەک لایەن یان دوو لایەن بێت

کردارە سەرەکییەکان لەسەر linked list

١. زیادکردنی نۆد

• زیادکردن لە سەرەتاوە: O(1) - خێراترین کردارە

  1. نۆدی نوێ دروست بکە
  2. ئاماژەی نۆدەکە بۆ سەری لیست بگۆڕە
  3. سەری لیست بگۆڕە بۆ نۆدی نوێ

• زیادکردن لە کۆتاییەوە: O(n) لە لیستی یەک لایەن، O(1) ئەگەر ئاماژەی کۆتایی هەبێت

  1. نۆدی نوێ دروست بکە
  2. بەدوای دوا نۆدی لیستدا بگەڕێ
  3. ئاماژەی دوا نۆد بگۆڕە بۆ نۆدی نوێ

• زیادکردن لە شوێنێکی دیاریکراو: O(n)

  1. بەدوای شوێنی دیاریکراودا بگەڕێ
  2. ئاماژەکان بەشێوەیەک بگۆڕە کە نۆدی نوێ لە نێوان نۆدی پێشوو و داهاتوو بێت

٢. سڕینەوەی نۆد

• سڕینەوە لە سەرەتاوە: O(1)

  1. ئاماژەی سەری لیست بگۆڕە بۆ نۆدی دووەم
  2. بیرگەی نۆدی سەرەتا ئازاد بکە

• سڕینەوە لە کۆتاییەوە: O(n) لە لیستی یەک لایەن

  1. بەدوای نۆدی پێش-کۆتایی بگەڕێ
  2. ئاماژەی نۆدی پێش-کۆتایی بگۆڕە بۆ NULL
  3. بیرگەی نۆدی کۆتایی ئازاد بکە

• سڕینەوە لە شوێنێکی دیاریکراو: O(n)

  1. بەدوای نۆدەکە و نۆدی پێشووی بگەڕێ
  2. ئاماژەی نۆدی پێشوو بگۆڕە بۆ نۆدی داهاتووی ئەو نۆدەی دەسڕدرێتەوە
  3. بیرگەی نۆدەکە ئازاد بکە

٣. گەڕان

• تێچووی کاتی: O(n) - پێویستە بە شێوەی زنجیرەیی بە هەموو نۆدەکاندا بڕۆیت
• پرۆسە:
  1. دەست پێبکە لە سەری لیست
  2. بە ئاماژەی داهاتوودا بڕۆ هەتا ئەو بەهایەی بەدوایدا دەگەڕێیت دەدۆزیتەوە یان دەگەیتە کۆتایی

کۆدی لیستی بەستراو بە پایسۆن

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

class LinkedList:
    def __init__(self):
        self.head = None
    
    # زیادکردن لە کۆتاییەوە
    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node
    
    # زیادکردن لە سەرەتاوە
    def prepend(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
    
    # نیشاندانی لیست
    def display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("NULL")
    
    # گەڕان بەدوای بەهایەک
    def search(self, key):
        current = self.head
        while current:
            if current.data == key:
                return True
            current = current.next
        return False
    
    # سڕینەوەی نۆدێک بەپێی بەها
    def delete(self, key):
        current = self.head
        
        # ئەگەر سەری لیست بێت
        if current and current.data == key:
            self.head = current.next
            current = None
            return
        
        # گەڕان بەدوای نۆدەکە
        prev = None
        while current and current.data != key:
            prev = current
            current = current.next
        
        # ئەگەر نۆدەکە نەدۆزرایەوە
        if current is None:
            return
        
        # جیاکردنەوەی نۆدەکە لە لیست
        prev.next = current.next
        current = None

باشی و خراپی لیستی بەستراو

باشییەکان

1. زیادکردن و سڕینەوەی دینامیکی: بەپێچەوانەی ئەڕەی، قەبارەی لیستی بەستراو دینامیکیە و پێویست ناکات پێشتر قەبارەکەی دیاری بکەیت
2. زیادکردن و سڕینەوەی ئاسان: لە سەرەتا و کۆتایی لیست زۆر خێرایە (O(1) بۆ سەرەتا)
3. بەکارهێنانی کاریگەری بیرگە: تەنها ئەو بیرگەیە بەکاردەهێنێت کە پێویستە
4. جێبەجێکردنی ئاسان: بۆ زۆر پێکهاتەی داتای تر وەک stack و queue بەکاردێت

خراپییەکان

1. دەستگەیشتنی ڕاستەوخۆ نییە: پێویستە بە شێوەی زنجیرەیی تێپەڕ بیت، ناتوانیت ڕاستەوخۆ بگەیتە نۆدێکی دیاریکراو
2. تێچووی بیرگەی زیاتر: هەر نۆدێک پێویستی بە بیرگەی زیاترە بۆ هەڵگرتنی ئاماژەکان
3. پەیمانکردنی دوو لایەن ئاڵۆزە: بەتایبەتی لە لیستی دوو لایەن، ئاڵۆزی زیاترە لە کاتی گۆڕینی پێکهاتەکەدا

بەکارهێنانەکانی لیستی بەستراو

1. لەبەرگرتنەوەی کردارەکان: لیستی کردارە نەهێڵکارەکان (Undo functionality) لە پرۆگرامەکان
2. پێکهاتەکانی تر: وەک بناغە بۆ جێبەجێکردنی ستاک، کیو، هاش تەیبڵ، گراف
3. سیستەمی بەڕێوەبردنی بیرگە: فایل سیستەم و سیستەمی بەڕێوەبردنی پرۆسێسەکان
4. ئەلگۆریتمەکانی ڕێکخستن: وەک Merge Sort

لیستی بەستراو یەکێکە لە گرنگترین پێکهاتەکانی داتا کە خوێندکارانی زانستی کۆمپیوتەر دەبێت بەتەواوەتی لێیان تێبگەن، چونکە بناغەی تێگەیشتنی زۆربەی پێکهاتە ئاڵۆزترەکانی داتایە.