Implementación de plantillas de lista vinculada individualmente -- ++ campo con linked-list camp codereview Relacionados El problema

Singly linked list template implementation


3
vote

problema

Español

Mi implementación es solo para fines de estudio, estoy de acuerdo en que algunas de las características pueden ser contracuitivas.

Supongo que el mejor método es usar una lista en la biblioteca STL.

Cualquier mejoras será muy apreciada.

El siguiente código compila y funciona, si es posible, me gustaría que el código revisado en C ++ 98, si no es el más cercano a él, que es C ++ 03;

  #include <iostream> using namespace std;  template <class T> struct node {     node(T data) : data(data), next(NULL) {}     T data;     node<T> *next; };  template <class T> class linkedlist {     template<class U>     friend ostream &operator<<(ostream &os, const linkedlist<U> &rhs); private:     node<T> *head; public:     linkedlist() : head(NULL) {};     ~linkedlist();     linkedlist(const linkedlist &rhs);     linkedlist &operator=(const linkedlist &rhs);     void insert(const T data);     bool search(const T data) const;     void remove(const T data);     bool isEmpty() const;     bool operator==(const linkedlist<T> &rhs) const;     bool operator!=(const linkedlist<T> &rhs) const;     bool operator<(const linkedlist<T> &rhs) const;     bool operator>(const linkedlist<T> &rhs) const; };  template <class T> bool linkedlist<T>::operator!=(const linkedlist<T> &rhs) const {     return !(*this == rhs); }  template<class T> bool linkedlist<T>::operator<(const linkedlist<T>& rhs) const {     node<T> *lhsTemp = head;     node<T> *rhsTemp = rhs.head;     while (lhsTemp != NULL && rhsTemp != NULL)     {         if (lhsTemp->data > rhsTemp->data)             return false;         lhsTemp = lhsTemp->next;         rhsTemp = rhsTemp->next;     }     return true; }  template<class T> bool linkedlist<T>::operator>(const linkedlist<T>& rhs) const {     return rhs < *this; }  template <class T> bool linkedlist<T>::operator==(const linkedlist<T> &rhs) const {     node<T> *lhsTemp = head;     node<T> *rhsTemp = rhs.head;     while (lhsTemp != NULL || rhsTemp != NULL)     {         if (lhsTemp != NULL && rhsTemp == NULL || lhsTemp == NULL && rhsTemp != NULL)             return false;         else if (lhsTemp->data != rhsTemp->data)             return false;         lhsTemp = lhsTemp->next;         rhsTemp = rhsTemp->next;     }     return true; }  template<class T> linkedlist<T>::~linkedlist() {     while (head != NULL)     {         node<T> *tmp = head;         head = head->next;         delete tmp;     }     delete head; }  template<class T> linkedlist<T>::linkedlist(const linkedlist & rhs) : head(NULL) {     *this = rhs; }   template <class T> linkedlist<T> & linkedlist<T>::operator=(const linkedlist<T> &rhs) {     if (this != &rhs)     {         node<T> *temp;         while (head != NULL)         {             temp = head;             head = head->next;             delete temp;         }          if (rhs.head != NULL)             head = new node<T>(rhs.head->data);          node<T> *tmpHead = head;          for (node<T> *tmp = rhs.head->next; tmp != NULL; tmp = tmp->next)         {             tmpHead->next = new node<T>(tmp->data);             tmpHead = tmpHead->next;         }     }     return *this; }  template<class T> void linkedlist<T>::insert(const T data) {     if (head == NULL)     {         head = new node<T>(data);     }     else     {         node<T> *temp = head;         for (temp = head; temp->next != NULL; temp = temp->next);         temp->next = new node<T>(data);     } }  template<class T> bool linkedlist<T>::search(const T data) const {     if (head == NULL)         return false;      for (node<T> *tmp = head; tmp != NULL; tmp = tmp->next)         if (tmp->data == data)             return true;      return true; }  template<class T> void linkedlist<T>::remove(const T data) {     bool removed = false;     node<T> *curr = head;     node<T> *prev = head;      for (; curr != NULL && removed == false; curr = curr->next)     {         if (head->data == data)         {             node<T> *tmp = head;             head = head->next;             delete tmp;             removed = true;         }         else if (curr->data == data)         {             node<T> *tmp = curr;             prev->next = curr->next;             delete tmp;             removed = true;         }         prev = curr;     } }  template<class T> bool linkedlist<T>::isEmpty() const {     return head == NULL; }  template<class T> ostream & operator<<(ostream & os, const linkedlist<T>& rhs) {     for (node<T> *temp = rhs.head; temp != NULL; temp = temp->next)     {         os << temp->data;         if (temp->next != NULL)             os << ", ";     }     return os; }   
