Por que listas vinculadas usam ponteiros em vez de armazenar nós dentro de nós

121

Eu trabalhei com listas vinculadas antes extensivamente em Java, mas sou muito novo em C ++. Eu estava usando essa classe de nó que me foi dada em um projeto muito bem

class Node
{
  public:
   Node(int data);

   int m_data;
   Node *m_next;
};

mas eu tinha uma pergunta que não foi respondida muito bem. Por que é necessário usar

Node *m_next;

para apontar para o próximo nó na lista em vez de

Node m_next;

Eu entendo que é melhor usar a versão do ponteiro; Não vou discutir fatos, mas não sei por que é melhor. Eu recebi uma resposta não tão clara sobre como o ponteiro é melhor para alocação de memória e fiquei pensando se alguém aqui poderia me ajudar a entender isso melhor.

c++ pointers linked-list m0meni
fonte
14
@self Perdoe-me? Por que um idioma em que tudo é um ponteiro não possui listas vinculadas?
Angew não está mais orgulhoso de SO
41
É importante observar como C e C ++ são diferentes de Java em termos de ponteiros de objetos e referências. Node m_nextnão é uma referência a um nó, é armazenamento para o todo em Nodesi.
9789 Brian Cain #
41
@self Java tem ponteiros que você simplesmente não os usa explicitamente.
M0meni 09/04
27
Tartarugas todo o caminho não é uma opção. A loucura tem que terminar em algum lugar.
WhozCraig
26
Por favor, esqueça tudo o que você sabe sobre Java. C ++ e Java tratam a memória de maneiras fundamentalmente diferentes. Vá ver esta pergunta para recomendações de livros, escolha uma e leia-a. Você estará fazendo um grande favor a todos nós.
Rob K

Respostas:

218

Não é apenas melhor, é a única maneira possível.

Se você armazenasse um Node objeto dentro de si, o que seria sizeof(Node)? Seria sizeof(int) + sizeof(Node), o que seria igual sizeof(int) + (sizeof(int) + sizeof(Node)), o que seria igual sizeof(int) + (sizeof(int) + (sizeof(int) + sizeof(Node))), etc. ao infinito.

Um objeto como esse não pode existir. É impossível .

emlai
fonte
25
* A menos que seja avaliado preguiçosamente. Listas infinitas são possíveis, mas não com avaliação rigorosa.
precisa saber é o seguinte
55
@Carcigenicate não se trata de avaliar / executar alguma função no objeto Node - trata-se do layout de memória de todas as instâncias do Node, que devem ser determinadas em tempo de compilação, antes que qualquer avaliação possa ocorrer.
31513 Peteris
6
@DavidK É logicamente impossível fazer isso. Você precisa de um ponteiro (bem, na verdade, um indireto) aqui - com certeza o idioma pode escondê-lo de você, mas no final, não há maneira de contornar isso.
Voo
2
@ David, estou confuso. Primeiro você concorda que é logicamente impossível, mas depois quer contemplá-lo? Remova qualquer coisa de C ou C ++ - é impossível em qualquer idioma que você possa imaginar, tanto quanto eu posso ver. Essa estrutura é por definição uma recursão infinita e sem algum nível de indireção, não podemos quebrá-la.
Voo 10/04
13
@bjamjamin Na verdade, eu apontei (porque sabia que alguém traria isso à tona - bem, não ajudou) que Haskell alocou os thunks no momento da criação e, portanto, isso funciona porque esses thunks nos dão o indireto de que precisamos. Isto não é senão um ponteiro com dados extras em disfarçar ...
Voo
178

Em Java 

Node m_node

armazena um ponteiro para outro nó. Você não tem escolha. Em C ++

Node *m_node

significa a mesma coisa. A diferença é que, em C ++, você pode realmente armazenar o objeto em oposição a um ponteiro para ele. É por isso que você tem que dizer que deseja um ponteiro. Em C ++:

Node m_node

significa armazenar o nó aqui (e isso claramente não pode funcionar para uma lista - você acaba com uma estrutura definida recursivamente).

