القوائم المرتبطة في بايثون

المُقدّمة

القائمة المرتبطة هي بنية بيانات تتكون من سلسلة من العقد، تحتوي كل منها على قيمة ومرجع إلى العقدة التالية في التسلسل. على عكس المصفوفات، لا تتطلب القوائم المرتبطة تخصيصًا متجاورًا للذاكرة، مما يجعلها أكثر مرونة وكفاءة لعمليات معينة. في هذه المقالة، سوف نستكشف مزايا وعيوب القوائم المرتبطة وكيفية تنفيذها في بايثون.

مزايا وعيوب القوائم المرتبطة

توفر القوائم المرتبطة العديد من المزايا مقارنة بهياكل البيانات الأخرى. أولاً، تسمح بإدراج العناصر وحذفها بكفاءة، لأنها تتطلب فقط تحديث مراجع العقد المجاورة. وهذا يجعل LinkedLists مثاليًا للسيناريوهات التي يُتوقع فيها إجراء تعديلات متكررة. بالإضافة إلى ذلك، يمكن للقوائم المرتبطة أن تنمو أو تتقلص في الحجم ديناميكيًا، على عكس المصفوفات التي لها حجم ثابت.

ومع ذلك، فإن القوائم المرتبطة لها أيضًا بعض العيوب. على عكس المصفوفات، لا تدعم القوائم المرتبطة الوصول العشوائي إلى العناصر، مما يعني أن الوصول إلى عنصر في فهرس محدد يتطلب اجتياز القائمة من البداية. يمكن أن يؤدي هذا إلى أداء أبطأ لعمليات معينة. علاوة على ذلك، تتطلب القوائم المرتبطة ذاكرة إضافية لتخزين المراجع إلى العقد التالية، والتي قد تكون غير فعالة لمجموعات البيانات الصغيرة.

تنفيذ القوائم المرتبطة في بايثون

توفر Python طريقة مرنة وبديهية لتنفيذ القوائم المرتبطة. هناك ثلاثة أنواع رئيسية من القوائم المرتبطة: القائمة المرتبطة بشكل فردي، والقائمة المرتبطة بشكل مضاعف، والقائمة المرتبطة الدائرية. دعونا نستكشف كل واحد منهم بالتفصيل.

قائمة مرتبطة بشكل فردي

تتكون القائمة المرتبطة بشكل فردي من العقد حيث تحتوي كل عقدة على قيمة ومرجع إلى العقدة التالية في التسلسل. إليك كيفية إنشاء قائمة مرتبطة منفردة في بايثون:

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

class Linked List:
    def __init__(self):
        self.head = None

إنشاء قائمة مرتبطة منفردة

لإنشاء قائمة مرتبطة منفردة، نحتاج إلى تحديد فئة العقدة التي تمثل كل عقدة في القائمة. تحتوي كل عقدة على قيمة ومرجع إلى العقدة التالية. تعمل فئة القائمة المرتبطة كحاوية للعقد، حيث تشير سمة الرأس إلى العقدة الأولى في القائمة.

إدراج العقد في قائمة مرتبطة منفردة

يتضمن إدراج العقد في قائمة مرتبطة منفردة تحديث مراجع العقد المجاورة. فيما يلي مثال لإدراج عقدة في بداية القائمة:

def insert_at_beginning(self, value):
    new_node = Node(value)
    new_node.next = self.head
    self.head = new_node

حذف العقد من قائمة مرتبطة منفردة

يتطلب حذف العقد من القائمة المرتبطة بشكل فردي تحديث مراجع العقد المجاورة. فيما يلي مثال لحذف عقدة ذات قيمة محددة:

def delete_node(self, value):
    current = self.head
    if current.value == value:
        self.head = current.next
    else:
        while current.next:
            if current.next.value == value:
                current.next = current.next.next
                break
            current = current.next

البحث في قائمة مرتبطة منفردة

