¿Por qué las listas enlazadas usan punteros en lugar de almacenar nodos dentro de nodos?

121

He trabajado con listas vinculadas anteriormente en Java, pero soy muy nuevo en C ++. Estaba usando esta clase de nodo que me fue dada en un proyecto muy bien

class Node
{
  public:
   Node(int data);

   int m_data;
   Node *m_next;
};

pero tenía una pregunta que no fue respondida muy bien. ¿Por qué es necesario usar

Node *m_next;

para apuntar al siguiente nodo en la lista en lugar de

Node m_next;

Entiendo que es mejor usar la versión de puntero; No voy a discutir hechos, pero no sé por qué es mejor. Obtuve una respuesta no tan clara sobre cómo el puntero es mejor para la asignación de memoria, y me preguntaba si alguien aquí podría ayudarme a comprenderlo mejor.

c++ pointers linked-list m0meni
fuente
14
@self Disculpe? ¿Por qué un lenguaje donde todo es un puntero no tiene listas vinculadas?
Angew ya no está orgulloso de SO
41
Es importante tener en cuenta cómo C y C ++ son distintos de Java en términos de punteros de objetos frente a referencias. Node m_nextno es una referencia a un nodo, es almacenamiento para todo el Nodemismo.
Brian Cain
41
@self Java tiene punteros que simplemente no los usas explícitamente.
m0meni
27
Tortugas todo el camino es no una opción. La locura tiene que terminar en alguna parte.
WhozCraig
26
Olvida todo lo que sabes sobre Java. C ++ y Java manejan la memoria de maneras fundamentalmente diferentes. Ve a ver esta pregunta para las recomendaciones de libros, elige una y léela. Nos harás un gran favor a todos.
Rob K

Respuestas:

218

No es solo mejor, es la única forma posible.

Si almacenaras un Node objeto dentro de sí mismo, ¿cuál sería sizeof(Node)? Sería sizeof(int) + sizeof(Node), que sería igual a sizeof(int) + (sizeof(int) + sizeof(Node)), que sería igual a sizeof(int) + (sizeof(int) + (sizeof(int) + sizeof(Node))), etc., al infinito.

Un objeto como ese no puede existir. Es imposible .

emlai
fuente
25
* A menos que se evalúe perezosamente. Las listas infinitas son posibles, solo que no con una evaluación estricta.
Carcigenicate
55
@Carcigenicate no se trata de evaluar / ejecutar alguna función en el objeto Node, se trata del diseño de memoria de cada instancia de Node, que debe determinarse en el momento de la compilación, antes de que pueda ocurrir cualquier evaluación.
Peteris
66
@DavidK Es lógicamente imposible hacer esto. Usted necesita un puntero (bueno en realidad una vía indirecta) aquí - de que el lenguaje puede esconderla de usted, pero al final, no hay forma de evitar eso.
Voo
2
@David estoy confundido. Primero, ¿estás de acuerdo en que es lógicamente imposible, pero luego quieres contemplarlo? Elimine cualquier cosa de C o C ++: es imposible en cualquier lenguaje que pueda imaginar hasta donde puedo ver. Esa estructura es, por definición, una recursión infinita y sin algún nivel de indirección no podemos romper eso.
Voo
13
@benjamin En realidad señalé (porque sabía que de lo contrario alguien mencionaría esto, bueno, no ayudó) que Haskell asignó los thunks en el momento de la creación y, por lo tanto, esto funciona porque esos thunks nos dan la indirecta que necesitamos. Esto no es más que un puntero con datos adicionales disfrazados ...
Voo
178

En java 

Node m_node

almacena un puntero a otro nodo. No tienes elección al respecto. En C ++

Node *m_node

significa lo mismo. La diferencia es que en C ++ puede almacenar el objeto en lugar de un puntero. Es por eso que tienes que decir que quieres un puntero. En C ++:

Node m_node

significa almacenar el nodo aquí (y eso claramente no puede funcionar para una lista; terminas con una estructura definida recursivamente).