pm100
fonte
2
@ SalmanA Eu já sabia disso. Eu só queria saber por que não funcionaria sem um ponteiro, o que a resposta aceita explicou muito melhor.
M0meni
3
@ AR7 Ambos estão dando o mesmo tipo de explicação, sob duas abordagens diferentes. Se você a declarasse como uma variável "regular", na primeira vez em que um construtor fosse chamado, isso seria instanciado para uma nova instância. Mas antes que termine de instancia-lo - antes que o construtor do primeiro seja terminado - o construtor do membro Nodeseria chamado, o que instanciaria outra nova instância ... e você obteria pseudo-recursão interminável. Não é realmente uma questão de tamanho em termos completamente estritos e literais, pois é uma questão de desempenho.
Panzercrisis
Mas tudo o que você realmente quer é apenas uma maneira de apontar para a próxima na lista, não a Nodeque está realmente dentro da primeira Node. Então, você cria um ponteiro, que é essencialmente como o Java lida com objetos, em vez de primitivos. Quando você chama um método ou cria uma variável, o Java não armazena uma cópia do objeto ou mesmo do próprio objeto; ele armazena uma referência a um objeto, que é essencialmente um ponteiro com um pouco de uma luva infantil enrolada em torno dele. É isso que as duas respostas estão dizendo essencialmente.
Panzercrisis
não é um problema de tamanho ou velocidade - é um problema de impossibilidade. O objeto Nó incluído incluiria um objeto Node, que incluiria um objeto Node ... Na verdade, é impossível compilá-lo
PM100
3
@ Panzercrisis Estou ciente de que os dois estão dando a mesma explicação. Essa abordagem, no entanto, não foi tão útil para mim porque se concentrou no que eu já tinha entendido: como os ponteiros funcionam em C ++ e como os ponteiros são manipulados em Java. A resposta aceita abordou especificamente por que não usar um ponteiro seria impossível porque o tamanho não pode ser calculado. Por outro lado, este deixou-o mais vagamente como "uma estrutura definida recursivamente". PS sua explicação que você acabou de escrever explica melhor do que as duas coisas: D.
m0meni
38

C ++ não é Java. Quando você escreve

Node m_next;

em Java, é o mesmo que escrever

Node* m_next;

em C ++. Em Java, o ponteiro está implícito, em C ++, é explícito. Se você escrever

Node m_next;

em C ++, você coloca uma instância Nodeali dentro do objeto que está definindo. Está sempre lá e não pode ser omitido, não pode ser alocado newe não pode ser removido. Esse efeito é impossível de obter em Java e é totalmente diferente do que Java faz com a mesma sintaxe.

cmaster - restabelece monica
fonte
1
Para obter algo semelhante em Java, provavelmente seria "estendido" se o SuperNode estender o Nó, o SuperNodes inclui todos os Atributos do Nó e deve reservar todo o espaço adicional. Assim, em Java você não pode fazer "Nó estende Nó"
Falco
@Falco É verdade que a herança é uma forma de inclusão no local das classes base. No entanto, como o Java não permite herança múltipla (diferente do C ++), você só pode obter uma instância de uma única outra classe preexistente por herança. É por isso que eu não consideraria a herança um substituto para a inclusão de membros no local.
Cmaster - reinstate monica
27

Você usa um ponteiro, caso contrário, seu código:

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

… Não seria compilado, pois o compilador não pode calcular o tamanho de Node. Isso ocorre porque depende de si mesmo - o que significa que o compilador não pode decidir quanta memória consumiria.

Nawaz
fonte
5
Pior ainda, não existe tamanho válido: se k == sizeof(Node)retém e o seu tipo possui dados, ele também deve ser retido sizeof(Node) = k + sizeof(Data) = sizeof(Node) + sizeof(Data)e depois sizeof(Node) > sizeof(Node).
bitmask
4
@bitmask não existe tamanho válido nos números reais . Se você permitir transinfinites, aleph_0funciona. (Just ser excessivamente pedante :-))
k_g
2
@k_g Bem, o padrão C / C ++ exige que o valor de retorno sizeofseja um tipo integral não assinado, então existe a esperança de tamanhos transfinitos ou mesmo reais. (sendo ainda mais pedante: p!)
Thomas
@ Thomas: Pode-se até apontar que existem mesmo os números naturais. (Passar por cima -pedantic: p)
bitmask
1
De fato, Nodenem sequer é definido antes do final deste trecho, portanto você não pode usá-lo realmente por dentro. Permitir que um ponteiro declarar implicitamente para a frente para uma classe ainda não declarada é uma pequena trapaça permitida pelo idioma para possibilitar tais estruturas, sem a necessidade de lançar ponteiros explicitamente o tempo todo.
Osa
13

O último ( Node m_next) teria que conter o nó. Não apontaria para isso. E então não haveria ligação de elementos.

Wallyk
fonte
3
Pior, seria logicamente impossível para um objeto conter algo do mesmo tipo.
91115 Mike Seymour
Tecnicamente, ainda não haveria vinculação porque seria um nó que continha um nó e assim por diante?
M0meni 09/04
9
@ AR7: Não, contenção significa que está literalmente dentro do objeto, não está vinculado a ele.
91115 Mike Seymour
9

A abordagem que você descreve é compatível não apenas com C ++, mas também com a sua (principalmente) linguagem subconjunto C . Aprender a desenvolver uma lista vinculada no estilo C é uma boa maneira de se apresentar a técnicas de programação de baixo nível (como gerenciamento manual de memória), mas geralmente não é uma prática recomendada para o desenvolvimento moderno de C ++.

Abaixo, implementei quatro variações de como gerenciar uma lista de itens em C ++.

  1. raw_pointer_demousa a mesma abordagem que a sua - gerenciamento manual de memória necessário com o uso de ponteiros brutos. O uso de C ++ aqui é apenas para açúcar sintático , e a abordagem usada é compatível com a linguagem C.
  2. Na shared_pointer_demolista, o gerenciamento ainda é feito manualmente, mas o gerenciamento de memória é automático (não usa ponteiros brutos). Isso é muito semelhante ao que você provavelmente já experimentou com Java.
  3. std_list_demousa o listcontêiner da biblioteca padrão . Isso mostra como as coisas ficam mais fáceis se você confiar nas bibliotecas existentes, em vez de criar suas próprias.
  4. std_vector_demousa o vectorcontêiner da biblioteca padrão . Isso gerencia o armazenamento da lista em uma única alocação de memória contígua. Em outras palavras, não há indicadores para elementos individuais. Para certos casos bastante extremos, isso pode se tornar significativamente ineficiente. Para casos típicos, no entanto, essa é a melhor prática recomendada para o gerenciamento de listas em C ++ .

Nota: De todos esses itens, apenas os que raw_pointer_demorealmente exigem que a lista seja destruída explicitamente para evitar "vazamento" de memória. Os outros três métodos destruiriam automaticamente a lista e seu conteúdo quando o contêiner ficar fora do escopo (na conclusão da função). O ponto é: o C ++ é capaz de ser muito "semelhante ao Java" a esse respeito - mas somente se você optar por desenvolver seu programa usando as ferramentas de alto nível à sua disposição.

