为什么链表使用指针而不是在节点内部存储节点

我曾经在 Java 中大量使用过链表，但是对 C + + 来说我还是个新手。我正在使用一个项目中给我的节点类

class Node
{
public:
Node(int data);


int m_data;
Node *m_next;
};

但我有一个问题没有得到很好的回答。为什么有必要使用

Node *m_next;

指向列表中的下一个节点，而不是

Node m_next;

我知道使用指针版本更好; 我不打算讨论事实，但我不知道为什么它更好。关于指针如何更好地进行内存分配，我得到了一个不太清楚的答案，我想知道这里是否有人可以帮助我更好地理解这一点。

16451 次浏览
小开

后者(Node m_next)必须将 包容作为节点。它指不出来。这样元素之间就没有联系了。

小开

使用指针，否则代码:

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

... 将 没有编译，因为编译器无法计算 Node的大小。这是因为它依赖于它自己，这意味着编译器不能决定它将消耗多少内存。

小开
最佳答案

这不仅仅是更好，这是唯一可能的方法。

如果你把一个 Node 对象存储在它自己内部，那么 sizeof(Node)是什么？它是 sizeof(int) + sizeof(Node)，等于 sizeof(int) + (sizeof(int) + sizeof(Node))，等于 sizeof(int) + (sizeof(int) + (sizeof(int) + sizeof(Node)))，等于无穷大。

这样的物体不可能存在，这是 不可能。

小开

用爪哇语

Node m_node

stores a pointer to another node. You don't have a choice about it. In C++ 

Node *m_node

意思是一样的。不同之处在于，在 C + + 中实际上可以存储对象，而不是存储指向它的指针。这就是为什么你必须说你想要一个指针。在 C + + 中:

Node m_node

意味着将节点存储在这里(这显然不适用于列表——最终将得到一个递归定义的结构)。

小开

C + + 不是 Java

Node m_next;

在 Java 中，这和写一样

Node* m_next;

在 Java 中，指针是隐式的，在 C + + 中是显式的

Node m_next;

在 C + + 中，您将 Node的一个实例放在您正在定义的对象中。它总是在那里，不能被忽略，它不能被分配与 new，它不能被删除。这种效果在 Java 中是不可能实现的，而且它完全不同于 Java 使用相同语法所做的工作。

小开

顺便说一句，如果类或结构的第一个成员是下一个指针(所以没有虚函数或类的任何其他特性意味着下一个不是类或结构的第一个成员) ，那么你可以使用一个“基”类或结构只有一个下一个指针，并使用公共代码的基本链表操作，如附加，插入之前，检索前，..。这是因为 C/C + + 保证类或结构的第一个成员的地址与类或结构的地址相同。基本节点类或结构只有一个下一个指针供基本链表函数使用，然后根据需要进行类型转换，以便在基本节点类型和“派生”节点类型之间进行转换。附注: 在 C + + 中，如果基本节点类只有一个下一个指针，那么我假设派生类不能有虚函数。

小开

为什么在链表中使用指针更好？

原因是当您创建 Node对象时，编译器必须为该对象分配内存，并为此计算对象的大小。
任何类型的指针大小都是编译器已知的 ，因此可以用自引用的指针大小来计算对象。

如果用 Node m_node代替，那么编译器就不知道 Node的大小，它会卡在计算 sizeof(Node)的 无限递归中。永远记住: 类不能包含自己类型 的成员。

小开

概述

There are 2 ways to reference and allocate objects in C++, while in Java there is only one way.

为了解释这一点，下面的图表显示了对象是如何存储在内存中的。

1.1 C + + 没有指针的项目

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

警告 : 本例中使用的 C + + 语法与 Java 中的语法类似。但是，内存分配是不同的。

1.2使用指针的 C + + 项

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

如果你检查两种方式的区别，你会发现, 在第一种技术中，地址项是在客户中分配的，而在第二种方法中，您必须显式地创建每个地址。

Warning: Java allocates objects in memory like this second technique, but, the syntax is like the first way, which may be confusing to newcomers to "C++".

实施

因此，您的列表示例可以类似于下面的示例。

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

摘要

由于 LinkedList 中的项数量是可变的，因此会根据需要和可用性分配内存。

更新:

Also worth to mention, as @haccks commented in his post.

That sometimes, references or object pointers, indicate nested items (a.k.a. "U.M.L. Composition").

And sometimes, references or object pointers, indicates external items (a.k.a. "U.M.L. Aggregation").

但是，同一类的嵌套项不能用“无指针”技术应用。

小开

The approach that you describe is compatible not only with C++, but also with its (主要)子语言 C. Learning to develop a C-style linked-list is a good way to introduce yourself to low-level programming techniques (such as manual memory management), but it generally is 没有 a best-practice for modern C++ development.

下面，我实现了关于如何在 C + + 中管理项目列表的四个变体。

  1. raw_pointer_demo使用与您相同的方法——使用原始指针需要手动内存管理。这里使用的 C + + 只适用于 译自: http://www.wikipedia.org/wiki/Syntactssugar/(http://en.wikipedia.org/wiki/Syntactssugar)，并且所使用的方法与 C 语言兼容。
  2. 在 shared_pointer_demo中，列表管理仍然是手工完成的，但是内存管理是 自动的(不使用原始指针)。这与您在 Java 中可能经历的情况非常相似。
  3. std_list_demo使用标准库 list容器。这表明，如果依赖现有库而不是自己的库，事情会变得容易得多。
  4. std_vector_demo使用标准库 vector容器。这将管理单个连续内存分配中的列表存储。换句话说，没有指向单个元素的指针。对于某些相当极端的情况，这可能会变得非常低效。然而，对于典型案例，这是 C + + 中列表管理推荐的最佳实践。

注意: 在所有这些方法中，只有 raw_pointer_demo实际上要求显式销毁列表，以避免“泄漏”内存。当容器超出范围时(在函数结束时) ，其他三个方法将 自然而然地销毁列表及其内容。关键在于: 在这方面，C + + 能够非常“像 Java”——但是只有在您选择使用可支配的高级工具开发程序时才能这样做。

/*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();
}
小开

因为在 C + + 里

int main (..)
{
MyClass myObject;


// or


MyClass * myObjectPointer = new MyClass();


..
}

相当于 爪哇咖啡中的这个

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

where both of them create a new object of MyClass using the default constructor.

小开

为什么链表使用指针而不是将节点存储在 节点？

当然有一个微不足道的答案。

如果他们没有通过一个指针从一个节点到下一个节点，他们就不会是 连结清单。

链表的存在是因为我们希望能够将对象链接在一起。例如: 我们已经有一个来自某个地方的对象。例如，我们现在希望将实际对象(而不是副本)放在队列的末尾。这是通过将队列中已有的最后一个元素的 链接添加到我们正在添加的条目中来实现的。用机器的术语来说，就是用下一个元素的地址来填充一个单词。


提交答案