Enlace Patrocinado

¿Por qué las listas enlazadas en C / C ++ son tan difíciles de implementar?

Enlace Patrocinado
Debe ser porque no has intentado implementarlas en Rust. Ahora mismo aprovecho la cuarentena para aprender este lenguaje, y una de las primeras cosas que intento hacer es esa estructura de datos.
Implementar una lista enlazada (que sea safe) en Rust es algo complicado: uno parece estarse peleando todo el tiempo con el borrow checker y los lifetimes que aún no le he agarrado del todo la onda.
Crear una lista simplemente enlazada en C o C++ es algo trivial, pero en Rust es una pequeña pesadilla.
Esta es una lista simplemente enlazada en Rust
 con algunos métodos para demo:
Enlace Patrocinado 




  1. // Lista 'simplemente' enlazada en Rust 





  2.  





  3. // type alias por conveniencia 





  4. type Link<T> = Option<Box<Node<T>>>; 





  5. use std::fmt; 





  6. use std::mem::replace as exchange; 





  7. // Single link list 





  8. struct SingleList<T> 





  9. where T: std::fmt::Display, { 





  10.     head: Link<T>, 





  11.     size: usize, 





  12. } 





  13.  





  14. // Nodo generico 





  15. struct Node<T> { 





  16.     elem: T, 





  17.     next: Link<T>, 





  18. } 





  19. // implementacion 





  20. // ... resto del código en el enlace 



Lo primero que voy a comentar el el tipo de dato Node:



  1. struct Node<T> { 





  2.     elem: T, 





  3.     next: Link<T>, 





  4. } 



¿Qué es Link<T>? Por lo general esperamos que el campo next sea algo asi como Node<T>*, pero en Rust (safe) no se manejan punteros de esa manera; además el lenguaje necesitaría saber el tamaño de un Node<T> y como haría entonces si uno de sus miembros es del mismo tipo que estoy definiendo? No es posible. Sin embargo, el tamaño de un Box<Node<T>> si es conocido. Link<T> es entonces:



  1. type Link<T> = Option<Box<Node<T>>>; 



Es decir un alias para Option<Box<Node<T>>>. Option es necesario porque al no existir (null, NULL, nullptr) y next podría o no refererirse a un siguiente nodo. Como crearé los nodos en la heap entonces debo envolverlos en Box<T> que es un managed pointer parecido a std::unique_ptr en C++.
El keyword type es análogo a typedef en C.
Con mi nodo definido creamos la lista propiamente:



  1. struct SingleList<T>{ 





  2.     head: Link<T>, 





  3.     size: usize, 





  4. } 



Solo contiene dos miembros head “que es de tipo Node<T>” y el miembro size que es el tamaño de la lista. La funcionalidad de la lista (sus métodos) los implemento en en un bloque impl y son funciones asociadas a el estructura de dato:



  1. impl<T> SingleList<T> { 





  2.     // nueva lista vacia 





  3.     pub fn new() -> Self { 





  4.         Self{head: None, size: 0} 





  5.     }     





  6.     // check 





  7.     pub fn is_empty(&self) -> bool{ 





  8.         self.size==0 





  9.     } 





  10. // ... más funciones 





  11. } 



Noten la diferencia entre las funciones new y is_empty. La primera no toma ningún argumentos y esto es porque su labor es crear una nueva lista; la segunda toma un argumento por referencia (shared reference o immutable reference como también se les refiere). self (sí como en Python) se refiere a la instancia a la que está asociada la función (is_empty en este caso). La notación del argumento de la última función es un shorthand para: is_empty(self: &SingleList<T>) pero dentro del bloque impl como primer argumento self es especial y también lo es Self que es el tipo de dato de self, es decir SingleList<T>, o sea que también podría escribir is_empy(self: &Self). Pero esos son detalles, veamos como implementar algunas otrasde las funciones propias de una lista.
Como es una lista simplemente enlazada lo más fácil de hacer es agregar elementos a la cabeza de la lista:



  1.   pub fn push_front(&mut self, elem: T){ 





  2.      let ref mut head = exchange(&mut self.head, None); 





  3.   // creo nuevo node 





  4.      let new_node = match head { 





  5.        Some(ref mut _node) =>{  





  6.         // creo nuevo nodo apuntando 'next' 





  7.      // a la antigua head 





  8.         Some(Box::new(Node{elem, next: head.take()}));}, 





  9.        None => 





  10.      // next es None  





  11.      Some(Box::new(Node{elem, next: None})) 





  12.      } 





  13.   // actualizo 





  14.   self.head = new_node; 





  15.   self.size += 1; 





  16.     } 



