El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Llistes Circulars

Següent ►
►

Introducció a les Llistes Circulars

Les llistes circulars són una variació de les llistes enllaçades on l'últim node apunta al primer node, creant així una estructura circular. Aquesta característica permet que es pugui navegar per la llista de manera contínua sense arribar mai a un punt final.

Característiques de les Llistes Circulars

  • Circularitat: L'últim node apunta al primer node.
  • No tenen cap ni cua: No hi ha un punt d'inici o final definit, es pot començar des de qualsevol node.
  • Navegació contínua: Es pot recórrer la llista indefinidament.

Tipus de Llistes Circulars

Hi ha dos tipus principals de llistes circulars:

  1. Llista Circular Simplement Enllaçada: Cada node té un enllaç al següent node, i l'últim node enllaça al primer.
  2. Llista Circular Doblement Enllaçada: Cada node té enllaços tant al següent com al node anterior, i l'últim node enllaça al primer i viceversa.

Implementació de Llistes Circulars

Llista Circular Simplement Enllaçada

Estructura del Node

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

Creació de la Llista Circular

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

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            self.head.next = self.head
        else:
            temp = self.head
            while temp.next != self.head:
                temp = temp.next
            temp.next = new_node
            new_node.next = self.head

    def display(self):
        nodes = []
        temp = self.head
        if self.head:
            while True:
                nodes.append(temp.data)
                temp = temp.next
                if temp == self.head:
                    break
        print(" -> ".join(map(str, nodes)))

# Exemple d'ús
cll = CircularLinkedList()
cll.append(1)
cll.append(2)
cll.append(3)
cll.display()  # Sortida: 1 -> 2 -> 3

Llista Circular Doblement Enllaçada

Estructura del Node

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

Creació de la Llista Circular

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

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

    def display(self):
        nodes = []
        temp = self.head
        if self.head:
            while True:
                nodes.append(temp.data)
                temp = temp.next
                if temp == self.head:
                    break
        print(" <-> ".join(map(str, nodes)))

# Exemple d'ús
cdll = CircularDoublyLinkedList()
cdll.append(1)
cdll.append(2)
cdll.append(3)
cdll.display()  # Sortida: 1 <-> 2 <-> 3

Avantatges i Desavantatges de les Llistes Circulars

Avantatges

  • Navegació contínua: Ideal per aplicacions que requereixen un recorregut cíclic.
  • No hi ha nodes nuls: Sempre es pot accedir a un node següent.

Desavantatges

  • Complexitat: La implementació i manteniment poden ser més complicats que les llistes enllaçades lineals.
  • Accés aleatori: No és eficient per accedir a elements de manera aleatòria.

Exercicis Pràctics

Exercici 1: Inserció en una Llista Circular

Implementa una funció per inserir un node en una posició específica d'una llista circular simplement enllaçada.

Exercici 2: Eliminació en una Llista Circular

Implementa una funció per eliminar un node específic d'una llista circular doblement enllaçada.

Exercici 3: Cerca en una Llista Circular

Implementa una funció per cercar un element en una llista circular i retornar la seva posició.

Solucions als Exercicis

Solució a l'Exercici 1

def insert_at_position(cll, data, position):
    new_node = Node(data)
    if position == 0:
        new_node.next = cll.head
        temp = cll.head
        while temp.next != cll.head:
            temp = temp.next
        temp.next = new_node
        cll.head = new_node
    else:
        temp = cll.head
        for _ in range(position - 1):
            temp = temp.next
        new_node.next = temp.next
        temp.next = new_node

Solució a l'Exercici 2

def delete_node(cdll, key):
    temp = cdll.head
    if temp.data == key:
        if temp.next == cdll.head:
            cdll.head = None
        else:
            tail = cdll.head.prev
            cdll.head = temp.next
            cdll.head.prev = tail
            tail.next = cdll.head
    else:
        while temp.next != cdll.head:
            if temp.next.data == key:
                temp.next = temp.next.next
                temp.next.prev = temp
                break
            temp = temp.next

Solució a l'Exercici 3

def search(cll, key):
    temp = cll.head
    position = 0
    while True:
        if temp.data == key:
            return position
        temp = temp.next
        position += 1
        if temp == cll.head:
            return -1

Conclusió

Les llistes circulars són una eina poderosa per a certes aplicacions que requereixen una navegació contínua. Tot i que poden ser més complexes de gestionar que les llistes enllaçades lineals, ofereixen avantatges significatius en termes de navegació i accessibilitat. Amb la pràctica i la comprensió dels seus conceptes bàsics, es poden implementar de manera efectiva en diversos contextos de programació.

◄ Anterior
◄
Següent ►
►
El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2024. Tots els drets reservats