链表是构建其他复杂数据结构的基础，如栈、队列、图和哈希表等。通过对链表进行适当的扩展和修改，可以实现这些数据结构的功能。想学算法，数据结构，不会链表是万万不行的。这篇笔记是一名小白在学习时整理的。
C语言
链表部分
链表的定义
这里用原始的方法定义了一个含有3个节点的链表，并用原始的办法输出。
输出时，一种用“ -> ”，另一种只用“ . ”
#include <stdio.h>
#include <stdlib.h>typedef struct Node {int date;struct Node* next;
}Node;int main() {Node node01 = { 11,NULL };Node node02 = { 22,NULL };Node node03 = { 33,NULL };node01.next = &node02;node02.next = &node03;printf("%d\n", node01.date);printf("%d\n", node01.next->date);printf("%d\n", (*(node01.next)).date);printf("%d\n", node01.next->next->date);printf("%d\n", (*(*(node01.next)).next).date);system("pause");
}链表的遍历
循环遍历
以循环遍历的方式输出链表的数据
这里需要用到指针
#include <stdio.h>
#include <stdlib.h>typedef struct Node {int date;struct Node* next;
}Node;int main() {Node node01 = { 11,NULL };Node node02 = { 22,NULL };Node node03 = { 33,NULL };node01.next = &node02;node02.next = &node03;Node* point = &node01;while (point != NULL) {printf("%d\n", point->date);point = point->next;}system("pause");
}递归遍历
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {int date;struct Node* next;
}Node;void printList(Node* point);
int main() {Node node01 = { 11,NULL };Node node02 = { 22,NULL };Node node03 = { 33,NULL };node01.next = &node02;node02.next = &node03;Node* point = &node01;printList(point);system("pause");
}void printList(Node* point) {if(point != NULL){printf("%d\n", point->date);printList(point->next);}
}链表的插入
后插法
将一个新节点添加在date为22的节点之后
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {int date;struct Node* next;
}Node;
void printList(Node* point);
void insertListBehind(Node* point, int id, Node* newnode);int main() {Node node01 = { 11,NULL };Node node02 = { 22,NULL };Node node03 = { 33,NULL };node01.next = &node02;node02.next = &node03;Node* point = &node01;Node newnode = { 23,NULL };insertListBehind(point, 22, &newnode);printList(point);system("pause");
}void insertListBehind(Node* point, int id,Node*newnode) {while (point != NULL) {if (point->date == id) {newnode->next = point->next;point->next = newnode;}point = point->next;}
}void printList(Node* point) {if(point != NULL){printf("%d\n", point->date);printList(point->next);}
}前插法
比后插难一点点，要用到头指针。
要考虑到前插到第一个节点的情况（单独考虑），我们可以用后插法来实现前插法。
即，如果前插到data为22的前面，我们可以转化为后插到data为22的节点的前一个节点的后面。
用到了二级指针
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {int data;struct Node* next;
} Node;
void printList(Node* head);
void insertListFront(Node** head, int id, Node* newnode);int main() {Node node01 = { 11, NULL };Node node02 = { 22, NULL };Node node03 = { 33, NULL };node01.next = &node02;node02.next = &node03;Node* head = &node01;Node newnode = { 12, NULL };insertListFront(&head, 22, &newnode);printList(head);system("pause");return 0;
}
void insertListFront(Node** head, int id, Node* newnode) {Node* point = *head;if (point->data == id) {newnode->next = point;*head = newnode;}else {while (point->next != NULL) {if (point->next->data == id) {newnode->next = point->next;point->next = newnode;break;}point = point->next;}}
}void printList(Node* head) {Node* point = head;while (point != NULL) {printf("%d\n", point->data);point = point->next;}
}链表的删除
可以参照前插法的思路，几乎一样的
这里删除data为22的那个节点。
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {int data;struct Node* next;
} Node;
void printList(Node* head);
void deleteListFront(Node** head, int id);int main() {Node node01 = { 11, NULL };Node node02 = { 22, NULL };Node node03 = { 33, NULL };node01.next = &node02;node02.next = &node03;Node* head = &node01;deleteListFront(&head, 22);printList(head);system("pause");return 0;
}
void deleteListFront(Node** head, int id) {Node* point = *head;if (point->data == id) {*head = point->next;}else {while (point->next != NULL) {if (point->next->data == id) {point->next = point->next->next;break;}point = point->next;}}
}void printList(Node* head) {Node* point = head;while (point != NULL) {printf("%d\n", point->data);point = point->next;}
}注意：这里的删除仅仅是断开了链表与该块数据的链接，并不是真正的删除。
真正的删除在下面《动态链表节点的删除》
动态链表
链表的动态添加
于链表前端添加节点
类似前插法，但是用malloc，实际上更简单一点。
我们可以利用头指针来添加
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {int data;struct Node* next;
}Node;
void addNodeFront(Node** head, int data);
void printList(Node* head);int main() {Node* head = NULL;addNodeFront(&head, 111);addNodeFront(&head, 222);addNodeFront(&head, 333);printList(head);
}
void addNodeFront(Node** head, int data) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = data;newNode->next = NULL;if (*head == NULL) {*head = newNode;}else {newNode->next = *head;*head = newNode;}
}void printList(Node* head) {Node* point = head;while (point != NULL) {printf("%d\n", point->data);point = point->next;}
}于链表后端添加节点
比前加难一点。因为头指针只指头，所以要找到尾指针。
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {int data;struct Node* next;
}Node;
void addNodeBehind(Node** head, int data);
void printList(Node* head);int main() {Node* head = NULL;addNodeBehind(&head, 111);addNodeBehind(&head, 222);addNodeBehind(&head, 333);printList(head);
}
void addNodeBehind(Node** head, int data) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = data;newNode->next = NULL;if (*head == NULL) {*head = newNode;}else {Node* point = *head;while(point->next != NULL) {point = point->next;}point->next = newNode;}
}void printList(Node* head) {Node* point = head;while (point != NULL) {printf("%d\n", point->data);point = point->next;}
}动态链表删除节点
由于C语言不会像Java那样有垃圾处理器，断开连接后内存不会自动释放。
我们可以使用 free() 来实现。free掉从链表上取下的节点。
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {int data;struct Node* next;
}Node;
void deleteNode(Node** head, int id);
void addNodeBehind(Node** head, int data);
void printList(Node* head);int main() {Node* head = NULL;addNodeBehind(&head, 111);addNodeBehind(&head, 222);addNodeBehind(&head, 333);deleteNode(&head, 222);printList(head);
}void deleteNode(Node** head, int id) {Node* point = *head;if (point->data == id) {*head = point->next;free(point);}else {while (point->next != NULL) {if (point->next->data == id) {Node* deletetemp = point->next;point->next = deletetemp->next;free(deletetemp);}point = point->next;}}
}void addNodeBehind(Node** head, int data) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = data;newNode->next = NULL;if (*head == NULL) {*head = newNode;}else {Node* point = *head;while(point->next != NULL) {point = point->next;}point->next = newNode;}
}
void printList(Node* head) {Node* point = head;while (point != NULL) {printf("%d\n", point->data);point = point->next;}
}只需要在原来删除节点的基础上，标记出要删除的那个节点，在断开链接后，再free掉它。
循环列表
之前学习研究的链表都是条状的，非循环的连表，有头有尾。循环列表是环状的哦。
循环列表的插入及遍历
如果循环列表为空，即插入的节点为第一个节点，该节点的next应指向自身。若不为空，先找到原列表最后一个，添加后，让新的末端指向头。
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {int data;struct Node* next;
}Node;
void addNodeBehind(Node** head, int data);
void printList(Node* head);int main() {Node* head = NULL;addNodeBehind(&head, 111);addNodeBehind(&head, 222);addNodeBehind(&head, 333);printList(head);
}void addNodeBehind(Node** head, int data) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = data;newNode->next = NULL;if (*head == NULL) {*head = newNode;}else {Node* point = *head;while(point->next != *head) {point = point->next;}point->next = newNode;}newNode->next = *head;
}
void printList(Node* head) {Node* point = head;do{printf("%d\n", point->data);point = point->next;} while (point != head);
}注意：因为链表的结束标志不再是节点的next指向为空，而是指向为头结点，所以遍历时应做出修改。因为point一开始就指向头节点，结束标志也是头节点，所以我使用do-while循环。
双向链表
大多为环装
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {int data;struct Node* next;struct Node* prev;
}Node;
void addNode(Node**head,int data);
void printList(Node* head);int main() {Node* head = NULL;addNode(&head, 111);addNode(&head, 222);addNode(&head, 333);printList(head);return 0;
}void addNode(Node** head, int data) {Node* newnode = (Node*)malloc(sizeof(Node));newnode->data = data;newnode->next = newnode;newnode->prev = newnode;if (*head == NULL) {*head = newnode;}else {Node* first = *head;Node* last = first->prev;last->next = newnode;newnode->prev = last;newnode->next = first;first->prev = newnode;}
}void printList(Node* head) {Node* point = head;do {printf("%d\n", point->data);point = point->next;}while (point != head);
}相比之下，双向链表插入等操作时，要断开2个链接，建立2个链接。但是不必使用循环。因为可以直接通过头找到尾。
C++语言
C++ List的基础知识
和<vector>的用法很像。
但是不能通过索引（索引的实质是地址的偏移量）来查找，因为链表的内存不是连续的，不像数组那样。不能随机查找
一些list函数，关键字等将在代码中进行注释
list的的声明
#include <iostream>
#include <list>int main() {std::list<int> list1; // 创建一个空的链表std::list<int> list2(3, 100); // 创建一个包含3个值为100的元素的链表std::list<int> list3(l2); // 创建一个l2的副本return 0;
}list元素的访问和修改
访问函数
front()：返回链表中第一个元素的引用back()：返回链表中最后一个元素的引用
修改函数
push_front()：在链表头部插入一个元素pop_front()：移除链表头部的元素push_back()：在链表尾部插入一个元素pop_back()：移除链表尾部的元素insert()：在指定位置插入一个元素- remove():删除指定的元素
clear()：移除链表中的所有元素- unique():除重
#include<iostream>
#include<list>
using namespace std;int main() {list<int> List;List.push_back(111);List.push_back(222);List.push_back(333);List.push_front(444);List.pop_back();List.pop_front();for (auto i : List) {cout << i << " ";}return 0;
}输出结果为111 222
list的基础操作
操作函数
merge()：将另一个有序链表other合并到当前链表中，合并后链表仍然有序sort()：对链表中的元素进行排序reverse()：反转链表中元素的顺序
容量函数
empty()：判断链表是否为空size()：返回链表中元素的数量
#include<iostream>
#include<list>
using namespace std;int main() {list<int> List;List.push_back(111);List.push_back(222);List.push_back(333);cout << "List size: " << List.size() << endl;while (!List.empty()) {cout << List.front() << endl;List.pop_front();}cout << List.empty() << endl;cout << "List size: " << List.size() << endl;return 0;
}C++List的迭代器
迭代器相关函数
begin()：返回指向链表第一个元素的迭代器end()：返回指向链表末尾（最后一个元素之后）的迭代器rbegin()：返回指向链表最后一个元素的反向迭代器rend()：返回指向链表开头（第一个元素之前）的反向迭代器
begin()和end()的使用示例
#include<iostream>
#include<list>
using namespace std;int main() {list<int> List;List.push_back(111);List.push_back(222);List.push_back(333);cout << *List.begin() << endl;cout << *--List.end() << endl;return 0;
}注意：.end并不指向最后一个节点，其指向为空，用--list.end可以获得链表List的最后的节点的地址。
List迭代器的使用
list< >::iterator __
Vlist<int>::iterator it = List.begin();创建一个名字叫 it 的迭代器，他指向名字叫 List 的链表的第一个节点
advance( , )
advance(it, 2);将名字叫 it 的迭代器正向移动2个节点。
这里是输出第3到第4的节点的数据
#include<iostream>
#include<list>
using namespace std;int main() {list<int> List;List.push_back(000);List.push_back(111);List.push_back(222);List.push_back(333);List.push_back(444);list<int>::iterator it = List.begin();advance(it, 2);for (int i = 0; i < 2; i++) {cout << *it << endl;it++;}return 0;
}