pm100
fuente
2
@SalmanA Ya lo sabía. Solo quería saber por qué no funcionaría sin un puntero, que es lo que la respuesta aceptada explicó mucho mejor.
m0meni
3
@ AR7 Ambos están dando una especie de misma explicación, bajo dos enfoques diferentes. Si lo declaraste como una variable "regular", entonces la primera vez que se llamó a un constructor, lo instanciaría a una nueva instancia. Pero antes de que termine de instanciarlo, antes de que termine el constructor del primero Node, se llamaría al propio constructor del miembro , lo que crearía una instancia de otra nueva instancia ... y obtendría una pseudo-recursión interminable. No es realmente un problema de tamaño en términos completamente estrictos y literales, ya que es un problema de rendimiento.
Panzercrisis
Pero todo lo que realmente deseas es solo una forma de señalar a la siguiente en la lista, no una Nodeque esté realmente dentro de la primera Node. Entonces crea un puntero, que es esencialmente cómo Java maneja los objetos, en lugar de las primitivas. Cuando llama a un método o crea una variable, Java no almacena una copia del objeto o incluso el objeto en sí; almacena una referencia a un objeto, que es esencialmente un puntero con un poco de guante para niños envuelto alrededor. Esto es lo que ambas respuestas están diciendo esencialmente.
Panzercrisis
no es un problema de tamaño o velocidad, es un problema de imposibilidad. El objeto Node incluido incluiría un objeto Node que incluiría un objeto Node ... De hecho, es imposible compilarlo
pm100
3
@ Panzercrisis Soy consciente de que ambos están dando la misma explicación. Sin embargo, este enfoque no fue tan útil para mí porque se centró en lo que ya entendía: cómo funcionan los punteros en C ++ y cómo se manejan los punteros en Java. La respuesta aceptada abordó específicamente por qué no usar un puntero sería imposible porque no se puede calcular el tamaño. Por otro lado, este lo dejó más vagamente como "una estructura definida recursivamente". PD: su explicación que acaba de escribir lo explica mejor que ambas: D.
m0meni
38

C ++ no es Java. Cuando escribes

Node m_next;

en Java, eso es lo mismo que escribir

Node* m_next;

en C ++. En Java, el puntero es implícito, en C ++ es explícito. Si tú escribes

Node m_next;

en C ++, coloca una instancia de Nodeallí dentro del objeto que está definiendo. Siempre está ahí y no se puede omitir, no se puede asignar newy no se puede eliminar. Este efecto es imposible de lograr en Java, y es totalmente diferente de lo que Java hace con la misma sintaxis.

cmaster - restablecer monica
fuente
1
Para obtener algo similar en Java probablemente sería "extiende" si SuperNode extiende Nodo, SuperNodes incluye todos los Atributos de Nodo y tiene que reservar todo el espacio adicional. Entonces en Java no puedes hacer "Nodo extiende Nodo"
Falco
@Falco True, la herencia es una forma de inclusión en el lugar de las clases base. Sin embargo, dado que Java no permite la herencia múltiple (a diferencia de C ++), solo puede obtener una instancia de otra clase preexistente a través de la herencia. Es por eso que no pensaría en la herencia como un sustituto de la inclusión de miembros en el lugar.
cmaster - reinstalar a monica el
27

Utiliza un puntero, de lo contrario su código:

class Node
{
   //etc
   Node m_next; //non-pointer
};

... no se compilaría, ya que el compilador no puede calcular el tamaño de Node. Esto se debe a que depende de sí mismo, lo que significa que el compilador no puede decidir cuánta memoria consumiría.

