带头单链表 C++实现

节点定义

带头单链表：我们只需要一个结点指针指向整个链表的第一个节点，这样我们就可以通过next指针访问整个链表内的所有节点

template<class T>
struct ListNode
{T _val;ListNode* _next;ListNode(const T &val):_val(val),_next(nullptr){}
};

 这里默认将节点的_next指针设置成nullptr

构造析构函数

 成员变量只需要Node* 的头指针即可，这里的_n用来记录整个链表中有几个节点

初始化将_head赋成nullptr 因为开始是空链表

析构：直接遍历链表中的节点，按顺序删除节点即可

template<class T>
class List
{
public:typedef ListNode<T> Node;List(){_head = nullptr;_n = 0;}~List(){Node* cur = _head;while (cur){_head = _head->_next;delete cur;cur = _head;--_n;}_head = nullptr;}private:Node* _head;size_t _n;
};

插入节点

        push_back

尾插：首先需要找到最后一个节点的地址，将新节点连到最后一个节点的_next上完成尾插

需要考虑_head 为nullptr的情况，因为 为nullptr时找尾操作会访问野指针！

void push_back(const T& val)
{Node* newnode = new Node(val);if (_head == nullptr){_head = newnode;_n++;}else{Node* cur = _head;while (cur->_next){cur = cur->_next;}cur->_next = newnode;_n++;}
}

        push_front

头插：头插不需要找尾，只需要让新节点指向原链表，头节点_head指向新节点即可

注意还需要考虑_head为nullptr的情况

void push_front(const T& val)
{Node* newnode = new Node(val);newnode->_next = _head;_head = newnode;++_n;
}

删除节点

pop_back

这里需要分情况，这里的0个节点的情况作了温柔处理，还可以直接assert暴力处理

有多个节点时，需要找到最后一个节点和最后一个的节点的前一个节点，进行删除操作，并将tailPrev的next指针赋为nullptr 

	void pop_back(){//①0个节点if (_head == nullptr){return;}//②一个节点if (_head->_next == nullptr){delete _head;_head = nullptr;--_n;return;}//③一个节点以上Node* tail = _head;Node* tailPrev = nullptr;while (tail->_next){tailPrev = tail;tail = tail->_next;}	delete tail;tail = nullptr;tailPrev->_next = nullptr;--_n;}

pop_front

头删比尾删简单的多：还是这里的空链表情况进行了温柔处理，还可以assert暴力处理

先将_head指向第二个节点，如果只有一个节点的话恰好就是nullptr，然后直接删除_head之前指向的节点 

	void pop_front(){if (_head == nullptr){return;}Node* deleteNode = _head;_head = _head->_next;delete deleteNode;deleteNode = nullptr;--_n;}

遍历节点

 根据链表的最后一个节点的next指针是空来判断走到了链表的尽头，挨个打印即可

void print()
{Node* cur = _head;while (cur){cout << cur->_val << "->";cur = cur->_next;}cout << "NULL" << endl;cout << "节点数量：" << _n << endl;
}

测试代码

void test1()
{List<int> L1;L1.push_back(10);L1.push_back(20);L1.push_back(30);L1.push_back(40);L1.print();
}void test2()
{List<int>L1;L1.push_front(10);L1.push_front(20);L1.push_front(30);L1.push_front(40);L1.print();L1.pop_back();L1.pop_back();L1.print();
}
void test3()
{List<int>L1;L1.push_front(10);L1.push_front(20);L1.push_front(30);L1.push_front(40);L1.print();L1.pop_front();L1.pop_front();L1.pop_front();L1.pop_front();L1.pop_front();L1.print();
}void test4()
{List<int>L1;L1.push_front(10);L1.push_front(20);L1.push_front(30);L1.push_front(40);L1.print();L1.pop_back();L1.pop_back();L1.pop_back();L1.pop_back();L1.pop_back();L1.pop_back();L1.print();
}