节点定义
带头单链表:我们只需要一个结点指针指向整个链表的第一个节点,这样我们就可以通过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();
}