Nawaz
fuente
55
Peor aún, no existe un tamaño válido: si se k == sizeof(Node)mantiene y su tipo tiene datos, también tendría que mantener eso sizeof(Node) = k + sizeof(Data) = sizeof(Node) + sizeof(Data)y luego sizeof(Node) > sizeof(Node).
bitmask
44
@bitmask no existe un tamaño válido en los números reales . Si permite transinfinitos, aleph_0funciona. (Solo siendo demasiado pedante :-))
k_g
2
@k_g Bueno, el estándar C / C ++ exige que el valor de retorno de sizeofsea ​​un tipo integral sin signo, por lo que existe la esperanza de tamaños transfinitos o incluso reales. (siendo incluso más pedante: p!)
Thomas
@Thomas: Uno incluso podría señalar que incluso van los Números Naturales. (Repasar la cima pedante: p)
bitmask
1
De hecho, Nodeni siquiera se define antes del final de este fragmento, por lo que realmente no puede usarlo en su interior. Permitir que uno declare implícitamente punteros a una clase aún no declarada es un pequeño truco permitido por el lenguaje para hacer posibles tales estructuras, sin la necesidad de emitir punteros explícitamente todo el tiempo.
osa
13

Este último ( Node m_next) debería contener el nodo. No lo señalaría. Y entonces no habría vinculación de elementos.

wallyk
fuente
3
Peor aún, sería lógicamente imposible que un objeto contenga algo del mismo tipo.
Mike Seymour
¿No seguiría técnicamente vinculando porque sería un nodo que contiene un nodo que contiene un nodo y así sucesivamente?
m0meni
9
@ AR7: No, la contención significa que está literalmente dentro del objeto, no vinculado a él.
Mike Seymour
9

El enfoque que usted describe es compatible no sólo con C ++, pero también con su (en su mayoría) lengua subgrupo C . Aprender a desarrollar una lista vinculada de estilo C es una buena manera de presentarse a las técnicas de programación de bajo nivel (como la administración manual de memoria), pero generalmente no es una práctica recomendada para el desarrollo moderno de C ++.

A continuación, he implementado cuatro variaciones sobre cómo administrar una lista de elementos en C ++.

  1. raw_pointer_demoutiliza el mismo enfoque que el suyo: se requiere la gestión manual de la memoria con el uso de punteros sin formato. El uso de C ++ aquí es solo para azúcar sintáctico , y el enfoque utilizado es compatible con el lenguaje C.
  2. En shared_pointer_demola lista, la administración todavía se realiza manualmente, pero la administración de la memoria es automática (no utiliza punteros sin formato). Esto es muy similar a lo que probablemente haya experimentado con Java.
  3. std_list_demousa el listcontenedor de biblioteca estándar . Esto muestra cuánto más fácil se vuelven las cosas si confía en las bibliotecas existentes en lugar de crear las suyas propias.
  4. std_vector_demousa el vectorcontenedor de biblioteca estándar . Esto gestiona el almacenamiento de la lista en una única asignación de memoria contigua. En otras palabras, no hay punteros a elementos individuales. Para ciertos casos bastante extremos, esto puede volverse significativamente ineficiente. Sin embargo, en casos típicos, esta es la mejor práctica recomendada para la gestión de listas en C ++ .

De nota: De todos estos, solo el raw_pointer_demorealmente requiere que la lista se destruya explícitamente para evitar la "pérdida" de memoria. Los otros tres métodos destruirían automáticamente la lista y su contenido cuando el contenedor se salga del alcance (al finalizar la función). El punto es: C ++ es capaz de ser muy "similar a Java" a este respecto, pero solo si elige desarrollar su programa utilizando las herramientas de alto nivel a su disposición.

/*BINFMTCXX: -Wall -Werror -std=c++11
*/

#include <iostream>
#include <algorithm>
#include <string>
#include <list>
#include <vector>
#include <memory>
using std::cerr;
/** Brief   Create a list, show it, then destroy it */
void raw_pointer_demo()
{
    cerr << "\n" << "raw_pointer_demo()..." << "\n";

    struct Node
    {
        Node(int data, Node *next) : data(data), next(next) {}
        int data;
        Node *next;
    };

    Node * items = 0;
    items = new Node(1,items);
    items = new Node(7,items);
    items = new Node(3,items);
    items = new Node(9,items);

    for (Node *i = items; i != 0; i = i->next)
        cerr << (i==items?"":", ") << i->data;
    cerr << "\n";

    // Erase the entire list
    while (items) {
        Node *temp = items;
        items = items->next;
        delete temp;
    }
}
raw_pointer_demo()...
9, 3, 7, 1
/** Brief   Create a list, show it, then destroy it */
void shared_pointer_demo()
{
    cerr << "\n" << "shared_pointer_demo()..." << "\n";

    struct Node; // Forward declaration of 'Node' required for typedef
    typedef std::shared_ptr<Node> Node_reference;

    struct Node
    {
        Node(int data, std::shared_ptr<Node> next ) : data(data), next(next) {}
        int data;
        Node_reference next;
    };

    Node_reference items = 0;
    items.reset( new Node(1,items) );
    items.reset( new Node(7,items) );
    items.reset( new Node(3,items) );
    items.reset( new Node(9,items) );

    for (Node_reference i = items; i != 0; i = i->next)
        cerr << (i==items?"":", ") << i->data;
    cerr<<"\n";

    // Erase the entire list
    while (items)
        items = items->next;
}
shared_pointer_demo()...
9, 3, 7, 1
/** Brief   Show the contents of a standard container */
template< typename C >
void show(std::string const & msg, C const & container)
{
    cerr << msg;
    bool first = true;
    for ( int i : container )
        cerr << (first?" ":", ") << i, first = false;
    cerr<<"\n";
}
/** Brief  Create a list, manipulate it, then destroy it */
void std_list_demo()
{
    cerr << "\n" << "std_list_demo()..." << "\n";

    // Initial list of integers
    std::list<int> items = { 9, 3, 7, 1 };
    show( "A: ", items );

    // Insert '8' before '3'
    items.insert(std::find( items.begin(), items.end(), 3), 8);
    show("B: ", items);

    // Sort the list
    items.sort();
    show( "C: ", items);

    // Erase '7'
    items.erase(std::find(items.begin(), items.end(), 7));
    show("D: ", items);

    // Erase the entire list
    items.clear();
    show("E: ", items);
}
std_list_demo()...
A:  9, 3, 7, 1
B:  9, 8, 3, 7, 1
C:  1, 3, 7, 8, 9
D:  1, 3, 8, 9
E:
/** brief  Create a list, manipulate it, then destroy it */
void std_vector_demo()
{
    cerr << "\n" << "std_vector_demo()..." << "\n";

    // Initial list of integers
    std::vector<int> items = { 9, 3, 7, 1 };
    show( "A: ", items );

    // Insert '8' before '3'
    items.insert(std::find(items.begin(), items.end(), 3), 8);
    show( "B: ", items );

    // Sort the list
    sort(items.begin(), items.end());
    show("C: ", items);

    // Erase '7'
    items.erase( std::find( items.begin(), items.end(), 7 ) );
    show("D: ", items);

    // Erase the entire list
    items.clear();
    show("E: ", items);
}
std_vector_demo()...
A:  9, 3, 7, 1
B:  9, 8, 3, 7, 1
C:  1, 3, 7, 8, 9
D:  1, 3, 8, 9
E:
int main()
{
    raw_pointer_demo();
    shared_pointer_demo();
    std_list_demo();
    std_vector_demo();
}
Brent Bradburn
fuente
La Node_referencedeclaración anterior aborda una de las diferencias de nivel de lenguaje más interesantes entre Java y C ++. En Java, declarar un objeto de tipo Nodeimplícitamente usaría una referencia a un objeto asignado por separado. En C ++, tiene la opción de asignación de referencia (puntero) versus asignación directa (pila), por lo que debe manejar la distinción explícitamente. En la mayoría de los casos, usaría la asignación directa, aunque no para los elementos de la lista.
Brent Bradburn
No sé por qué no recomendé también la posibilidad de un std :: deque .
Brent Bradburn
8

Visión general

Hay 2 formas de referenciar y asignar objetos en C ++, mientras que en Java solo hay una.

Para explicar esto, los siguientes diagramas muestran cómo se almacenan los objetos en la memoria.

1.1 Elementos de C ++ sin punteros

class AddressClass
{
  public:
    int      Code;
    char[50] Street;
    char[10] Number;
    char[50] POBox;
    char[50] City;
    char[50] State;
    char[50] Country;
};

class CustomerClass
{
  public:
    int          Code;
    char[50]     FirstName;
    char[50]     LastName;
    // "Address" IS NOT A pointer !!!
    AddressClass Address;
};

int main(...)
{
   CustomerClass MyCustomer();
     MyCustomer.Code = 1;
     strcpy(MyCustomer.FirstName, "John");
     strcpy(MyCustomer.LastName, "Doe");
     MyCustomer.Address.Code = 2;
     strcpy(MyCustomer.Address.Street, "Blue River");
     strcpy(MyCustomer.Address.Number, "2231 A");

   return 0;
} // int main (...)

.......................................
..+---------------------------------+..
..|          AddressClass           |..
..+---------------------------------+..
..| [+] int:      Code              |..
..| [+] char[50]: Street            |..
..| [+] char[10]: Number            |..
..| [+] char[50]: POBox             |..
..| [+] char[50]: City              |..
..| [+] char[50]: State             |..
..| [+] char[50]: Country           |..
..+---------------------------------+..
.......................................
..+---------------------------------+..
..|          CustomerClass          |..
..+---------------------------------+..
..| [+] int:      Code              |..
..| [+] char[50]: FirstName         |..
..| [+] char[50]: LastName          |..
..+---------------------------------+..
..| [+] AddressClass: Address       |..
..| +-----------------------------+ |..
..| | [+] int:      Code          | |..
..| | [+] char[50]: Street        | |..
..| | [+] char[10]: Number        | |..
..| | [+] char[50]: POBox         | |..
..| | [+] char[50]: City          | |..
..| | [+] char[50]: State         | |..
..| | [+] char[50]: Country       | |..
..| +-----------------------------+ |..
..+---------------------------------+..
.......................................

Advertencia : la sintaxis de C ++ utilizada en este ejemplo es similar a la sintaxis de Java. Pero, la asignación de memoria es diferente.

1.2 Elementos de C ++ que utilizan punteros

class AddressClass
{
  public:
    int      Code;
    char[50] Street;
    char[10] Number;
    char[50] POBox;
    char[50] City;
    char[50] State;
    char[50] Country;
};

class CustomerClass
{
  public:
    int           Code;
    char[50]      FirstName;
    char[50]      LastName;
    // "Address" IS A pointer !!!
    AddressClass* Address;
};

.......................................
..+-----------------------------+......
..|        AddressClass         +<--+..
..+-----------------------------+...|..
..| [+] int:      Code          |...|..
..| [+] char[50]: Street        |...|..
..| [+] char[10]: Number        |...|..
..| [+] char[50]: POBox         |...|..
..| [+] char[50]: City          |...|..
..| [+] char[50]: State         |...|..
..| [+] char[50]: Country       |...|..
..+-----------------------------+...|..
....................................|..
..+-----------------------------+...|..
..|         CustomerClass       |...|..
..+-----------------------------+...|..
..| [+] int:      Code          |...|..
..| [+] char[50]: FirstName     |...|..
..| [+] char[50]: LastName      |...|..
..| [+] AddressClass*: Address  +---+..
..+-----------------------------+......
.......................................

int main(...)
{
   CustomerClass* MyCustomer = new CustomerClass();
     MyCustomer->Code = 1;
     strcpy(MyCustomer->FirstName, "John");
     strcpy(MyCustomer->LastName, "Doe");

     AddressClass* MyCustomer->Address = new AddressClass();
     MyCustomer->Address->Code = 2;
     strcpy(MyCustomer->Address->Street, "Blue River");
     strcpy(MyCustomer->Address->Number, "2231 A");

     free MyCustomer->Address();
     free MyCustomer();

   return 0;
} // int main (...)

Si marca la diferencia entre ambas formas, verá que en la primera técnica, el elemento de dirección se asigna dentro del cliente, mientras que en la segunda forma, debe crear cada dirección explícitamente.

Advertencia: Java asigna objetos en la memoria como esta segunda técnica, pero la sintaxis es como la primera forma, lo que puede ser confuso para los recién llegados a "C ++".

