双向链表混淆
Doubly linked list confusion
我创建了双向链表和 2 个函数。第一个函数从头到尾打印列表,第二个函数从头到尾打印列表。在第二个函数中,我将第一个 node->prev 设置为 NULL 但是
- 我不明白为什么第一个函数实际上有效,因为我从未将最后一个节点的下一个指针设置为 NULL,所以在我看来它应该创建一个无限循环。
代码如下:
#include <iostream>
using namespace std;
class LinkedList
{
struct Node
{
int data;
Node * next;
Node * prev;
};
public:
LinkedList ( void );
void AddToList ( int val );
void FrontToBack ( void ) const;
void BackToFront ( void ) const;
private:
Node * head;
Node * n;
Node * tail;
};
LinkedList::LinkedList ( void )
{
head = NULL;
n = NULL;
tail = NULL;
}
void LinkedList::AddToList ( int val )
{
n = new Node ( );
n -> data = val;
if ( head == NULL )
{
n -> prev = NULL;
head = n;
tail = n;
}
else
{
n -> prev = tail;
tail -> next = n;
tail = n;
}
}
void LinkedList::FrontToBack ( void ) const
{
Node * tmp = head;
int size = 0;
cout << "Printing list from head to tail:" << endl;
while ( tmp != NULL )
{
if ( ! size )
{
cout << tmp -> data;
tmp = tmp -> next;
}
else
{
cout << " " << tmp -> data;
tmp = tmp -> next;
}
++ size;
}
cout << endl;
}
void LinkedList::BackToFront ( void ) const
{
Node * tmp = tail;
int size = 0;
cout << "Printing list from tail to head:" << endl;
while ( tmp != NULL )
{
if ( ! size )
{
cout << tmp -> data;
tmp = tmp -> prev;
}
else
{
cout << " " << tmp -> data;
tmp = tmp -> prev;
}
++ size;
}
cout << endl;
}
int main ( void )
{
LinkedList list;
list.AddToList( 1 );
list.AddToList( 2 );
list.AddToList( 3 );
list.AddToList( 4 );
list.AddToList( 5 );
list.AddToList( 6 );
list.FrontToBack( );
list.BackToFront( );
return 0;
}
- I do not understand why the first function actually works because I have never set the last node's next pointer to NULL so in my opinion it should create an infinite loop.
struct Node
的 next
和 prev
指针从未被初始化,因此访问和取消引用它们是未定义的行为。这意味着您不能期望任何特定行为,例如 无限循环 。
为了确保定义的行为,只需默认初始化 Node
结构中的指针:
struct Node
{
int data;
Node * next;
Node * prev;
Node() : next(nullptr), prev(nullptr) {} // <<<<<<<<<<<<<<<<<<<
};
我创建了双向链表和 2 个函数。第一个函数从头到尾打印列表,第二个函数从头到尾打印列表。在第二个函数中,我将第一个 node->prev 设置为 NULL 但是
- 我不明白为什么第一个函数实际上有效,因为我从未将最后一个节点的下一个指针设置为 NULL,所以在我看来它应该创建一个无限循环。
代码如下:
#include <iostream>
using namespace std;
class LinkedList
{
struct Node
{
int data;
Node * next;
Node * prev;
};
public:
LinkedList ( void );
void AddToList ( int val );
void FrontToBack ( void ) const;
void BackToFront ( void ) const;
private:
Node * head;
Node * n;
Node * tail;
};
LinkedList::LinkedList ( void )
{
head = NULL;
n = NULL;
tail = NULL;
}
void LinkedList::AddToList ( int val )
{
n = new Node ( );
n -> data = val;
if ( head == NULL )
{
n -> prev = NULL;
head = n;
tail = n;
}
else
{
n -> prev = tail;
tail -> next = n;
tail = n;
}
}
void LinkedList::FrontToBack ( void ) const
{
Node * tmp = head;
int size = 0;
cout << "Printing list from head to tail:" << endl;
while ( tmp != NULL )
{
if ( ! size )
{
cout << tmp -> data;
tmp = tmp -> next;
}
else
{
cout << " " << tmp -> data;
tmp = tmp -> next;
}
++ size;
}
cout << endl;
}
void LinkedList::BackToFront ( void ) const
{
Node * tmp = tail;
int size = 0;
cout << "Printing list from tail to head:" << endl;
while ( tmp != NULL )
{
if ( ! size )
{
cout << tmp -> data;
tmp = tmp -> prev;
}
else
{
cout << " " << tmp -> data;
tmp = tmp -> prev;
}
++ size;
}
cout << endl;
}
int main ( void )
{
LinkedList list;
list.AddToList( 1 );
list.AddToList( 2 );
list.AddToList( 3 );
list.AddToList( 4 );
list.AddToList( 5 );
list.AddToList( 6 );
list.FrontToBack( );
list.BackToFront( );
return 0;
}
- I do not understand why the first function actually works because I have never set the last node's next pointer to NULL so in my opinion it should create an infinite loop.
struct Node
的 next
和 prev
指针从未被初始化,因此访问和取消引用它们是未定义的行为。这意味着您不能期望任何特定行为,例如 无限循环 。
为了确保定义的行为,只需默认初始化 Node
结构中的指针:
struct Node
{
int data;
Node * next;
Node * prev;
Node() : next(nullptr), prev(nullptr) {} // <<<<<<<<<<<<<<<<<<<
};