数据结构复习（七）模板类封装实现不带头结点的单链表

一、代码

二、总结

---

一、代码

#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();
}