يتضمن البحث عن قيمة محددة في قائمة مرتبطة منفردة اجتياز القائمة حتى يتم العثور على القيمة أو الوصول إلى نهاية القائمة. فيما يلي مثال للبحث عن قيمة:

def search(self, value):
    current = self.head
    while current:
        if current.value == value:
            return True
        current = current.next
    return False

عكس قائمة مرتبطة منفردة

يتطلب عكس القائمة المرتبطة بشكل فردي تحديث مراجع كل عقدة للإشارة إلى العقدة السابقة. فيما يلي مثال على عكس قائمة مرتبطة منفردة:

def reverse(self):
    previous = None
    current = self.head
    while current:
        next_node = current.next
        current.next = previous
        previous = current
        current = next_node
    self.head = previous

قائمة مرتبطة بشكل مضاعف

تشبه القائمة المرتبطة بشكل مزدوج القائمة المرتبطة بشكل فردي، لكن كل عقدة تحتوي على مرجع لكل من العقدة التالية والعقدة السابقة في التسلسل. وهذا يسمح بالعبور الفعال في كلا الاتجاهين. إليك كيفية إنشاء قائمة مرتبطة بشكل مضاعف في بايثون:

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

class DoublyLinked List:
    def __init__(self):
        self.head = None

إنشاء قائمة مرتبطة بشكل مضاعف

لإنشاء قائمة مرتبطة بشكل مضاعف، نحدد فئة العقدة التي تحتوي على قيمة، ومرجع إلى العقدة التالية، ومرجع إلى العقدة السابقة. تعمل فئة القائمة DoublyLinked كحاوية للعقد، حيث تشير سمة الرأس إلى العقدة الأولى في القائمة.

إدراج العقد في قائمة مرتبطة بشكل مزدوج

يتضمن إدراج العقد في القائمة المرتبطة بشكل مزدوج تحديث مراجع العقد المجاورة. فيما يلي مثال لإدراج عقدة في بداية القائمة:

def insert_at_beginning(self, value):
    new_node = Node(value)
    if self.head:
        self.head.previous = new_node
    new_node.next = self.head
    self.head = new_node

حذف العقد من قائمة مرتبطة بشكل مضاعف

يتطلب حذف العقد من القائمة المرتبطة بشكل مزدوج تحديث مراجع العقد المجاورة. فيما يلي مثال لحذف عقدة ذات قيمة محددة:

def delete_node(self, value):
    current = self.head
    if current.value == value:
        self.head = current.next
        if self.head:
            self.head.previous = None
    else:
        while current.next:
            if current.next.value == value:
                current.next = current.next.next
                if current.next:
                    current.next.previous = current
                break
            current = current.next

البحث في قائمة مرتبطة بشكل مزدوج

يتضمن البحث عن قيمة محددة في القائمة المرتبطة بشكل مزدوج اجتياز القائمة في أي اتجاه حتى يتم العثور على القيمة أو الوصول إلى نهاية القائمة. فيما يلي مثال للبحث عن قيمة:

def search(self, value):
    current = self.head
    while current:
        if current.value == value:
            return True
        current = current.next
    return False

عكس قائمة مرتبطة بشكل مضاعف

يتطلب عكس القائمة المرتبطة بشكل مزدوج تحديث مراجع كل عقدة لتبديل المؤشرات التالية والسابقة. فيما يلي مثال على عكس القائمة المرتبطة بشكل مزدوج:

def reverse(self):
    current = self.head
    while current:
        next_node = current.next
        current.next = current.previous
        current.previous = next_node
        if not next_node:
            self.head = current
        current = next_node

قائمة مرتبطة دائرية

القائمة المرتبطة الدائرية هي شكل مختلف من القائمة المرتبطة بشكل فردي حيث تشير العقدة الأخيرة إلى العقدة الأولى، مما يؤدي إلى إنشاء بنية دائرية. وهذا يسمح بالاجتياز الفعال من أي عقدة في القائمة. إليك كيفية إنشاء قائمة مرتبطة دائرية في بايثون:

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