/*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
fonte
A Node_referencedeclaração acima aborda uma das diferenças mais interessantes no nível da linguagem entre Java e C ++. Em Java, declarar um objeto do tipo Nodeimplicitamente usaria uma referência a um objeto alocado separadamente. No C ++, você tem a opção de alocação de referência (ponteiro) vs. alocação direta (pilha) - portanto, você deve lidar com a distinção explicitamente. Na maioria dos casos, você usaria alocação direta, embora não para elementos da lista.
Brent Bradburn
Não sei por que também não recomendei a possibilidade de um std :: deque .
Brent Bradburn
8

Visão geral

Existem 2 maneiras de referenciar e alocar objetos em C ++, enquanto em Java há apenas uma maneira.

Para explicar isso, os diagramas a seguir mostram como os objetos são armazenados na memória.

1.1 Itens C ++ sem ponteiros

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       | |..
..| +-----------------------------+ |..
..+---------------------------------+..
.......................................

Aviso : A sintaxe C ++ usada neste exemplo é semelhante à sintaxe em Java. Mas, a alocação de memória é diferente.

1.2 Itens C ++ usando ponteiros

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 (...)

Se você verificar a diferença entre os dois lados, verá que, na primeira técnica, o item de endereço é alocado no cliente, enquanto na segunda maneira, você deve criar cada endereço explicitamente.

Aviso: Java aloca objetos na memória como esta segunda técnica, mas a sintaxe é como a primeira maneira, o que pode ser confuso para os novatos no "C ++".

Implementação

Portanto, o exemplo da sua lista pode ser algo semelhante ao exemplo a seguir.

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].
.......................................

Resumo

Como uma lista vinculada tem uma quantidade variável de itens, a memória é alocada conforme necessário e, conforme disponível.

ATUALIZAR:

Também vale a pena mencionar, como @haccks comentou em seu post.

Às vezes, referências ou ponteiros de objeto indicam itens aninhados (também conhecido como "Composição UML").

E, às vezes, referências ou ponteiros de objeto indicam itens externos (também conhecido como "Agregação UML").

Porém, itens aninhados da mesma classe, não podem ser aplicados com a técnica "no-pointer".

umlcat
fonte
7

Em uma nota lateral, se o primeiro membro de uma classe ou estrutura for o próximo ponteiro (portanto, nenhuma função virtual ou qualquer outro recurso de uma classe que significaria o próximo não será o primeiro membro de uma classe ou estrutura), então você pode usar uma classe ou estrutura "base" com apenas um próximo ponteiro e usar código comum para operações básicas de lista vinculada, como anexar, inserir antes, recuperar de frente, .... Isso ocorre porque o C / C ++ garante que o endereço do primeiro membro de uma classe ou estrutura seja o mesmo que o endereço da classe ou estrutura. A classe ou estrutura do nó base teria apenas um próximo ponteiro a ser usado pelas funções básicas da lista vinculada, e a conversão de tipo seria usada conforme necessário para converter entre o tipo de nó base e os tipos de nó "derivados". Nota lateral - em C ++, se a classe do nó base tiver apenas um próximo ponteiro,

rcgldr
fonte
6

Por que é melhor usar ponteiros em uma lista vinculada?

O motivo é que, quando você cria um Nodeobjeto, o compilador precisa alocar memória para esse objeto e para isso o tamanho do objeto é calculado.
O tamanho do ponteiro para qualquer tipo é conhecido pelo compilador e, portanto, com o ponteiro auto-referencial, o tamanho do objeto pode ser calculado.

Se Node m_nodefor usado, o compilador não tem idéia do tamanho de Nodee ficará preso em uma recursão infinita de cálculo sizeof(Node). Lembre-se sempre: uma classe não pode conter um membro de seu próprio tipo .

haccks
fonte
5

Porque isso em C ++

int main (..)
{
    MyClass myObject;

    // or

    MyClass * myObjectPointer = new MyClass();

    ..
}

é equivalente a isso em Java

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

onde ambos criam um novo objeto de MyClass usando o construtor padrão.

Khaled.K
fonte
0

Por que listas vinculadas usam ponteiros em vez de armazenar nós dentro de nós?

É claro que há uma resposta trivial.

Se eles não vinculassem um nó ao outro por um ponteiro, eles não seriam listas vinculadas .

A existência de listas vinculadas é porque queremos ser capazes de encadear objetos. Por exemplo: já temos um objeto de algum lugar. Agora, queremos colocar esse objeto real (não uma cópia) no final de uma fila, por exemplo. Isso é obtido adicionando um link do último elemento já na fila à entrada que estamos adicionando. Em termos de máquina, é preencher uma palavra com o endereço do próximo elemento.

user13784117
fonte