Original en ingles

My implementation is only for study purposes, I agree that some of the features may be counter-intuitive.

I guess the best method is to use a list in the STL library.

Any improvements will be greatly appreciated.

The following code compiles and works, If possible I would like the code reviewed in C++98, If not the closest to him which is C++03;

#include <iostream> using namespace std;  template <class T> struct node {     node(T data) : data(data), next(NULL) {}     T data;     node<T> *next; };  template <class T> class linkedlist {     template<class U>     friend ostream &operator<<(ostream &os, const linkedlist<U> &rhs); private:     node<T> *head; public:     linkedlist() : head(NULL) {};     ~linkedlist();     linkedlist(const linkedlist &rhs);     linkedlist &operator=(const linkedlist &rhs);     void insert(const T data);     bool search(const T data) const;     void remove(const T data);     bool isEmpty() const;     bool operator==(const linkedlist<T> &rhs) const;     bool operator!=(const linkedlist<T> &rhs) const;     bool operator<(const linkedlist<T> &rhs) const;     bool operator>(const linkedlist<T> &rhs) const; };  template <class T> bool linkedlist<T>::operator!=(const linkedlist<T> &rhs) const {     return !(*this == rhs); }  template<class T> bool linkedlist<T>::operator<(const linkedlist<T>& rhs) const {     node<T> *lhsTemp = head;     node<T> *rhsTemp = rhs.head;     while (lhsTemp != NULL && rhsTemp != NULL)     {         if (lhsTemp->data > rhsTemp->data)             return false;         lhsTemp = lhsTemp->next;         rhsTemp = rhsTemp->next;     }     return true; }  template<class T> bool linkedlist<T>::operator>(const linkedlist<T>& rhs) const {     return rhs < *this; }  template <class T> bool linkedlist<T>::operator==(const linkedlist<T> &rhs) const {     node<T> *lhsTemp = head;     node<T> *rhsTemp = rhs.head;     while (lhsTemp != NULL || rhsTemp != NULL)     {         if (lhsTemp != NULL && rhsTemp == NULL || lhsTemp == NULL && rhsTemp != NULL)             return false;         else if (lhsTemp->data != rhsTemp->data)             return false;         lhsTemp = lhsTemp->next;         rhsTemp = rhsTemp->next;     }     return true; }  template<class T> linkedlist<T>::~linkedlist() {     while (head != NULL)     {         node<T> *tmp = head;         head = head->next;         delete tmp;     }     delete head; }  template<class T> linkedlist<T>::linkedlist(const linkedlist & rhs) : head(NULL) {     *this = rhs; }   template <class T> linkedlist<T> & linkedlist<T>::operator=(const linkedlist<T> &rhs) {     if (this != &rhs)     {         node<T> *temp;         while (head != NULL)         {             temp = head;             head = head->next;             delete temp;         }          if (rhs.head != NULL)             head = new node<T>(rhs.head->data);          node<T> *tmpHead = head;          for (node<T> *tmp = rhs.head->next; tmp != NULL; tmp = tmp->next)         {             tmpHead->next = new node<T>(tmp->data);             tmpHead = tmpHead->next;         }     }     return *this; }  template<class T> void linkedlist<T>::insert(const T data) {     if (head == NULL)     {         head = new node<T>(data);     }     else     {         node<T> *temp = head;         for (temp = head; temp->next != NULL; temp = temp->next);         temp->next = new node<T>(data);     } }  template<class T> bool linkedlist<T>::search(const T data) const {     if (head == NULL)         return false;      for (node<T> *tmp = head; tmp != NULL; tmp = tmp->next)         if (tmp->data == data)             return true;      return true; }  template<class T> void linkedlist<T>::remove(const T data) {     bool removed = false;     node<T> *curr = head;     node<T> *prev = head;      for (; curr != NULL && removed == false; curr = curr->next)     {         if (head->data == data)         {             node<T> *tmp = head;             head = head->next;             delete tmp;             removed = true;         }         else if (curr->data == data)         {             node<T> *tmp = curr;             prev->next = curr->next;             delete tmp;             removed = true;         }         prev = curr;     } }  template<class T> bool linkedlist<T>::isEmpty() const {     return head == NULL; }  template<class T> ostream & operator<<(ostream & os, const linkedlist<T>& rhs) {     for (node<T> *temp = rhs.head; temp != NULL; temp = temp->next)     {         os << temp->data;         if (temp->next != NULL)             os << ", ";     }     return os; } 
     
         
         

