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

目录

一、链表和结点结构体的声明 (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;}
}