class CircularLinked List:
    def __init__(self):
        self.head = None

إنشاء قائمة مرتبطة دائرية

لإنشاء قائمة مرتبطة دائرية، نحدد فئة العقدة التي تحتوي على قيمة ومرجع إلى العقدة التالية. تعمل فئة القائمة CircularLinked كحاوية للعقد، حيث تشير سمة الرأس إلى العقدة الأولى في القائمة. بالإضافة إلى ذلك، يتم تعيين المرجع التالي للعقدة الأخيرة على الرأس، مما يؤدي إلى إنشاء بنية دائرية.

إدراج العقد في قائمة مرتبطة دائرية

يتضمن إدراج العقد في القائمة المرتبطة الدائرية تحديث مراجع العقد المجاورة. فيما يلي مثال لإدراج عقدة في بداية القائمة:

def insert_at_beginning(self, value):
    new_node = Node(value)
    if not self.head:
        self.head = new_node
        new_node.next = self.head
    else:
        current = self.head
        while current.next != self.head:
            current = current.next
        current.next = new_node
        new_node.next = self.head
        self.head = new_node

حذف العقد من القائمة المرتبطة الدائرية

يتطلب حذف العقد من القائمة المرتبطة الدائرية تحديث مراجع العقد المجاورة. فيما يلي مثال لحذف عقدة ذات قيمة محددة:

def delete_node(self, value):
    if not self.head:
        return
    current = self.head
    if current.value == value:
        while current.next != self.head:
            current = current.next
        if current == self.head:
            self.head = None
        else:
            current.next = self.head.next
            self.head = self.head.next
    else:
        previous = None
        while current.next != self.head:
            previous = current
            current = current.next
            if current.value == value:
                previous.next = current.next
                break

البحث في قائمة مرتبطة دائرية

يتضمن البحث عن قيمة معينة في القائمة المرتبطة الدائرية اجتياز القائمة حتى يتم العثور على القيمة أو اجتياز القائمة بأكملها. فيما يلي مثال للبحث عن قيمة:

def search(self, value):
    if not self.head:
        return False
    current = self.head
    while True:
        if current.value == value:
            return True
        current = current.next
        if current == self.head:
            break
    return False

عكس القائمة المرتبطة الدائرية

يتطلب عكس القائمة المرتبطة الدائرية تحديث مراجع كل عقدة لعكس البنية الدائرية. فيما يلي مثال على عكس القائمة المرتبطة الدائرية:

def reverse(self):
    if not self.head:
        return
    previous = None
    current = self.head
    next_node = current.next
    while True:
        current.next = previous
        previous = current
        current = next_node
        next_node = next_node.next
        if current == self.head:
            break
    self.head = previous

العمليات المشتركة على القوائم المرتبطة

تدعم القوائم المرتبطة العديد من العمليات الشائعة التي يمكن إجراؤها على العناصر. دعونا نستكشف بعض هذه العمليات:

الوصول إلى العناصر في القائمة المرتبطة

للوصول إلى العناصر الموجودة في القائمة المرتبطة، يمكننا اجتياز القائمة بدءًا من العقدة الرئيسية والانتقال إلى العقدة التالية حتى نصل إلى الموضع المطلوب. فيما يلي مثال للوصول إلى عنصر في فهرس محدد:

def get_element(self, index):
    current = self.head
    count = 0
    while current:
        if count == index:
            return current.value
        count += 1
        current = current.next
    raise IndexError("Index out of range")

تعديل العناصر في القائمة المرتبطة

يتضمن تعديل العناصر في القائمة المرتبطة اجتياز القائمة للعثور على العنصر المطلوب وتحديث قيمته. فيما يلي مثال لتعديل عنصر في فهرس محدد:

def modify_element(self, index, new_value):
    current = self.head
    count = 0
    while current:
        if count == index:
            current.value = new_value
            return
        count += 1
        current = current.next
    raise IndexError("Index out of range")

العثور على طول القائمة المرتبطة

للعثور على طول القائمة المرتبطة، يمكننا اجتياز القائمة وحساب عدد العقد. فيما يلي مثال للعثور على طول القائمة المرتبطة:

def get_length(self):
    current = self.head
    count = 0
    while current:
        count += 1
        current = current.next
    return count

التحقق مما إذا كانت القائمة المرتبطة فارغة

للتحقق مما إذا كانت القائمة المرتبطة فارغة، يمكننا ببساطة التحقق مما إذا كانت العقدة الرئيسية لا شيء. فيما يلي مثال للتحقق مما إذا كانت القائمة المرتبطة فارغة:

def is_empty(self):
    return self.head is None

تسلسل القوائم المرتبطة

لربط قائمتين مرتبطتين، يمكننا اجتياز القائمة الأولى للعثور على العقدة الأخيرة وتحديث مرجعها التالي إلى رأس القائمة الثانية. فيما يلي مثال لتسلسل قائمتين مرتبطتين:

def concatenate(self, other_list):
    if not self.head:
        self.head = other_list.head
    else:
        current = self.head
        while current.next:
            current = current.next
        current.next = other_list.head

القائمة المرتبطة مقابل المصفوفة

تعد القوائم والمصفوفات المرتبطة من هياكل البيانات شائعة الاستخدام، ولكن لها خصائص مختلفة تجعلها مناسبة لسيناريوهات مختلفة. دعونا نقارن بين القوائم والمصفوفات المرتبطة من حيث كفاءة الذاكرة، وكفاءة الإدراج والحذف، وكفاءة الوصول العشوائي.

كفاءة الذاكرة

تعد القوائم المرتبطة أكثر كفاءة في الذاكرة من المصفوفات لأنها لا تتطلب تخصيصًا متجاورًا للذاكرة. تحتاج كل عقدة في القائمة المرتبطة فقط إلى تخزين القيمة والإشارة إلى العقدة التالية، بينما تحتاج المصفوفات إلى تخصيص ذاكرة لجميع العناصر، حتى لو لم يتم استخدامها.

كفاءة الإدراج والحذف

تتفوق القوائم المرتبطة في عمليات الإدراج والحذف، خاصة عندما تتم إضافة العناصر أو إزالتها بشكل متكرر من منتصف القائمة. يتطلب إدراج عنصر أو حذفه في قائمة مرتبطة فقط تحديث مراجع العقد المجاورة، بينما قد تتطلب المصفوفات تغيير العناصر لاستيعاب التغيير.

كفاءة الوصول العشوائي

توفر المصفوفات وصولاً عشوائيًا فعالاً إلى العناصر بناءً على مؤشراتها، لأنها تسمح بالمعالجة المباشرة للذاكرة. في المقابل، تتطلب القوائم المرتبطة اجتياز القائمة من البداية للوصول إلى عنصر في فهرس محدد، مما يؤدي إلى أداء أبطأ لعمليات الوصول العشوائي.

اختيار بنية البيانات الصحيحة

يعتمد الاختيار بين القوائم المرتبطة والمصفوفات على المتطلبات المحددة للتطبيق. إذا كان من المتوقع إجراء تعديلات متكررة وتغيير الحجم الديناميكي، فإن القوائم المرتبطة هي الخيار الأفضل. من ناحية أخرى، إذا كان الوصول العشوائي وكفاءة الذاكرة أمرًا بالغ الأهمية، فإن المصفوفات تكون أكثر ملاءمة.

تطبيقات القائمة المرتبطة

الآن بعد أن أصبح لدينا فهم جيد للقوائم المرتبطة وكيفية عملها، دعنا نستكشف بعض التطبيقات العملية حيث يمكن استخدام القوائم المرتبطة بفعالية.

