数据结构复习（七）模板类封装实现不带头结点的单链表
一、代码
二、总结
一、代码
#include<iostream>
using namespace std;template<class T>
struct ListNode
{T _data;ListNode* next;ListNode(const T& data = T()){_data = data;next = nullptr;}~ListNode(){next = nullptr;}
};template<class T>
class List
{typedef ListNode<T> Node; // 重命名
public:List(){_head = nullptr;}void PushFront(const T& data = T()) // 每次对头结点判空处理{Node* newnode = new Node(data);if (_head == nullptr)_head = newnode;else{Node* cur = _head;_head = newnode;_head->next = cur;}}void PopFront(){if (_head == nullptr)return;Node* del = _head;_head = _head->next;delete del;}void PushBack(const T& data = T()){Node* newnode = new Node(data);if (_head == nullptr){_head = newnode;return;}Node* cur = _head;while (cur->next){cur = cur->next;}cur->next = newnode;}void PopBack(){Node* pre = _head;if (pre == nullptr)return;else if (pre->next == nullptr){_head = nullptr;delete pre;}else{Node* cur = _head->next;while (cur->next){cur = cur->next;pre = pre->next;}pre->next = nullptr;delete cur;}}
private:Node* _head;
};void Test()
{List<int> l;l.PushBack(0);l.PushBack(1);l.PushBack(2);l.PushBack(3);l.PushBack(4);l.PopBack(); l.PopBack(); l.PopBack();l.PopBack();l.PopBack();l.PopBack();l.PopBack();
}void Test1()
{List<int> l;l.PushFront(0);l.PushFront(1);l.PushFront(2);l.PushFront(3);l.PushFront(4);l.PopFront();l.PopFront();l.PopFront();l.PopFront();l.PopFront();l.PopFront();l.PopFront();
}二、总结
带头结点的单链表和不带头结点的单链表
一、两者区别：
1、不带头结点的单链表对于第一个节点的操作与其他节点不一样，需要特殊处理，这增加了程序的复杂性和出现bug的机会，因此，通常在单链表的开始结点之前附设一个头结点。
2、带头结点的单链表,初始时一定返回的是指向头结点的地址，所以一定要用二维指针，否则将导致内存访问失败或异常。
3、带头结点与不带头结点初始化、插入、删除、输出操作都不样，在遍历输出链表数据时，带头结点的判断条件是while(head->next!=NULL)，而不带头结点是while(head!=NULL)，虽然头指针可以在初始时设定，但是如1所述，对于特殊情况如只有一个节点会出现问题。
二、为什么不带头结点初始化有2种方式，而带头结点只有1种方式呢？
因为不带头结点声明Node
*head
时；C编译器将其自动初始化为NULL，于是根本不需要调用InitList(head)；也即不带头结点的初始化是个伪操作。而带头结点的初始化在堆开辟了一段内存，需要修改head指针变量指向的地址(即head的值)，所以要修改head的值，必须传保存head变量的地址(即二维指针)。而直接调用CreatList(head);相当于传head变量的值，函数修改的是head的副本，无法真正改变head的值。 注：这里可以将head指针看成一个变量(不管它保存的是地址)，就比较好理解了。
三、其实本质上还是传值，传址的问题，只不过指针本身保存的地址，让这个过程变得有点纠结。在函数调用需要修改指针变量的指向(value)时，应该传递指针变量的地址(address)。
另外，对于函数的形参是指针时，只要该参数不在左边（即都是右值操作），二维指针（形参）就可以简化为一维指针。如上面带头结点的尾插简化版本。
#include<iostream>
using namespace std;template<class T>
struct ListNode
{
T _data;
ListNode* next;
ListNode(const T& data = T())
{
_data = data;
next = nullptr;
}
~ListNode()
{
next = nullptr;
}
};template<class T>
class List
{
typedef ListNode<T> Node;
public:
List()
{
_head = nullptr;
}
void PushFront(const T& data = T())
{
Node* newnode = new Node(data);
if (_head == nullptr)
_head = newnode;
else
{
Node* cur = _head;
_head = newnode;
_head->next = cur;
}
}
void PopFront()
{
if (_head == nullptr)
return;
Node* del = _head;
_head = _head->next;
delete del;
}
void PushBack(const T& data = T())
{
Node* newnode = new Node(data);
if (_head == nullptr)
{
_head = newnode;
return;
}
Node* cur = _head;
while (cur->next)
{
cur = cur->next;
}
cur->next = newnode;
}
void PopBack()
{
Node* pre = _head;
if (pre == nullptr)
return;
else if (pre->next == nullptr)
{
_head = nullptr;
delete pre;
}
else
{
Node* cur = _head->next;
while (cur->next)
{
cur = cur->next;
pre = pre->next;
}
pre->next = nullptr;
delete cur;
}
}
private:
Node* _head;
};void Test()
{
List<int> l;
l.PushBack(0);
l.PushBack(1);
l.PushBack(2);
l.PushBack(3);
l.PushBack(4);
l.PopBack();
l.PopBack();
l.PopBack();
l.PopBack();
l.PopBack();
l.PopBack();
l.PopBack();
}void Test1()
{
List<int> l;
l.PushFront(0);
l.PushFront(1);
l.PushFront(2);
l.PushFront(3);
l.PushFront(4);
l.PopFront();
l.PopFront();
l.PopFront();
l.PopFront();
l.PopFront();
l.PopFront();
l.PopFront();
}