1.理解C 语言里是如何构造出链表的
2.链表增加元素，首部、中间和尾部分别会有什么问题，该如何处理？
3.链表删除元素，首部、中间和尾部分别会有什么问题，该如何处理？
4.双向链表是如何构造的，如何实现元素的插入和删除。
一、链表是什么
链表是一种常见的数据结构，由一系列节点（结点）组成，每个节点都含有数据以及一个指向下一个节点的指针（引用），形成链式结构。它可以动态地分配内存空间，在插入或删除节点时只需要调整相邻节点的指针，而不需要移动节点本身，因此具有较好的插入和删除性能。👉🤖
可以试着把链表想象成火车
一个类似于火车一样的数据结构，里面存储的元素（例如整数、字符串、对象）是相互连接用 “节点” 来表示的（就类似于火车的车厢），每个节点都有一个指向下一个节点（火车车厢连着下一个火车）。这种结构允许我们通过单向或双向遍历来访问和操作数据。
一节火车车厢分为两部分，前半部分存放元素，后半部分存放地址。打开前门拿数据，打开后门则知道下一个数据存在哪。
二、怎么定义链表（C语言版）
在 C 语言中，链表可以通过定义结构体和指针来实现。
1. 定义链表结构体
一个简单的链表结构体可以像这样定义：
typedef struct Node{
int data;
struct Node *next;
} Node;其中，每个节点包括一个整型数据 data 和一个指向下一个节点的指针 next。定义好结构体后，我们就可以开始创建链表。
2. 创建头节点
首先需要定义一个头节点，通常把头节点的指针命名为 head，表示链表的起点。然后可以通过动态内存分配函数 malloc 在堆空间中为链表节点分配内存。
例如，可以先创建一个头节点：
typedef struct Node{
int data;
struct Node *next;
} Node;这段代码创建了一个头节点，它的 next 指针指向空（NULL）节点，表示链表目前为空。
3. 插入新节点
接下来，可以定义一个函数来向链表中插入新节点。例如，可以定义一个函数 addNode，它接受头节点和待插入的节点数据，并将新节点添加到链表尾部：
void addNode(Node *head, int data) {
Node *newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
Node *p = head;
while (p->next != NULL) {
p = p->next;
}
p->next = newNode;
}这段代码创建了一个新节点，设置它的数据为传入的参数 data，并将 next 指针设置为空。然后从头节点开始遍历链表，直到找到最后一个节点，再将新节点插入到链表尾部。通过不断重复调用 addNode 函数，就可以创建一个完整的链表了。
4. 释放所有节点
注意，在使用完链表后，需要释放所有节点的内存，避免内存泄漏。可以定义一个清空链表的函数 clearList，遍历整个链表并释放每个节点的内存：
void clearList(Node *head) {
Node *p = head;
while (head != NULL) {
p = head;
head = head->next;
free(p);
}
}这段代码遍历整个链表，逐个释放每个节点的内存，并将头节点的指针设置为空。
三、怎么定义链表（C++版）
在C++中，可以通过定义一个节点的结构体来构造一个链表。每个节点包含一个数据和一个指向下一个节点的指针。具体步骤如下：
1. 定义节点结构体 Node
struct Node {
int data; // 节点存储的数据
Node* next; // 指向下一个节点的指针
};2. 构造链表
首先需要定义头节点 head。然后循环添加节点，创建节点时使用 new 运算符分配内存，并将前一个节点（初始为头节点）的 next 指向新节点，最后将新节点设置为前一个节点，继续循环直到所有节点都添加完毕。
Node* head = new Node; // 定义头节点
head->next = nullptr; // 头节点的 next 指针为空
Node* p = head; // p 初始指向头节点
for (int i = 0; i < n; i++) {
Node* q = new Node; // 创建新节点
q->data = arr[i]; // 节点存储数据
q->next = nullptr; // 新节点的 next 指针为空
p->next = q; // 前一个节点的 next 指针指向新节点
p = q; // 将新节点设置为前一个节点
}3. 遍历链表
遍历链表时，从头节点开始沿着 next 指针遍历每个节点，直到 next 指针为空。
Node* p = head->next; // p 初始指向第一个数据节点
while (p != nullptr) {
// 处理节点数据...
p = p->next; // p 指向下一个节点
}四、如何插入链表
在这里中只考虑单链表的问题，双向链表那就是另外的问题了
链表的插入看似简单，实则有很多坑。在不同位置的插入会有不同的写法。
1. 头插
当在链表首部增加元素时，需要重新设置头指针。在C语言中，可以新建一个节点，将其指向原来的链表头，再将头指针指向这个新节点。代码如下：
//新建一个节点
struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
newNode->val = val;
newNode->next = NULL;
//将新节点的指针指向旧链表头
newNode->next = head;
//设置新链表头的指针
head = newNode;在C++中可以使用STL中的链表容器，使用push_front()函数可以在链表头部添加元素。代码如下：
std::list<int> mylist { 1, 2, 3 };
mylist.push_front(0); // 0 1 2 32. 中间插入
当在链表中间增加元素时，需要注意插入位置的前一个节点的指针需要正确指向插入的新节点。在C语言中，可以使用一个指针变量遍历链表，找到需要插入的位置，再进行插入操作，代码如下：
struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
newNode->val = val;
newNode->next = NULL;
struct ListNode* p = head;
//找到插入位置的前一个节点
while (p->next && p->next->val < val) {
p = p->next;
}
//插入新节点
newNode->next = p->next;
p->next = newNode;在C++中也可以使用STL中的链表容器，使用insert()函数可以在指定位置插入元素。代码如下：
std::list<int> mylist { 1, 2, 4, 5 };
std::list<int>::iterator it = mylist.begin();
++it;
mylist.insert (it,3); // 1 2 3 4 53. 尾插
当在链表尾部增加元素时，需要更新链表的尾指针，否则会导致无法访问新加入的节点。在C语言中，可以使用一个指针变量遍历链表，找到链表尾部的指针，再将其指向新节点。在C++中可以使用STL中的链表容器，使用push_back()函数可以在链表尾部添加元素。
C语言代码如下：
struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
newNode->val = val;
newNode->next = NULL;
struct ListNode* p = head;
//找到链表尾部节点
while (p->next) {
p = p->next;
}
//将尾节点指针指向新节点
p->next = newNode;C++代码如下：
std::list<int> mylist { 1, 2, 3 };
mylist.push_back(4); // 1 2 3 44. 总结
当链表增加元素时，分别在首部、中间和尾部可能会遇到以下问题：
- 首部：插入节点成为新的头节点时，需要更新链表的头指针，否则会丢失原有头节点的引用。
- 中间：在中间插入节点时，需要注意新节点的指针需要正确地指向其前面和后面的节点，这样才能保证链表的完整性。
- 尾部：插入节点成为新的尾节点时，需要更新链表的尾指针，否则会导致无法访问新加入的节点。
针对以上问题的解决方案如下：
- 对于头节点的插入，可以先将新节点的指针指向原有的头节点，然后再将链表的头指针更新为新节点。
- 在中间插入节点时，需要找到新节点需要插入到哪两个节点之间，然后将新节点的指针指向前后两个节点即可。
- 对于尾节点的插入，可以先将新节点的指针指向null，然后再将链表的尾指针更新为新节点。
同时要注意边界条件的判断，避免越界等问题的发生。
五、如何删除链表
链表的删除和链表的插入一样，看似简单，实则有很多坑。在不同位置的删除会有不同的写法。按照位置的不同，我们分为首部、中部和尾部三个部分来讲。
1. 删除头节点
当删除链表的头节点时，需要特别处理。我们需要记录头节点的下一个节点，将头节点释放并把头指针改变为下一个节点。需要注意的是，当链表只有一个节点时，删除后头指针应该变为NULL。
代码实现（C语言版）：
typedef struct ListNode {
int val;
struct ListNode *next;
} ListNode;
ListNode* removeFirstNode(ListNode *head) {
if (head == NULL) {
return NULL;
}
ListNode *nextNode = head->next;
free(head);
head = nextNode;
return head;
}代码实现（C++版）：
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* removeFirstNode(ListNode* head) {
if (head == NULL) {
return NULL;
}
ListNode *nextNode = head->next;
delete head;
head = nextNode;
return head;
}2. 删除中间节点
如果要删除的节点在链表的中间，我们需要找到该节点的前一个节点，将前一个节点的指针连接到要删除节点的下一个节点，释放掉要删除的节点。
代码实现（C语言版）：
ListNode* removeNode(ListNode* head, int val) {
if (head == NULL) {
return NULL;
}
ListNode *curNode = head;
ListNode *preNode = NULL;
while (curNode != NULL && curNode->val != val) {
preNode = curNode;
curNode = curNode->next;
}
if (curNode == NULL) {
return head;
}
if (preNode == NULL) {
//需要删除的节点是头节点
head = curNode->next;
} else {
preNode->next = curNode->next;
}
free(curNode);
curNode = NULL;
return head;
}代码实现（C++版）：
ListNode* removeNode(ListNode* head, int val) {
if (head == NULL) {
return NULL;
}
ListNode *curNode = head;
ListNode *preNode = NULL;
while (curNode != NULL && curNode->val != val) {
preNode = curNode;
curNode = curNode->next;
}
if (curNode == NULL) {
return head;
}
if (preNode == NULL) {
//需要删除的节点是头节点
head = curNode->next;
} else {
preNode->next = curNode->next;
}
delete curNode;
curNode = NULL;
return head;
}3. 删除尾节点
删除尾节点也需要特殊处理，需要找到尾节点的前一个节点，并将其指向NULL，最后释放掉尾节点。
代码实现（C语言版）：
ListNode* removeLastNode(ListNode* head) {
if (head == NULL) {
return NULL;
}
if (head->next == NULL) {
//只有一个节点，删除后链表为空
free(head);
head = NULL;
return NULL;
}
ListNode *curNode = head;
ListNode *preNode = NULL;
while (curNode->next != NULL) {
preNode = curNode;
curNode = curNode->next;
}
preNode->next = NULL;
free(curNode);
curNode = NULL;
return head;
}代码实现（C++版）：
ListNode* removeLastNode(ListNode* head) {
if (head == NULL) {
return NULL;
}
if (head->next == NULL) {
//只有一个节点，删除后链表为空
delete head;
head = NULL;
return NULL;
}
ListNode *curNode = head;
ListNode *preNode = NULL;
while (curNode->next != NULL) {
preNode = curNode;
curNode = curNode->next;
}
preNode->next = NULL;
delete curNode;
curNode = NULL;
return head;
}注释说明：
以上是C和C++两种语言的链表删除节点的实现方法。
链表的操作要注意多个边界条件。在代码实现时，需要考虑链表为空、链表只有一个节点等特殊情况。
4. 总结
对于链表删除元素，不同位置可能会有不同的问题：
- 首部删除：需要将头指针指向下一个元素，同时释放被删除元素的内存空间。
- 中间删除：需要找到需要删除元素的前一个元素，将其指向需要删除元素的下一个元素，同时释放被删除元素的内存空间。
- 尾部删除：需要找到需要删除元素的前一个元素，并将其指向NULL，同时释放被删除元素的内存空间。
六、如何构造双向链表
双向链表是由多个节点构成的数据结构，每个节点包含两个指针，一个指向前驱节点（previous），一个指向后继节点（next），并且每个节点还包含一个数据域存储具体的数据。
双向链表的构造可以分为以下几个步骤：
1. 定义节点结构体
首先需要定义一个节点结构体，包含前驱节点的指针、数据域和后继节点的指针。
2. 初始化头节点和尾节点
创建一个空的双向链表需要初始化头节点和尾节点，可以让它们都指向 NULL 或者让它们相互指向。
3. 添加节点
在双向链表中插入、删除元素时，需要连接相邻节点之间的指针，具体实现可以通过修改前一个节点的 next 指针、后一个节点的 previous 指针和新插入节点的 previous 和 next 指针来完成。
4. 遍历链表
双向链表可以从前向后遍历，也可以从后向前遍历，只需要根据需要选择不同的指针。
5. 插入与删除
双向链表的插入与删除需要注意以下几点：
- 插入节点时，需要注意新节点的前驱和后继节点的更新，以及边界情况的处理。
- 删除节点时，需要注意被删除节点前后节点的更新，以及被删除节点的内存释放问题。
- 双向链表相较于单向链表，需要考虑前驱节点是否存在，因此在处理头节点和尾节点时需要特别注意。
- 插入节点和删除节点时，需要注意链表的头尾指针是否需要更新，根据需要进行处理。
- 在进行插入和删除操作时，要考虑链表是否为空或只有一个节点的特殊情况。
需要注意的是，在处理双向链表的插入和删除操作时，要特别注意节点的前后关系、边界情况以及链表指针的更新，这样才能保证操作的正确性和高效性。💡
6. 代码实现
双向链表是一种常见的数据结构，它通过链接每个节点的前驱和后继节点形成一个链表。下面分别用C语言和C++展示如何构造双向链表，并实现元素的插入和删除。
C语言实现：
// 双向链表节点结构体
typedef struct Node {
int data; // 数据域
struct Node* prev; // 前驱节点指针
struct Node* next; // 后继节点指针
} Node;
// 双向链表结构体
typedef struct List {
Node* head; // 头节点指针
Node* tail; // 尾节点指针
} List;
// 在双向链表末尾添加一个元素
void insert(List* list, int data) {
Node* node = (Node*)malloc(sizeof(Node));
node->data = data;
node->prev = list->tail;
node->next = NULL;
if (list->tail != NULL) {
list->tail->next = node;
} else {
list->head = node;
}
list->tail = node;
}
// 从双向链表中删除一个元素
void remove(List* list, int data) {
Node* cur = list->head;
while (cur != NULL && cur->data != data) {
cur = cur->next;
}
if (cur == NULL) {
return;
}
if (cur->prev != NULL) {
cur->prev->next = cur->next;
} else {
list->head = cur->next;
}
if (cur->next != NULL) {
cur->next->prev = cur->prev;
} else {
list->tail = cur->prev;
}
free(cur);
}C++实现：
通过以上代码示例，可以看出，双向链表的构造需要定义一个节点结构体或类，包含数据域、前驱指针和后继指针，然后定义一个链表结构体或类，包含头节点和尾节点指针。元素的插入和删除操作都是基于双向链表节点结构体或类实现的，需要考虑前驱指针和后继指针的更新。
七、全文总结
链表在数据结构中十分重要，虽然只考链表的算法题比较少，但是常考且重要。
链表是一种数据结构，它由节点组成，每个节点包含一个data域和一个next域，其中data域存储数据，next域指向下一个节点。链表使用指针连接各个节点，在内存中不要求连续分配空间。文章来源：https://www.toymoban.com/news/detail-608601.html
链表的要点总结如下：文章来源地址https://www.toymoban.com/news/detail-608601.html
- 链表有头结点和尾节点，头结点不存储数据；
- 链表的操作包括插入、删除、查找，其中插入和删除比较容易产生内存泄漏或者野指针的问题，需要仔细考虑；
- 链表的插入有头插法和尾插法，删除有按节点值删除和按节点位置删除；
- 可以使用快慢指针的方法来查找链表中的环，也可以使用递归的方法反转链表；
- 在实际使用中，需要注意链表的长度和节点数，在大数据情况下，链表的操作复杂度变高。
到了这里，关于算法村第一关黄铜｜链表｜单链表与双向链表（c语言&c++实现）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