Lista de respuestas

5
 
vote
vote
La mejor respuesta
 

nunca use push9 en un encabezado. Mientras que Array0 es ya considerado mala práctica en general , es especialmente malo en un archivo de encabezado. Afecta a cada archivo que incluye su encabezado.

Siguiente, Ocultar tu < Código> Array1 . Es un detalle de implementación. Puede colocarlo en un espacio de nombres Array22 , dentro de su clase , o en otro encabezado. Pero no debería estar fácilmente disponible para un usuario final.

Además, usted tiene una convención de nombramiento inconsistente. Sus variables están escritas en Camelcase, sus métodos están escritos en camellas, pero su clase es solo 99887776655443324 . El tamaño de la muestra es demasiado pequeño para ver cómo desea nombrar sus métodos. Sin embargo, Array5 es más difícil de leer que Array6 , Array7 o unshift28 .

Es genial que implementó Array9 En términos de y unshift31 En términos de unshift2 . ¡Excelente manera de reducir el código duplicado! Pero ¿por qué detenerse allí? Usted ha duplicado su código en varios otros lugares. Por ejemplo, borrar la lista se realiza en ambos unshift3 y unshift4 . Proporcionar una función 9988777665544333554443335 , por ejemplo.

  unshift6  

Por cierto, ¿ese unshift7 ? Eso es algo que definitivamente podría agregar a su clase por su propia conveniencia:

  unshift8  

Mientras lo estamos en ello, debe ser Muy cuidadoso en los métodos unshift9 . Aún puede cambiar accidentalmente su lista:

  push0  

Su código no tiene ese error en lo que puedo ver, pero puede mantenerlo seguro usando push1 Más a menudo:

  push2  

Y mientras estamos en esos operadores, debe verificar si ambas partes son las mismas. De esa manera, usted puede reducir la operación:

  push3  

Puede usar el mismo método en push4 .

Errores

Tu código tiene varios errores. Algunos de ellos evitarán que su código compilado, algunos de ellos llevarán a un comportamiento indefinido.

Errores durante la compilación

Comencemos con los errores del compilador. Aquí está la parte que debe recordar: cuando usa una plantilla, el compilador solo instaneará los métodos si realmente los usa. Por ejemplo, su función push555443345 no compila, ya que su firma usa push6 , aunque devuelve un push7 :

 plantilla  void  Linkedlist :: Búsqueda (Const T Datos) Const {     if (head == null)         return  falso ;      para (nodo * tmp = cabeza; tmp! = null; tmp = tmp- & gt; Siguiente)         if (tmp- & gt; data == data)             return  verdadero ;      retorno  verdadero ; } 

que no compilará. O su compilador debe gritarle, pero no quiere. Hacer suire que habilitas advertencias.

Comportamiento indefinido

En push8 , su push9 bucle no debe ejecutar si 99887766555443350 está vacío:

  pop1  

Además, tiene una pequeña función para verificar si una lista está vacía. Úsalo. Y pop2 es algo engañoso. No tienes una cabeza temporal, tienes un último elemento o cola temporal. Pero como nos centramos en un solo nodo a la vez, lo llamamos pop3 :

  pop4  

