Implementar una lista enlazada con funciones de ordenamiento y búsqueda en Python

Document 对象参考手册Ejemplos de Python3

Usaremos Python para implementar una lista enlazada simple y le añadiremos funciones de ordenamiento y búsqueda. Una lista enlazada es una estructura de datos común que consta de una serie de nodos, cada nodo contiene datos y un puntero al siguiente nodo.

Ejemplo

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 not self.head:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

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

    def sort(self):
        if not self.head:
            return
        sorted_list = []
        current = self.head
        while current:
            sorted_list.append(current.data)
            current = current.next
        sorted_list.sort()
        self.head = None
        for item in sorted_list:
            self.append(item)

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

# Ejemplo de uso
ll = LinkedList()
ll.append(3)
ll.append(1)
ll.append(4)
ll.append(2)

print("Lista enlazada original:")
ll.display()

ll.sort()
print("Lista enlazada ordenada:")
ll.display()

print("Buscar elemento 4:", ll.search(4))
print("Buscar elemento 5:", ll.search(5))

Análisis del código:

  1. NodeClase: representa un nodo en la lista enlazada, contiene datosdatay un puntero al siguiente nodonext。
  2. LinkedListClase: representa la lista enlazada, contiene un puntero al nodo cabeza de la listahead。
  3. appendMétodo: agrega un nuevo nodo al final de la lista enlazada.
  4. displayMétodo: imprime todos los elementos de la lista enlazada.
  5. sortMétodo: ordena los elementos de la lista enlazada. Primero extrae los datos de la lista a una lista (array), luego ordena la lista y finalmente vuelve a insertar los datos ordenados en la lista enlazada.
  6. searchMétodo: busca el elemento especificado en la lista enlazada, si lo encuentra devuelveTrue, de lo contrario devuelveFalse。

Resultado de salida:

原始链表:
3 -> 1 -> 4 -> 2 -> None
排序后的链表:
1 -> 2 -> 3 -> 4 -> None
查找元素 4: True
查找元素 5: False

Document 对象参考手册Ejemplos de Python3

Otras extensiones