这里以结构体的方式来实现链表，也可以使用类。结构体在没有修饰符的情况下，默认是共有访问。如有不对，希望能指出。

---

目录

一、链表和结点结构体的声明 (ListNode.h)

二、链表各个功能的实现

1、增

(1) 构造函数（创建链表头结点）

 (2) 尾插

(3) 头插

(4) 任意位置的插入

2、删

(1) 尾删

 (2) 任意位置的删除

(3) 链表释放

3、查

(1) 获取元素个数

(2) 正向打印

(3) 反向打印

---

一、链表和结点结构体的声明 (ListNode.h)

typedef int data_t;typedef struct ListNode {		// 结点声明data_t data;ListNode* next;ListNode* prev;
}ListNode;typedef struct SeqLinkList {SeqLinkList();void list_print();					// 从前往后打印链表void list_reverse_print();			// 从后往前打印链表size_t size();						// 链表大小（链表结点个数）int push_back(data_t val);			// 尾插void pop_back();					// 尾删int push_front(data_t val);			// 头插int list_find(data_t val);			// 查找某个结点int list_insert(int pos, data_t val);	// 在某个位置插入一个结点int list_delete(int pos);				// 删除某个位置的结点void list_destroy();					// 释放整个链表private:ListNode* _phead;					// 链表头结点的地址ListNode* _ptail;					// 链表尾结点的地址size_t _num;						// 链表元素的个数}SeqLinkList;

二、链表各个功能的实现

1、增

(1) 构造函数（创建链表头结点）

创建一个空的头结点，同时初始化元素个数

SeqLinkList::SeqLinkList() {_phead = (ListNode*)malloc(sizeof(ListNode));assert(_phead);_ptail = _phead;		// 此时头尾指向同一个地方_num = 0;		// 初始化结点的个数
}

 (2) 尾插

int SeqLinkList::push_back(data_t val) {ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));if (newNode == NULL)return -1;newNode->data = val;newNode->next = NULL;newNode->prev = _ptail;_ptail->next = newNode;	// 链接新的结点_ptail = newNode;		// 尾节点移动_num++;return 0;
}

(3) 头插

int SeqLinkList::push_front(data_t val) {ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));if (newNode == NULL)return -1;ListNode* nextNode = _phead->next;		// _phead的下一个结点newNode->data = val;newNode->next = nextNode;newNode->prev = _phead;_phead->next = newNode;if (nextNode != NULL)nextNode->prev = newNode;_num++;return 0;
}

(4) 任意位置的插入

int SeqLinkList::list_insert(int pos, data_t val) {if (pos > _num - 1)return -1;ListNode* current = _phead;while (pos-- && (current = current->next) != NULL);ListNode* nextNode = current->next;			// 记录下当前节点的下一个结点ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));if (newNode == NULL)return -1;newNode->data = val;            // 链接新的结点current->next = newNode;newNode->next = nextNode;newNode->prev = current;if (nextNode != NULL)nextNode->prev = newNode;		// 考虑尾插_num++;return 0;
}

2、删

(1) 尾删

void SeqLinkList::pop_back() {ListNode* tailNode = _ptail;		// 记录尾节点_ptail = _ptail->prev;			_ptail->next = NULL;free(tailNode);tailNode = NULL;_num--;
}

 (2) 任意位置的删除

int SeqLinkList::list_delete(int pos) {if (pos > _num - 1)return -1;ListNode* current = _phead;while (pos-- && (current = current->next) != NULL);if (current == _phead)_phead = current->next;		// 考虑头删else{ListNode* prevNode = current->prev;ListNode* nextNode = current->next;prevNode->next = nextNode;if (nextNode != NULL)nextNode->prev = prevNode;}free(current);current = NULL;_num--;return 0;
}

(3) 链表释放

void SeqLinkList::list_destroy() {_num++;			// 补上一个头结点，下面是连带着头结点一起释放了while (_phead != NULL){ListNode* lastNode = _phead;_phead = _phead->next;free(lastNode);lastNode = NULL;_num--;}
}

 

3、查

(1) 获取元素个数

size_t SeqLinkList::size() {return _num;
}

(2) 正向打印

void SeqLinkList::list_print(){ListNode* current = _phead;while ((current = current->next) != NULL){printf("%d->", current->data);}
}

(3) 反向打印

void SeqLinkList::list_reverse_print() {ListNode* current = _ptail;while (current != _phead){printf("%d->", current->data);current = current->prev;}
}