使用类模板封装一个链表，模板如下
class List{
public:
struct node{
T val;
node* next;
node* prev;可选
}
private:
node* head;
node* tail;
构造函数
析构函数
增删改查排遍历 6个函数
}
程序代码：
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <unistd.h>
#include <sstream>
#include <vector>
#include <memory>using namespace std; template <typename T>
class List {
public:struct Node {T val;Node* next;Node* prev;Node(const T& value) : val(value), next(NULL), prev(NULL) {}};// 迭代器类class Iterator {private:Node* current;public:Iterator(Node* node) : current(node) {}// 解引用操作符T& operator*() const {return current->val;}// 前置递增操作符Iterator& operator++() {if (current) {current = current->next;}return *this;}// 后置递增操作符Iterator operator++(int) {Iterator temp = *this;++(*this);return temp;}// 前置递减操作符Iterator& operator--() {if (current) {current = current->prev;}return *this;}// 后置递减操作符Iterator operator--(int) {Iterator temp = *this;--(*this);return temp;}// 相等比较操作符bool operator==(const Iterator& other) const {return current == other.current;}// 不等比较操作符bool operator!=(const Iterator& other) const {return current != other.current;}};private:Node* head;Node* tail;public:// 构造函数List() : head(NULL), tail(NULL) {}// 析构函数~List() {while (head) {Node* temp = head;head = head->next;delete temp;}}// 在链表尾部添加元素void push_back(const T& value) {Node* newNode = new Node(value);if (!tail) {head = tail = newNode;} else {tail->next = newNode;newNode->prev = tail;tail = newNode;}}// 在链表头部添加元素void push_front(const T& value) {Node* newNode = new Node(value);if (!head) {head = tail = newNode;} else {newNode->next = head;head->prev = newNode;head = newNode;}}// 删除链表尾部元素void pop_back() {if (!tail) return;Node* temp = tail;if (tail->prev) {tail = tail->prev;tail->next = NULL;} else {head = tail = NULL;}delete temp;}// 删除链表头部元素void pop_front() {if (!head) return;Node* temp = head;if (head->next) {head = head->next;head->prev = NULL;} else {head = tail = NULL;}delete temp;}// 查找元素是否存在bool find(const T& value) const {Node* current = head;while (current) {if (current->val == value) {return true;}current = current->next;}return false;}// 修改指定位置的元素void update(int index, const T& value) {Node* current = head;int count = 0;while (current) {if (count == index) {current->val = value;return;}current = current->next;count++;}cout << "下标超出了范围" << endl;}// 遍历链表并打印元素void show() {for (const auto& val : *this) {cout << val << " ";}cout << endl;}// 排序链表（简单实现，使用冒泡排序）void sort() {if (!head) return;bool swapped;Node* ptr1;Node* lptr = NULL;do {swapped = false;ptr1 = head;while (ptr1->next != lptr) {if (ptr1->val > ptr1->next->val) {swap(ptr1->val, ptr1->next->val);swapped = true;}ptr1 = ptr1->next;}lptr = ptr1;} while (swapped);}// 返回链表头部迭代器Iterator begin() const {return Iterator(head);}// 返回链表尾部迭代器Iterator end() const {return Iterator(NULL);}
};int main() {List<int> list;list.push_back(3);list.push_back(1);list.push_back(2);list.push_front(0);cout << "原始链表: ";list.show();list.sort();cout << "列表排序后: ";list.show();list.update(1, 5);cout << "修改数据后: ";list.show();list.pop_back();list.pop_front();cout << "头删和尾删之后: ";list.show();return 0;
}
运行结果：
