Introducció

Les llistes dobles enllaçades són una extensió de les llistes enllaçades simples. En una llista enllaçada simple, cada node conté un enllaç al següent node de la seqüència. En canvi, en una llista doble enllaçada, cada node conté dos enllaços: un al següent node i un altre al node anterior. Això permet una navegació bidireccional, facilitant certes operacions com la inserció i l'eliminació de nodes.

Característiques Principals

Nodes Doblement Enllaçats: Cada node té dos enllaços, un al següent node i un altre al node anterior.
Capçalera i Cua: La llista té un node capçalera (head) i un node cua (tail).
Navegació Bidireccional: Es pot navegar tant cap endavant com cap enrere a través de la llista.

Estructura d'un Node

Un node en una llista doble enllaçada es pot representar de la següent manera en Python:

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

Implementació de la Llista Doblement Enllaçada

A continuació, es mostra una implementació bàsica d'una llista doble enllaçada en Python:

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node

    def prepend(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node

    def delete(self, data):
        current = self.head
        while current:
            if current.data == data:
                if current.prev:
                    current.prev.next = current.next
                if current.next:
                    current.next.prev = current.prev
                if current == self.head:
                    self.head = current.next
                if current == self.tail:
                    self.tail = current.prev
                return
            current = current.next

    def display_forward(self):
        current = self.head
        while current:
            print(current.data, end=" ")
            current = current.next
        print()

    def display_backward(self):
        current = self.tail
        while current:
            print(current.data, end=" ")
            current = current.prev
        print()

Explicació del Codi

Inicialització: La classe DoublyLinkedList inicialitza amb head i tail com a None.
Append: Afegeix un nou node al final de la llista. Si la llista està buida, el nou node es converteix en el cap i la cua. Si no, el nou node es col·loca després de la cua actual i es converteix en la nova cua.
Prepend: Afegeix un nou node al principi de la llista. Si la llista està buida, el nou node es converteix en el cap i la cua. Si no, el nou node es col·loca abans del cap actual i es converteix en el nou cap.
Delete: Elimina el primer node que conté el valor especificat. Si el node a eliminar és el cap o la cua, es realitzen les actualitzacions necessàries.
Display Forward: Mostra els elements de la llista des del cap fins a la cua.
Display Backward: Mostra els elements de la llista des de la cua fins al cap.

Exercici Pràctic

Implementa una funció que insereixi un nou node després d'un node específic en una llista doble enllaçada.

Solució

def insert_after(self, target_data, new_data):
    current = self.head
    while current:
        if current.data == target_data:
            new_node = Node(new_data)
            new_node.next = current.next
            new_node.prev = current
            if current.next:
                current.next.prev = new_node
            current.next = new_node
            if current == self.tail:
                self.tail = new_node
            return
        current = current.next

Explicació

Buscar el Node: La funció busca el node que conté target_data.
Crear el Nou Node: Un nou node es crea amb new_data.
Actualitzar Enllaços: Els enllaços del nou node i els nodes adjacents es modifiquen per inserir el nou node després del node objectiu.
Actualitzar la Cua: Si el node objectiu és la cua, el nou node es converteix en la nova cua.

Conclusió

Les llistes dobles enllaçades ofereixen una major flexibilitat en la navegació i manipulació de nodes en comparació amb les llistes enllaçades simples. Tot i que requereixen més memòria per emmagatzemar els enllaços addicionals, les seves operacions poden ser més eficients en certs casos. Practicar amb aquestes estructures de dades és essencial per comprendre millor les seves aplicacions i avantatges.

Llistes Doblement Enllaçades

Introducció

Característiques Principals

Estructura d'un Node

Implementació de la Llista Doblement Enllaçada

Explicació del Codi

Exercici Pràctic

Solució

Explicació

Conclusió

Curs d'Estructures de Dades

Mòdul 1: Introducció a les Estructures de Dades

Mòdul 2: Llistes

Mòdul 3: Piles

Mòdul 4: Cues

Mòdul 5: Arbres

Mòdul 6: Grafs

Mòdul 7: Conclusions i Recursos Addicionals