يمكنك أيضًا التسجيل في موقعنا دورات مجانية اليوم!

تنفيذ الأكوام وقوائم الانتظار

أحد التطبيقات الأكثر شيوعًا للقوائم المرتبطة هو تنفيذ المكدسات وقوائم الانتظار. تعد كل من الأكوام وقوائم الانتظار من أنواع البيانات المجردة التي يمكن تنفيذها بسهولة باستخدام القوائم المرتبطة.

المكدس عبارة عن بنية بيانات تتبع مبدأ Last-In-First-Out (LIFO). تتم إضافة العناصر وإزالتها من نفس النهاية، والمعروفة باسم الجزء العلوي من المكدس. توفر القوائم المرتبطة طريقة فعالة لتنفيذ الحزم المكدسة حيث يمكننا بسهولة إضافة أو إزالة العناصر من رأس القائمة.

فيما يلي مثال لتنفيذ مكدس باستخدام قائمة مرتبطة في بايثون:

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

class Stack:
    def __init__(self):
        self.head = None

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def pop(self):
        if self.head is None:
            return None
        popped = self.head.data
        self.head = self.head.next
        return popped

من ناحية أخرى، تتبع قائمة الانتظار مبدأ "الداخل أولاً يخرج أولاً" (FIFO). تتم إضافة العناصر من أحد الطرفين، المعروف باسم الجزء الخلفي، وإزالتها من الطرف الآخر، المعروف باسم الجزء الأمامي. يمكن أيضًا استخدام القوائم المرتبطة لتنفيذ قوائم الانتظار بكفاءة.

فيما يلي مثال لتنفيذ قائمة انتظار باستخدام قائمة مرتبطة في بايثون:

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

class Queue:
    def __init__(self):
        self.front = None
        self.rear = None

    def enqueue(self, data):
        new_node = Node(data)
        if self.rear is None:
            self.front = new_node
            self.rear = new_node
        else:
            self.rear.next = new_node
            self.rear = new_node

    def dequeue(self):
        if self.front is None:
            return None
        dequeued = self.front.data
        self.front = self.front.next
        if self.front is None:
            self.rear = None
        return dequeued

التعامل مع مجموعات البيانات الكبيرة

تعد القوائم المرتبطة مفيدة أيضًا عند التعامل مع مجموعات البيانات الكبيرة. على عكس المصفوفات، لا تتطلب القوائم المرتبطة تخصيصًا متجاورًا للذاكرة. وهذا يعني أن القوائم المرتبطة يمكنها التعامل بكفاءة مع مجموعات البيانات ذات الأحجام المختلفة دون الحاجة إلى تغيير الحجم أو إعادة التخصيص.

على سبيل المثال، لنفترض أن لدينا مجموعة بيانات تضم ملايين السجلات، ونحتاج إلى إجراء عمليات مثل الإدراج أو الحذف أو الاجتياز. قد يكون استخدام مصفوفة لهذه المهمة غير فعال لأنه يتطلب تغيير العناصر عند الإدراج أو الحذف. ومع ذلك، باستخدام القائمة المرتبطة، يمكننا بسهولة إدراج العناصر أو حذفها عن طريق تحديث المؤشرات، مما يؤدي إلى عمليات أسرع.

خوارزميات اجتياز الرسم البياني

يمكن أيضًا تنفيذ خوارزميات اجتياز الرسم البياني، مثل البحث بالعرض الأول (BFS) والبحث بالعمق الأول (DFS)، باستخدام القوائم المرتبطة. في اجتياز الرسم البياني، نقوم بزيارة كل قمة أو عقدة في الرسم البياني بترتيب معين.