Esta vez como agregar un elemento en una lista requiere mutar la lista, el argumento self adquiere otra notación &mut self que es una referencia exclusiva en Rust. Exclusiva como que solo a través de ella puedo referirme al argumento, por ello en la línea dos la intercambio y tomo ownership en head. Sobre la cual hago un match en la siguiente línea y si no es None creo un nuevo nodo con el elem y el compo next apuntando/refiriendose a head (head.take es un shortcut para exchange(&mut head, None) y exchange es un alias para std::mem::replace.
Está escrita así para de alguna forma ir paso a paso pero si ven atentamente se puede reescribir muy facilmente:



  1.  pub fn push_front(&mut self, elem: T){ 





  2.      self.head = Some(Box::new(Node{ 





  3.             elem,  





  4.             next: self.head.take()})); 





  5.         self.size += 1; 





  6. } 



Aunque no es común en una lista simplemente enlazada le agregue un push_back para añadir un elemento al final de la lista con la counterpart a push_front y notar la diferencia:



  1. pub fn push_back(&mut self, elem: T) { 





  2.         let mut it: &mut Link<T> = &mut self.head;         





  3.         // encontrar el final 





  4.         while let Some(ref mut node) = it { 





  5.             it = &mut node.next; 





  6.         } 





  7.         // aquí ya `it` es None. 





  8.         *it = Some(Box::new(Node{ 





  9.             elem,  





  10.             next: None 





  11.         })); 





  12.         self.size += 1; 





  13. } 



Nota: este método podría optimizarse si mantengo una referencia al último nodo.
Eliminar un elemento del principio/cabeza de la lista igual es muy fácil:



  1. // remove (primer elemento) 





  2.     pub fn pop_front(&mut self) -> Option<T> { 





  3.        match exchange(&mut self.head, None) { 





  4.             Some(node) => { 





  5.                 self.size -= 1; 





  6.                 self.head = node.next; 





  7.                 Some(node.elem) 





  8.             }, 





  9.             None => None 





  10.         } 





  11.     }  



Que puedo igualmente simplificar más



  1. // remove (primer elemento) 





  2. pub fn pop_front(&mut self) -> Option<T> { 





  3.     self.head.take().map(|node| { 





  4.   self.size -= 1; 





  5.   self.head = node.next; 





  6.   node.elem 





  7.  }) 





  8. }  



PERO la que viene a continuación pop_back para eliminar un elemento del final me tuvo varias horas tratando de hallar la disposición correcta de las referencias, etc.:
Honestamente NO quiero tener que explicarla, pero comparen con las demás y, por ejemplo, una función para remover un elemento previo a otro determinado se puede sacar muy fácilmente de aquí y no la incluí aquí.
Los demás métodos de la lista son para iterar, imprimir y destrucción de la lista cosa que hace Rust automáticamente pero que es necesario en este caso para no desbordar la pila de agregarse demasiados elementos a la lista ya que la eliminación de los nodos se hace de forma recursiva. Para romper la recursión:



  1. // Dtor 





  2. impl<T> Drop for SingleList<T> { 





  3.  fn drop(&mut self) { 





  4.   let mut it = self.head.take(); 





  5.   while let Some(ref mut n) = it { 





  6.    it = n.next.take(); // "nullify" el miembro next aquí 





  7.                                 // rompe la recursion 





  8.   } 





  9.         println!("Dropped!"); 





  10.  } 





  11. } 



No sé Uds. pero no me parece ahora que en C o C++ sea más complicado. ¿Puedo convertir esta lista a una doblemente enlazada agregando un miembro prev y tail a Node y SingleList respectivamente? Noooo… entre otras cosas para una lista doblemente enlazada ya no podría usar Box sino Rc (std::rc::Rc) y como en algún momento podría requerirse mutar los elementos en la lista y Rc no me lo permitiría, tendría que además envolver Node<T> en un RefCell (std::cell::RefCell), etc.
¿Qué hay acerca de la optimisation para push_back de la que hablé en la nota arriba? Dado que las referencias en Rust son reasignables pensé (naively) que lo podía lograr fácilmente… me equivoqué. Intenté:



  1. struct Node<T> { 





  2.     elem: T, 





  3.     next: Link<T>, 





  4.  last: &Link<T>, // siempre apunta al último nodo 





  5. } 



y luego modificaría:



  1. pub fn push_front(&mut self, elem: T){ 





  2.      let ref mut head = exchange(&mut self.head, None); 





  3.   // creo nuevo node 





  4.      let new_node = match head { 





  5.        Some(ref mut _node) =>{  





  6.         // creo nuevo nodo apuntando 'next' 





  7.      // a la antigua head 





  8.         Some(Box::new(Node{elem, next: head.take()}));}, 





  9.        None => { 





  10.      // next es None  





  11.      let new_node =Some(Box::new(Node{elem, next: None})) 





  12.      // como es el único elemento 





  13.      // `head` y `last` se refieren al mismo nodo 





  14.      self.last = new_node; 





  15.      new_node },    





  16.      } 





  17.   // actualizo 





  18.   self.head = new_node; 





  19.   self.size += 1; 





  20.     } 



Eso, por su puesto, no funciona. Primero antes de guardar una referencia en un struct debo asociar un lifetime:



  1. struct Node<'a, T> { 





  2.     elem: T, 





  3.     next: Link<T>, 





  4.  last: &'a Link<T>, // siempre apunta al último nodo 





  5. } 