Por cierto, ¿por qué es una mala idea en este momento usar pop5 , aunque hace que su código sea mucho más fácil?

  pop6  

Esto es mucho más fácil de leer, y puede verificar fácilmente que sea correcto. Pero, ¿por qué es una mala idea en este momento? ¿Y qué puedes hacer para cambiar eso?

más sobre eso en la última sección de la revisión. Por cierto, pop7 es

  pop8  

Tenemos que definirlo de esa manera, porque

  pop9  

que significaría que su puntero es constante, pero no el valor que apunta.

mejoras adicionales

su shift0 es Un poco de complejo. No tenga miedo de simplemente shift1 cuando haya terminado con el trabajo. Y mueva las condiciones que deben revisarse una sola vez de un bucle:

  shift2  

La función realmente no se puso más corta, pero ahora es más fácil razonar sobre su comportamiento.

Ahora es el momento de hablar de shift3 . Tuviste sobre una página de pantalla para pensarlo, lo cual no es mucho tiempo, lo siento. Pero, ¿cuál es el problema actual? ¿Por qué es una mala idea usarlo en shift4 ?

Porque tienes que atravesar toda la lista para cada inserción. Esto cambiaría su 9988776665554433655 desde $ $ MATHCAL O (N) $ a $ MATHCAL O (N ^ 2) $. Entonces, ¿cómo podrías arreglar esto? Es un poco fácil: Tienes que recordar no solo el primero, sino también el último elemento de la lista. Un shift6 .

Tenga en cuenta que esto hará todas las funciones que eliminan los elementos más torpe. Sus trabajos de implementación actuales, pero si desea tener un $ Mathcal O (1) $ shift7 , realmente necesita otro puntero en su shift8 .

Otros comentarios

Su implementación está bien, pero es. Hm. No es muy útil. Solo puede insertar cosas en su lista, y puede verificar si algo está ahí (y retírelo). Las siguientes funciones al menos ayudarían a acceder a algunos elementos :

  • shift9 para el primer elemento
  • unshift0 para eliminar el primer elemento
  • unshift1 Para el último elemento (solo si ha agregado unshift2 arriba).

y por último, pero no menos importante, su comentario sobre STL:

Supongo que el mejor método es usar una lista en la biblioteca STL.

si. Por lo general, es una buena idea usar lo que ya está allí. Sin embargo, su unshift3 tiene una sola función para agregar elementos al final. Si solo agrega elementos al final, use unshift4 . No unshift5 . Usted solo quiere usar unshift6 Si necesita insertar en el centro de la lista con mucha frecuencia. Pero unshift7 no es realmente amigable con caché. Depende de lo que quieras hacer con tu contenedor. Consulte este punto de referencia para obtener más información .

 

Never use using namespace std in a header. While using namespace std is already considered bad practice in general, it's especially evil in a header file. It affects every file that includes your header.

Next, hide your node. It's an implementation detail. You can put it in a detail namespace, inside your linkedlist class, or in another header. But it shouldn't be readily available to an end-user.

Furthermore, you have an inconsistent naming convention. Your variables are written in camelCase, your methods are written in camelCase, but your class is just linkedlist. The sample size is too small to see how you want to name your methods. However, linkedlist is harder to read than LinkedList, linkedList or linked_list.

It's great that you implemented > in terms of < and != in terms of ==. Great way to reduce duplicate code! But why stop there? You have duplicated your code in several other places. For example clearing the list is done in both operator= and ~linkedlist(). Provide a clear() function, e.g.

void clear () {     while(head != NULL) {         node_ptr tmp = head->next;         delete head;         head = tmp;     } } 

By the way, that node_type? That's something you could definitely add to your class for your own convenience:

typedef node<T> node_type; typedef node_type* node_ptr; 

While we're at it, you have to be very careful in those const methods. You can still accidentally change your list:

head->data = T(); // compiles fine 

Your code doesn't have that error as far as I can see, but you can keep it safe by using const more often:

template <class T> bool linkedlist<T>::operator==(const linkedlist<T> &rhs) const { //vvvvv     const node<T> *lhsTemp = head;     const node<T> *rhsTemp = rhs.head;     while (lhsTemp != NULL && rhsTemp != NULL)     {         if (lhsTemp->data != rhsTemp->data)             return false;         lhsTemp = lhsTemp->next;         rhsTemp = rhsTemp->next;     }     return (lhsTemp == NULL) && (rhsTemp == NULL); } 

And while we're in those operators, you should check whether both sides are the same. That way you can short-cut the operation:

template <class T> bool linkedlist<T>::operator==(const linkedlist<T> &rhs) const {     if(this == &rhs) {         return true;     }      // other function as above         } 

You can use the same method in operator<.

Errors

Your code has several errors. Some of them will prevent your code from compiling, some of them will lead to undefined behaviour.

Errors during compilation

Let's start with the compiler errors. Here's the part you should remember: whenenver you use a template, the compiler will only instantiate the methods if you actually use them. For example your search function does not compile, since its signature uses void, although it returns a bool:

template void linkedlist::search(const T data) const {     if (head == NULL)         return false;      for (node *tmp = head; tmp != NULL; tmp = tmp->next)         if (tmp->data == data)             return true;      return true; }

That won't compile. Or your compiler should yell at you, but it doesn't want to. Make suire that you enable warnings.

Undefined behaviour

In operator=, your for loop must not run if rhs is empty:

template <class T> linkedlist<T> & linkedlist<T>::operator=(const linkedlist<T> &rhs) {     if (this != &rhs)     {         // ... cut          // let's say rhs.head == NULL          // undefined behaviour, since rhs.head does not point         // to something valid.         for (node<T> *tmp = rhs.head->next; tmp != NULL; tmp = tmp->next)         {             tmpHead->next = new node<T>(tmp->data);             tmpHead = tmpHead->next;         }     }     return *this; } 

Also, you have a nice little function to check whether a list is empty. Use it. And tmpHead is somewhat misleading. You don't have a temporary head, you have a temporary last element or tail. But since we focus on only one node at a time, let's call it current:

template <class T> linkedlist<T> & linkedlist<T>::operator=(const linkedlist<T> &rhs) {     if (this != &rhs)     {         clear(); // the function at the start of this review          if(rhs.isEmpty()) {             // short cut, since the other list is empty             return *this;         }          head = new node<T>(rhs.head->data);          node<T> * current = head;          for (node<T> *tmp = rhs.head->next; tmp != NULL; tmp = tmp->next)         {             current->next = new node<T>(tmp->data);             current = current->next;         }     }     return *this; } 

By the way, why is it a bad idea at the moment to use insert, although it makes your code a lot easier?

template <class T> linkedlist<T> & linkedlist<T>::operator=(const linkedlist<T> &rhs) {     if (this != &rhs)     {         clear(); // the function at the start of this review          for(const_node_ptr tmp = rhs.head; tmp != NULL; tmp = tmp->next)         {             insert(tmp->data);         }     }     return *this; } 

This is a lot easier to read, and you can easily check that it's correct. But why is it a bad idea at the moment? And what can you do to change that?

More on that in the last section of the review. By the way, const_node_ptr is

typedef const node_type * const_node_ptr 

We have to define it that way, because

const node_ptr == node_type * const 

which would mean that your pointer is constant, but not the value it points to.

Further improvements

Your remove is a tad to complex. Don't be afraid to simply return when you're done with the job. And move conditions that should be checked once out of a loop:

template<class T> void linkedlist<T>::remove(const T data) {     if(isEmpty())     {         return;     }      if (head->data == data)     {         node<T> * tmp = head;         head = head->next;         delete tmp;          return;     }      for (node_ptr curr = head->next, prev = head; curr != NULL; curr = curr->next)     {         if (curr->data == data)         {             node<T> *tmp = curr;             prev->next = curr->next;             delete tmp;              return;         }         prev = curr;     } } 

The function didn't really get shorter, but it's now easier to reason about its behaviour.

Now it's time to talk about insert. You had about a screen page to think about it, which isn't really much time, sorry. But what's the current problem? Why is it a bad idea to use it in operator=?

Because you have to traverse the whole list for every insertion. This would change your current operator= from \$\mathcal O(n)\$ to \$\mathcal O(n^2)\$. So how could you fix this? It's somewhat easy: You have to remember not only the first, but also the last element of the list. A tail.

Note that this will make all functions that remove elements more awkward. Your current implementation works, but if you want to have an \$\mathcal O(1)\$ insert, you really need another pointer in your linkedlist.

Further remarks

Your implementation is fine, but it is. Hm. Not very helpful. You can only insert things into your list, and you can check whether something is in there (and remove it). The following functions would at least help to access some elements:

  • front() for the first element
  • removeFirst() to remove the first element
  • back() for the last element (only if you've added tail above).

And last but not least, your remark about STL:

I guess the best method is to use a list in the STL library.

Yes. It's usually a good idea to use what's already there. However, your linkedlist has only one function to add elements at the end. If you only add elements at the end, use std::vector. Not std::list. You only want to use std::list if you need to insert in the middle of the list very often. But std::list isn't really cache friendly. It depends on what you want to do with your container. See this benchmark for more information.

 
 
   
   

Relacionados problema

3  Lista doblemente vinculada en óxido usando los punteros crudos  ( Doubly linked list in rust using raw pointers ) 
Estoy practicando la oxidación escribiendo una lista doblemente vinculada usando los punteros crudos, 9988776655544330 Para asignar datos en el montón, 998...

7  Simulando una lista enlazada lineal usando una matriz  ( Simulating a linear linked list using an array ) 
Un programa para simular una lista enlazada lineal usando una matriz: Especificaciones: A Y: cree un nuevo nodo con el valor de datos y, y agregue este...

5  Cola de bloqueo con la exactitud de la lista doblemente vinculada  ( Lock free queue with doubly linked list correctness ) 
Necesito una cola de bloqueo que se implementa mediante la lista doblemente vinculada. es mi código correcto? ¿Hay algún error? ¿Hay alguna mejoras a realiz...

1  DEQUEUE () en la implementación de la cola que utiliza una lista circular vinculada  ( Dequeue in queue implememtation that uses a circular linked list ) 
Utilizo una lista de enlaces circulares para implementar un queue , y solo sostiene un 99887776665544332 (Tenga en cuenta que 99887776655443333 enlaces a...

4  ADT Pila con Linkedlist  ( Adt stack with linkedlist ) 
Actualmente estoy preparando para mi examen y estoy tratando de implementar algunos tipos de datos abstractos con listas vinculadas como preparación para el e...

10  Lista vinculada de objetos de conejito  ( Linked list of bunny objects ) 
El ejercicio es el ejercicio de la lista de conejitos vinculados; El último ejercicio para principiantes de aquí . Estoy buscando comentarios sobre absolut...

4  Eliminar nodos alternativos de una lista vinculada  ( Delete alternate nodes of a linked list ) 
Si la lista vinculada es 1- & gt; 2- & gt; 3- & gt; 4 entonces la salida debe ser 1- & gt; 3. Si la lista vinculada es 1- & gt; 2- & gt; 3- & gt; 4- & gt; 5,...

0  Agregando dos números extremadamente grandes usando una estructura de datos personalizada  ( Adding two extremely large numbers using a custom data structure ) 
Tengo una implementación para agregar 2 números extremadamente grandes, mayor que el techo proporcionado por long , por ejemplo, 1238913893838383813813813813...

14  Implementando una lista relacionada adecuada para un entorno profesional  ( Implementing a proper linked list for a professional environment ) 
Tengo algunas preocupaciones: ¿Es normal que la clase tenga al menos un nodo? En otras palabras, esta implementación no puede tener una lista vinculada va...

5  Destructor para una lista vinculada  ( Destructor for a linked list ) 
El código completo se encuentra aquí: https://gist.github.com/4521540 < / p> Es un maniquí List en C ++. Mi preocupación es para liberar la memoria. No s...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos