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

Llistes Enllaçades

Següent ►
►

Introducció

Les llistes enllaçades són una estructura de dades fonamental que permet emmagatzemar una col·lecció d'elements de manera dinàmica. A diferència de les llistes estàtiques (com els arrays), les llistes enllaçades no requereixen una mida fixa i poden créixer o reduir-se segons sigui necessari.

Característiques Principals

  1. Nodes: Cada element d'una llista enllaçada es diu node. Cada node conté dues parts:

    • Dada: L'element que s'emmagatzema.
    • Enllaç: Un punter o referència al següent node de la llista.

  2. Cap: El primer node de la llista es coneix com a cap (head). Si la llista està buida, el cap és null.

  3. Dinàmica: Les llistes enllaçades poden créixer i reduir-se dinàmicament, ja que els nodes es creen i s'eliminen segons sigui necessari.

Tipus de Llistes Enllaçades

  1. Llista Enllaçada Simple: Cada node apunta només al següent node.
  2. Llista Doblement Enllaçada: Cada node apunta tant al següent com al node anterior.
  3. Llista Enllaçada Circular: L'últim node apunta al primer node, formant un cercle.

Implementació d'una Llista Enllaçada Simple

Estructura del Node

En una llista enllaçada simple, cada node conté una dada i un enllaç al següent node. A continuació es mostra una implementació bàsica en Python:

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

Estructura de la Llista Enllaçada

La classe de la llista enllaçada conté un punter al cap de la llista i mètodes per a les operacions bàsiques com afegir, eliminar i cercar elements.

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

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

    def append(self, data):
        new_node = Node(data)
        if self.is_empty():
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

Operacions Bàsiques

Afegir un Element

Per afegir un element al final de la llista, es crea un nou node i es recorre la llista fins trobar l'últim node, al qual se li assigna el nou node com a següent.

def append(self, data):
    new_node = Node(data)
    if self.is_empty():
        self.head = new_node
    else:
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node

Eliminar un Element

Per eliminar un element, es recorre la llista fins trobar el node amb la dada desitjada i es modifica l'enllaç del node anterior per saltar-se el node a eliminar.

def delete(self, key):
    current = self.head
    previous = None
    while current and current.data != key:
        previous = current
        current = current.next
    if previous is None:
        self.head = current.next
    elif current:
        previous.next = current.next
        current.next = None

Cercar un Element

Per cercar un element, es recorre la llista fins trobar el node amb la dada desitjada.

def search(self, key):
    current = self.head
    while current and current.data != key:
        current = current.next
    return current is not None

Exemple Complet

A continuació es mostra un exemple complet de com utilitzar la classe LinkedList:

if __name__ == "__main__":
    ll = LinkedList()
    ll.append(1)
    ll.append(2)
    ll.append(3)
    ll.display()  # Output: 1 -> 2 -> 3 -> None

    ll.delete(2)
    ll.display()  # Output: 1 -> 3 -> None

    print(ll.search(3))  # Output: True
    print(ll.search(2))  # Output: False

Exercicis Pràctics

Exercici 1: Afegir al Principi

Implementa un mètode prepend que afegeixi un element al principi de la llista.

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

Exercici 2: Invertir la Llista

Implementa un mètode reverse que inverteixi la llista enllaçada.

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

Exercici 3: Comptar Elements

Implementa un mètode count que compti el nombre de nodes en la llista.

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

Conclusió

Les llistes enllaçades són una estructura de dades versàtil i eficient per a moltes aplicacions. La seva implementació i manipulació requereix una comprensió clara dels punters i la gestió dinàmica de la memòria. Amb les operacions bàsiques i els exercicis pràctics proporcionats, hauríeu de tenir una bona base per treballar amb llistes enllaçades en els vostres projectes de programació.

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