Solo hasta ahí todo bien, cuando intento modificar push_front y demás métodos donde manipulo self.tail fracaso. No hay manera tal y como esta escrita la lista. Debería utilizar std::rc::Rc si quiero que tener dos (o más) referencias a un mismo nodo (podría ahondar más en esto en una próxima actualización).
No sería justo cuando hablamos de comparaciones si no incluyo una versión en C (o C++). Hagamos la lista en C, tal como la versión en Rust debe ser genérica y además incluir la optimisation que no pude lograr, esta vez, en Rust:
Codigo (Rust) live: [Wandbox]三へ( へ՞ਊ ՞)へ ﾊｯﾊ
Links:
  • Iterator
     (trait)
  • Box 
    (pointer)
  • Display 
    (trait)
  • std::ops::Drop – Rust
     (trait)
  • Learn Rust with Entirely too many Lists
  • std::forward_list – cppreference.com
Ahora trataré de convencerlos de que en C no tiene porque ser extremadamente complicado. Contando solo con los pocos mecanismos de abstracción de C nuestra lista debe ser «genérica» y extensible.
TODA mi lista la baso en esta estructura:



  1. typedef struct link_base link_base; 





  2.  





  3. struct link_base 





  4. { 





  5.     link_base *next; 





  6. }; 





  7.  





  8. typedef struct basic_list basic_list; 





  9.  





  10. struct basic_list 





  11. { 





  12.     link_base *b4_head; // b4_head->next es `head` 





  13.     link_base *last; 





  14.     int length; 





  15. }; 





  16.  





  17. bool is_empty(basic_list *); 





  18. // elementos agregados a la lista 





  19. int length(basic_list *); 





  20.  





  21. // las operaciones 'append/add/push_back/prepend/push_front' etc 





  22. // las defino sobre esta función 





  23. link_base *insert_after(basic_list *, link_base *, link_base *); 





  24.  





  25. // las operaciones 'erase/pop/pop_front/pop_back/insert' etc las  





  26. // defino sobre esta función 





  27. link_base *remove_after(basic_list *, link_base *); 



Nota que en ninguna parte se menciona el tipo de dato de la lista (también nada es void *). Este es pues mi lista abstracta.
La implementación de insert_after y remove_after:



  1. bool is_empty(basic_list *lst) 





  2. { 





  3.     return lst->b4_head->next == lst->last 





  4.             && lst->length == 0; 





  5. } 





  6.  





  7. int length(basic_list *lst){ return lst->length; } 





  8.  





  9. link_base *insert_after(basic_list *lst, link_base *wh, link_base *elnk) 





  10. { 





  11.     if(wh==0){ // agregamos al principio 





  12.         link_base **head = &((link_base *)lst->b4_head)->next; 





  13.         if(*head){ 





  14.             elnk->next = *head; 





  15.             *head = elnk; 





  16.         } 





  17.         else { 





  18.             *head = lst->last = elnk; 





  19.         } 





  20.     } 





  21.     else { 





  22.         elnk->next = wh->next; 





  23.         wh->next = elnk; 





  24.  





  25.         if(wh == lst->last) 





  26.             lst->last = elnk; 





  27.     } 





  28.  





  29.     ++lst->length; 





  30.     return elnk; 





  31. } 





  32.  





  33.  





  34. link_base *remove_after(basic_list *lst, link_base *wh) 





  35. { 





  36.     link_base *it = wh? wh->next: lst->b4_head->next; 





  37.  





  38.     if(wh == 0){ 





  39.         int steps = lst->length - 1; 





  40.         while(--steps) 





  41.             it = it->next; 





  42.         lst->last = it; 





  43.     } 





  44.     else { 





  45.         wh->next = it->next; 





  46.     } 





  47.     it->next = 0; 





  48.     --lst->length; 





  49.     return it; 





  50. } 