Implementación

Entonces, su ejemplo de lista podría ser algo similar al siguiente ejemplo.

class Node
{
  public:
   Node(int data);

   int m_data;
   Node *m_next;
};

.......................................
..+-----------------------------+......
..|            Node             |......
..+-----------------------------+......
..| [+] int:           m_data   |......
..| [+] Node*:         m_next   +---+..
..+-----------------------------+...|..
....................................|..
..+-----------------------------+...|..
..|            Node             +<--+..
..+-----------------------------+......
..| [+] int:           m_data   |......
..| [+] Node*:         m_next   +---+..
..+-----------------------------+...|..
....................................|..
..+-----------------------------+...|..
..|            Node             +<--+..
..+-----------------------------+......
..| [+] int:           m_data   |......
..| [+] Node*:         m_next   +---+..
..+-----------------------------+...|..
....................................v..
...................................[X].
.......................................

Resumen

Como una lista vinculada tiene una cantidad variable de elementos, la memoria se asigna según sea necesario y, según esté disponible.

ACTUALIZAR:

También vale la pena mencionar, como @haccks comentó en su publicación.

Que a veces, referencias o punteros de objetos, indican elementos anidados (también conocido como "Composición UML").

Y a veces, las referencias o punteros de objetos, indican elementos externos (también conocido como "Agregación UML").

Pero los elementos anidados de la misma clase no se pueden aplicar con la técnica "sin puntero".

umlcat
fuente
7

En una nota al margen, si el primer miembro de una clase o estructura es el siguiente puntero (por lo que no hay funciones virtuales o cualquier otra característica de una clase que signifique que el siguiente no es el primer miembro de una clase o estructura), entonces usted puede usar una clase o estructura "base" con solo un puntero siguiente y usar un código común para operaciones básicas de listas vinculadas como agregar, insertar antes, recuperar desde el frente, .... Esto se debe a que C / C ++ garantiza que la dirección del primer miembro de una clase o estructura es la misma que la dirección de la clase o estructura. La clase o estructura del nodo base solo tendría un puntero siguiente para ser utilizado por las funciones básicas de la lista enlazada, luego la conversión de texto se usaría según sea necesario para convertir entre el tipo de nodo base y los tipos de nodo "derivados". Nota al margen: en C ++, si la clase de nodo base solo tiene un siguiente puntero,

rcgldr
fuente
6

¿Por qué es mejor usar punteros en una lista vinculada?

La razón es que cuando crea un Nodeobjeto, el compilador tiene que asignar memoria para ese objeto y para eso se calcula el tamaño del objeto.
El compilador conoce el tamaño del puntero a cualquier tipo y, por lo tanto, con el puntero autorreferencial se puede calcular el tamaño del objeto.

Si Node m_nodese usa en su lugar, entonces el compilador no tiene idea del tamaño de Nodey se atascará en una recursión infinita de cálculo sizeof(Node). Recuerde siempre: una clase no puede contener un miembro de su propio tipo .

hacks
fuente
5

Porque esto en C ++

int main (..)
{
    MyClass myObject;

    // or

    MyClass * myObjectPointer = new MyClass();

    ..
}

es equivalente a esto en Java

public static void main (..)
{
    MyClass myObjectReference = new MyClass();
}

donde ambos crean un nuevo objeto de MyClassusar el constructor predeterminado.

Khaled.K
fuente
0

¿Por qué las listas vinculadas usan punteros en lugar de almacenar nodos dentro de los nodos?

Por supuesto, hay una respuesta trivial.

Si no vincularan un nodo al siguiente mediante un puntero, no serían listas vinculadas .

La existencia de listas vinculadas es porque queremos poder encadenar objetos juntos. Por ejemplo: ya tenemos un objeto de alguna parte. Ahora queremos poner ese objeto real (no una copia) al final de una cola, por ejemplo. Esto se logra al agregar un enlace desde el último elemento que ya está en la cola a la entrada que estamos agregando. En términos de máquina, eso es completar una palabra con la dirección del siguiente elemento.

usuario13784117
fuente