يمكن استخدام القوائم المرتبطة لتمثيل قائمة الجوار للرسم البياني، حيث تمثل كل عقدة في القائمة المرتبطة قمة ويتم تخزين القمم المجاورة لها كعقد قائمة مرتبطة. يسمح هذا التمثيل بالاجتياز واستكشاف الرسم البياني بكفاءة.

تمثيل متعدد الحدود

يمكن استخدام القوائم المرتبطة لتمثيل كثيرات الحدود بكفاءة. في الرياضيات، كثيرات الحدود هي تعبيرات تتكون من متغيرات ومعاملات. يمكن تمثيل كل حد في كثيرة الحدود كعقدة في قائمة مرتبطة، حيث يتم تخزين المعامل والأس كبيانات.

باستخدام القوائم المرتبطة، يمكننا بسهولة إجراء العمليات على كثيرات الحدود، مثل الجمع والطرح والضرب. يمكن التلاعب بالعقد لتنفيذ هذه العمليات، مما يؤدي إلى تمثيل موجز وفعال لكثيرات الحدود.

قوائم تشغيل الموسيقى والفيديو

تُستخدم القوائم المرتبطة بشكل شائع لتنفيذ قوائم التشغيل في مشغلات الموسيقى والفيديو. يمكن تمثيل كل أغنية أو مقطع فيديو كعقدة في قائمة مرتبطة، حيث تحتوي البيانات على معلومات حول ملف الوسائط ويشير المؤشر إلى الأغنية أو الفيديو التالي في قائمة التشغيل.

يتيح استخدام القوائم المرتبطة لقوائم التشغيل سهولة التنقل بين الأغاني أو مقاطع الفيديو. يمكننا بسهولة إضافة أو إزالة الأغاني من قائمة التشغيل عن طريق تحديث المؤشرات، مما يوفر تجربة مستخدم سلسة.

وفي الختام

في الختام، القوائم المرتبطة هي هياكل بيانات متعددة الاستخدامات تجد تطبيقات في مجالات مختلفة. يمكن استخدامها لتنفيذ الأكوام وقوائم الانتظار، والتعامل مع مجموعات البيانات الكبيرة، وتنفيذ اجتياز الرسم البياني، وتمثيل كثيرات الحدود، وإنشاء قوائم التشغيل. توفر القوائم المرتبطة حلولاً فعالة لهذه المشكلات من خلال الاستفادة من تخصيص الذاكرة الديناميكية وسهولة التعامل مع العقد.

من خلال فهم تطبيقات القوائم المرتبطة، يمكننا اتخاذ قرارات مستنيرة عند اختيار هياكل البيانات لبرامجنا. سواء أكان الأمر يتعلق بإدارة البيانات، أو تنفيذ الخوارزميات، أو إنشاء واجهات سهلة الاستخدام، فإن القوائم المرتبطة توفر أداة قيمة في مجموعة أدوات المبرمج.

لذلك، في المرة القادمة التي تواجه فيها مشكلة تتطلب الإدراج أو الحذف أو الاجتياز بكفاءة، فكر في استخدام القوائم المرتبطة لتبسيط الحل الخاص بك وتحسين التعليمات البرمجية الخاصة بك.

يمكنك أيضًا قراءة المزيد من المقالات المتعلقة بقوائم Python هنا:

الأسئلة المتكررة

مقالات ذات صلة

• محتوى مدعوم من تحسين محركات البحث وتوزيع العلاقات العامة. تضخيم اليوم.
• PlatoData.Network Vertical Generative Ai. تمكين نفسك. الوصول هنا.
• أفلاطونايستريم. ذكاء Web3. تضخيم المعرفة. الوصول هنا.
• أفلاطون كربون، كلينتك ، الطاقة، بيئة، شمسي، إدارة المخلفات. الوصول هنا.
• أفلاطون هيلث. التكنولوجيا الحيوية وذكاء التجارب السريرية. الوصول هنا.
• المصدر https://www.analyticsvidhya.com/blog/2024/02/linked-lists-in-python/