为什么链表使用指针而不是将节点存储在节点内部
我已经广泛地在Java中使用链表，但是我对C ++很陌生。 我正在使用这个在项目中给我的节点类
class Node { public: Node(int data); int m_data; Node *m_next; }; 但是我有一个问题没有得到很好的回答。 为什么有必要使用
Node *m_next;
指向列表中的下一个节点而不是
Node m_next;
我明白，使用指针版本更好; 我不会去争论事实，但是我不知道为什么更好。 关于指针如何更好地分配内存，我得到了一个不太明确的答案，我想知道这里有没有人能帮助我更好地理解。
这不仅仅是更好，这是唯一可能的方式。
如果你在自己内部存储了一个Node 对象 ， sizeof(Node)是什么？ 它将是sizeof(int) + sizeof(Node) ，它将等于sizeof(int) + (sizeof(int) + sizeof(Node)) ，等于sizeof(int) + (sizeof(int) + (sizeof(int) + sizeof(Node)))等无穷大。
像这样的对象不能存在。 这是不可能的 。
在Java中
Node m_node
存储指向另一个节点的指针。 你没有select。 在C ++中
Node *m_node
意味着同样的事情。 不同的是，在C ++中，实际上可以存储对象而不是指向它的指针。 这就是为什么你必须说你想要一个指针。 在C ++中：
Node m_node
意味着在这里存储节点（并且显然不能用于列表 – 最终得到recursion定义的结构）。
C ++不是Java。 当你写
Node m_next;
在Java中，这与写作是一样的
Node* m_next;
在C ++中。 在Java中，指针是隐式的，在C ++中是明确的。 如果你写
Node m_next;
在C ++中，您将Node一个实例放在您定义的对象的内部。 它总是在那里，不能被忽略，它不能被分配new ，它不能被删除。 这种效果在Java中是不可能实现的，它与Java在相同的语法中完全不同。
你使用一个指针，否则你的代码：
class Node { //etc Node m_next; //non-pointer };
… 不会编译，因为编译器无法计算Node的大小。 这是因为它依赖于它本身 – 这意味着编译器不能决定它将消耗多less内存。
后者（ Node m_next ）将不得不包含该节点。 它不会指向它。 那么就不会有元素的联系。
您描述的方法不仅与C ++兼容，而且与其（主要）子集语言C兼容。 学习开发一个C风格的链表是一种很好的方式来介绍自己的低级编程技术（如手动内存pipe理），但它通常不是现代C ++开发的最佳实践。
下面，我已经实现了四种如何在C ++中pipe理项目列表的变体。
-
raw_pointer_demo使用与您的方法相同的方法 – 使用原始指针所需的手动内存pipe理。 这里的C ++的使用只适用于语法糖 ，而且所使用的方法与C语言兼容。 - 在
shared_pointer_demo，列表pipe理仍然是手动完成的，但内存pipe理是自动的 （不使用原始指针）。 这与您可能经历的Java非常相似。 -
std_list_demo使用标准库list容器。 这表明，如果依靠现有的库，而不是自己动手，容易得多。 -
std_vector_demo使用标准库vector容器。 这在单个连续的内存分配中pipe理列表存储。 换句话说，没有指向单个元素的指针。 对于某些相当极端的情况，这可能会变得非常低效。 但对于典型的情况， 这是C ++中列表pipe理的推荐最佳实践 。
注意：在所有这些中，只有raw_pointer_demo实际上要求列表被明确销毁，以避免“泄漏”内存。 当容器超出范围时（function结束时），其他三种方法会自动销毁列表及其内容。 问题的关键在于：C ++在这方面可以非常“类似Java”，但前提是您select使用高级工具来开发您的程序。
/*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 ++中有两种引用和分配对象的方法，而在Java中只有一种方法。
为了解释这一点，下面的图表显示了对象如何存储在内存中。
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 (...)
如果你检查两种方式之间的区别，你会看到，在第一种技术中，地址项目是在客户内部分配的，而第二种方式是，你必须明确地创build每个地址。
警告： Java像第二种技术一样在内存中分配对象，但是，语法就像是第一种方式，这可能会让新手对“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]. .......................................
概要
由于链接列表具有可变数量的项目，所以根据需要分配内存，并且如可用。
更新：
另外值得一提的是，@haccks在他的post中评论道。
有时，引用或对象指针指示嵌套的项目（又名“UML组合”）。
有时，引用或对象指针指示外部项目（又名“UML聚合”）。
但是，同一类的嵌套项目不能用“无指针”技术来应用。
注意，如果类或结构的第一个成员是下一个指针（所以没有虚拟函数或类的任何其他function，这将意味着下一个不是类或结构的第一个成员），那么你可以只使用一个“基”类或结构只有一个下一个指针，并使用普通的代码进行基本的链表操作，如追加，插入前，从前端检索…。 这是因为C / C ++保证类或结构的第一个成员的地址与类或结构的地址相同。 基节点类或结构只有基本链表function使用的下一个指针，那么将根据需要使用types转换来在基节点types和“派生”节点types之间进行转换。 注意 – 在C ++中，如果基节点类只有下一个指针，那么我假定派生类不能有虚函数。
为什么在链表中使用指针会更好？
原因是当你创build一个Node对象时，编译器必须为该对象分配内存，并且计算对象的大小。
指向任何types的指针的大小是编译器已知的 ，因此可以计算出对象的自指针大小。
如果使用Node m_node那么编译器不知道Node的大小，它将停留在计算sizeof(Node)的无限recursion中。 永远记住： 一个类不能包含它自己types的成员 。
因为这在C ++中
int main (..) { MyClass myObject; // or MyClass * myObjectPointer = new MyClass(); .. }
在Java中相当于这个
public static void main (..) { MyClass myObjectReference = new MyClass(); }
两个人都使用默认的构造函数创build一个MyClass的新对象。
