C和C++（list）的链表初步

 链表是构建其他复杂数据结构的基础，如栈、队列、图和哈希表等。通过对链表进行适当的扩展和修改，可以实现这些数据结构的功能。想学算法，数据结构，不会链表是万万不行的。这篇笔记是一名小白在学习时整理的。

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;
}