Ordenar lista enlazada en C++

1. Lista en C++
2. Implementar una lista enlazada en C++
3. Ordenar una lista enlazada en C++

Este tutorial de programación trivial demuestra la implementación de la operación de clasificación en una estructura de datos de lista enlazada en C++.

Lista en C++

List o Linked List es una estructura de datos lineal que puede servir como contenedor de datos y almacenar los datos en la memoria. A diferencia de los vectores o matrices, los datos de la lista no requieren ubicaciones de memoria consecutivas; en su lugar, los datos pueden crecer dinámicamente y asignarse a ubicaciones arbitrarias de memoria en montón.

Cada elemento de la lista se denomina nodo. Cada nodo de una lista contiene un puntero que apunta al siguiente nodo de la lista.

Incluir el puntero al elemento siguiente en cada nodo puede facilitar el encadenamiento lineal donde se puede acceder a cada elemento siguiente a través del nodo anterior. Este encadenamiento lineal entre los nodos es la principal razón para dar a esta estructura el nombre de Lista Enlazada.

Se pueden realizar varias operaciones ADT (tipo de datos abstractos) en la lista vinculada, como inserción, eliminación, búsqueda e incluso clasificación. Comenzaremos con la implementación estructural básica de la lista enlazada y luego implementaremos el algoritmo de clasificación en esa clase.

Implementar una lista enlazada en C++

Ahora, comenzaremos la implementación de la Lista Enlazada. Para eso, primero, necesitamos crear una clase para Node como esta:

template <class T>
class Node {
 public:
  T data;
  Node<T>* next;
  Node() { next = 0; }
};

En esta clase hay dos miembros, uno para almacenar datos, es decir, info, y el otro es el puntero de la clase para almacenar la dirección del siguiente nodo. La clase se crea con una plantilla para que se pueda crear una lista de cualquier tipo de datos.

Ahora, crearemos una clase de lista enlazada como esta:

template <class T>
class LSLL {
 private:
  Node<T>* head;

 public:
  LSLL() { head = 0; }
  void insertAtHead(T val) {
    Node<T>* x = new Node<T>(val);
    x->next = head;
    head = x;
  }
  void displayAll() {
    Node<T>* x = head;
    {
      while (x != 0) {
        cout << x->info << endl;
        x = x->next;
      }
    }
  }
};

En esta clase, hay un constructor y otras dos funciones miembro para insertar y mostrar los nodos de la lista.

Ordenar una lista enlazada en C++

Implementaremos el algoritmo de clasificación más simple, Bubble Sort, para clasificar la lista enlazada en orden creciente. Este algoritmo de clasificación intercambia repetidamente elementos adyacentes si se colocan en un orden desordenado.

Esta operación se realiza repetidamente hasta que todos los elementos estén en su posición ordenada correcta. Esto se implementará de la siguiente manera:

void sortLinkedList() {
  Node<T> *curr = head, *temp = NULL;
  int t;
  if (head == NULL) {
    return;
  } else {
    while (curr != NULL) {
      temp = curr->next;
      while (temp != NULL) {
        if (curr->info > temp->info) {
          t = curr->info;
          curr->info = temp->info;
          temp->info = t;
        }
        temp = temp->next;
      }
      curr = curr->next;
    }
  }
}

El programa controlador será:

int main() {
  LSLL<int> list;
  list.insertAtHead(50);
  list.insertAtHead(45);
  list.insertAtHead(16);
  cout << "Before sorting" << endl;
  list.displayAll();
  cout << "After Sorting: " << endl;
  list.sortLinkedList();
  list.displayAll();
  return 0;
}

Producción :

Before sorting
43
65
13
After Sorting:
13
43
65