Las listas enlazadas pueden ser complicadas en C si:
  1. No comprendes bien la estructura de datos, o
  2. No comprendes bien punteros.
Yo suelo extenderme hablando de punteros y ya la respuesta esta bastante larga, solo comentaré acerca de las estrategias en la implementación de ambas funciones.
insert_after recibe la lista a modifica, un puntero que indica donde insertar el nuevo nodo y el nuevo nodo que contiene el elemento. La idea aquí es que, por tratarse de una lista sencillamente enlazada, el segundo puntero (wh) sea el elemento previo; esto es, el nuevo nodo será wh->next. Por convención si wh == 0 indica que insertemos al principio y esto me permite implementar operaciones (push_front/prepend/etc). Luego un push_back lo implemento pasando como segundo puntero el campo last de la lista. Este campo es un puntero al último elemento de la lista, es la referencia que no pude agregar en la implementación con Rust. Entonces el nuevo elemento quedará en last->next. Las operaciones en insert_after son constantes. remove_after utiliza una estrategia similar, el segundo puntero me indica el elemento previo a eliminar. Nota que en la lista hay un campo b4_head y que head propiamente es b4_head->next. Todo esto para seguir la estrategia que utilizan las operaciones insert/remove_after.
Ahora bien, como creo una lista concreta? Hay varias maneras, comencemos con una lista para gestionar caracteres (chars):



  1. struct char_link 





  2. { 





  3.     link_base base_; 





  4.     char data; 





  5. }; 





  6.  





  7. struct char_list 





  8. { 





  9.     struct 





  10.     { 





  11.         struct char_link *b4_head; 





  12.         struct char_link *last; 





  13.         int length; 





  14.     }; 





  15. }; 



Nota el campo base_ de tipo link_base en la estructura char_link. Esto me permite tratar un puntero a char_link como uno a link_base. Luego char_list es básicamente un basic_list salvo que los campos b4_head y last son de tipo char_link* pero como estos son convertible a link_base entonces char_list es un basic_list.
Eso es lo que debo hacer para una lista de cualquier tipo de dato, cambio el campo data con el tipo de dato apropiado y defino la lista. Ejemplo, para una lista de tipo con elementos de tipo int:



  1. struct int_link 





  2. { 





  3.     link_base base_; 





  4.     int data; 





  5. }; 





  6.  





  7. struct int_list 





  8. { 





  9.     struct 





  10.     { 





  11.         struct int_link *b4_head; 





  12.         struct int_link *last; 





  13.         int length; 





  14.     }; 





  15. }; 



Ahora como ejemplo implementemos las funciones que definen una lista enlazada:



  1. // push_front: agregar al inicio 





  2. void push_front_char(char_list *lst, char element) 





  3. { 





  4.  // crea el nodo 





  5.     char_link *e = malloc(sizeof *e); 





  6.     if(e){ 





  7.   *e = (char_link){}; 





  8.   e->data = element; 





  9.   insert_after((basic_list*)lst, 0, (link_base*)e); 





  10. } 



La función solo se encarga de la creación del nodo y la gestión de este se delega a insert_after.



  1. // pop_front: elimina un elemento del inicio de la lista 





  2. char pop_front_char(char_list *lst) 





  3. { 





  4.  char_link *e = remove_after((basic_list*)lst, 





  5.         (link_base*)lst->b4_head); 





  6.     char elem = e->data; 





  7.     free(e); 





  8.     return elem; 





  9. } 



Es convencional que pop devuela el elemento eliminado.
Otra operación de la lista que no hemos hablado es clear. Para la cual podemos utilizar remove_after directamente o convenientemente a traves de pop_front_char:



  1. // clear: deja la lista tal que is_empty((basic_list*)lst)==true. 





  2. void clear_char_list(char_list *lst) 





  3. { 





  4.  while(length((basic_list*)lst)) 





  5.   pop_front_char(lst); 





  6. } 



Así de fácil. Esta bien, las estructuras de datos tienen sus detalles y C, muy a pesar de lo que muchos dicen, no es un lenguaje para principiantes. Pero tampoco tienen que ser mucho más difícil que en otros lenguajes y si resulta así es por el poco conocimiento de la estructura de datos o poco conocimiento del lenguaje que uses para implementarla (tal es mi caso con Rust en el ejemplo). Espero que se vea el patrón… tal vez más adelante agregue C++ y el repo con el código.
Cualquier duda/corrección, en los comentarios.

2 comentarios en “¿Por qué las listas enlazadas en C / C ++ son tan difíciles de implementar?”

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Scroll al inicio