一、链表定义

二、链表分类

三、链表操作

四、单向链表

1.链表定义

2.插入操作

3.删除操作

4.修改操作

5.查找操作

五、双向链表

1.链表定义

2.插入操作

3.删除操作

4.修改操作

5.查找操作

一、链表定义

链表是一种基本的数据结构，它由一系列节点组成，每个节点包含一个值和指向下一个节点的指针。链表的特点是可以动态添加和删除节点，而不需要预先知道数据的数量。与数组不同，链表中的节点不一定是连续的存储空间，因此可以有效地利用内存空间。

二、链表分类

链表可以分为三种类型：

单向链表：每个节点只有一个指针指向下一个节点，最后一个节点的指针指向NULL。
双向链表：每个节点有两个指针，分别指向上一个节点和下一个节点，可以在O(1)时间内实现向前和向后遍历。
循环链表：在单向或双向链表的基础上，将最后一个节点的指针指向头节点，形成一个环。

三、链表操作

链表的操作包括插入、删除、查找、遍历等。

插入操作：可以在链表头或尾插入节点，也可以在指定位置插入节点。
删除操作：可以删除指定节点或按照值删除节点。
查找操作：可以查找指定节点或按照值查找节点。
遍历操作：可以遍历整个链表，输出每个节点的值或执行其他操作。

链表的优点是可以动态添加和删除节点，因此非常适用于需要频繁插入和删除数据的场景。链表的缺点是访问操作的时间复杂度为O(n)，而且需要额外的空间存储节点的指针，因此在需要频繁访问数据的场景中，效率可能不如数组。

链表在计算机科学中有广泛的应用，例如操作系统中的进程链表、文件系统中的目录链表、图论中的邻接表等。在C语言中，链表常常用于实现动态内存分配、函数调用栈、多项式运算等问题。

四、单向链表

单向链表是由若干个节点组成的数据结构，每个节点包含两个部分：数据域和指针域。数据域存储节点的数据，指针域存储下一个节点的地址。

1.链表定义

单向链表定义如下：

struct ListNode {int val;struct ListNode* next;
};

2.插入操作

链表的插入操作可以在链表的头部、尾部或指定位置插入节点。具体实现如下：

// 在头部插入节点
struct ListNode* insertAtHead(struct ListNode* head, int val) {struct ListNode* new_node = (struct ListNode*)malloc(sizeof(struct ListNode));new_node->val = val;new_node->next = head;return new_node;
}// 在尾部插入节点
struct ListNode* insertAtTail(struct ListNode* head, int val) {struct ListNode* new_node = (struct ListNode*)malloc(sizeof(struct ListNode));new_node->val = val;new_node->next = NULL;if (head == NULL) {return new_node;}struct ListNode* p = head;while (p->next != NULL) {p = p->next;}p->next = new_node;return head;
}// 在指定位置插入节点
struct ListNode* insertAtIndex(struct ListNode* head, int index, int val) {int i = 0;struct ListNode* new_node = (struct ListNode*)malloc(sizeof(struct ListNode));new_node->val = val;if (index == 0) {new_node->next = head;return new_node;}struct ListNode* p = head;while (i < index - 1 && p != NULL) {p = p->next;i++;}if (p == NULL) {free(new_node);return head;}new_node->next = p->next;p->next = new_node;return head;
}

3.删除操作

链表的删除操作可以删除指定位置或指定值的节点。具体实现如下：

// 删除指定位置的节点
struct ListNode* deleteAtIndex(struct ListNode* head, int index) {int i = 0;if (head == NULL) {return NULL;}if (index == 0) {struct ListNode* temp = head;head = head->next;free(temp);return head;}struct ListNode* p = head;while (i < index - 1 && p != NULL) {p = p->next;i++;}if (p == NULL || p->next == NULL) {return head;}struct ListNode* temp = p->next;p->next = p->next->next;free(temp);return head;
}
// 删除指定值的节点
struct ListNode* deleteNode(struct ListNode* head, int val) {struct ListNode* p = head;struct ListNode* prev = NULL;while (p != NULL && p->val != val) {prev = p;p = p->next;}if (p == NULL) {return head;}if (prev == NULL) {head = head->next;} else {prev->next = p->next;}free(p);return head;
}

4.修改操作

链表的修改操作可以修改指定位置或指定值的节点的值。具体实现如下：

// 修改指定位置的节点的值
struct ListNode* modifyAtIndex(struct ListNode* head, int index, int val) {struct ListNode* p = head;int i = 0;while (i < index && p != NULL) {p = p->next;i++;}if (p == NULL) {return head;}p->val = val;return head;
}// 修改指定值的节点的值
struct ListNode* modifyNode(struct ListNode* head, int old_val, int new_val) {struct ListNode* p = head;while (p != NULL && p->val != old_val) {p = p->next;}if (p == NULL) {return head;}p->val = new_val;return head;
}

5.查找操作

链表的查找操作可以查找指定位置或指定值的节点。具体实现如下：

// 查找指定位置的节点的值
int getValAtIndex(struct ListNode* head, int index) {struct ListNode* p = head;int i = 0;while (i < index && p != NULL) {p = p->next;i++;}if (p == NULL) {return -1;}return p->val;
}// 查找指定值的节点的位置
int getIndexByVal(struct ListNode* head, int val) {struct ListNode* p = head;int i = 0;while (p != NULL && p->val != val) {p = p->next;i++;}if (p == NULL) {return -1;}return i;
}

以上是链表的基本操作，实现时需要注意空指针和越界等问题。

五、双向链表

双向链表和单向链表的不同在于每个节点有两个指针，分别指向前驱节点和后继节点。双向链表的优点是可以实现双向遍历和O(1)的删除操作，缺点是每个节点需要额外的一个指针。

1.链表定义

双向链表定义如下：

struct ListNode {int val;struct ListNode* prev;struct ListNode* next;
};

2.插入操作

双向链表的插入操作可以在指定位置前面或后面插入节点，具体实现如下：

// 在指定位置前面插入节点
struct ListNode* insertBefore(struct ListNode* head, int index, int val) {struct ListNode* p = head;int i = 0;while (i < index && p != NULL) {p = p->next;i++;}if (p == NULL) {return head;}struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));node->val = val;node->prev = p->prev;node->next = p;if (p->prev != NULL) {p->prev->next = node;} else {head = node;}p->prev = node;return head;
}// 在指定位置后面插入节点
struct ListNode* insertAfter(struct ListNode* head, int index, int val) {struct ListNode* p = head;int i = 0;while (i < index && p != NULL) {p = p->next;i++;}if (p == NULL) {return head;}struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));node->val = val;node->prev = p;node->next = p->next;if (p->next != NULL) {p->next->prev = node;}p->next = node;return head;
}

3.删除操作

双向链表的删除操作可以删除指定位置或指定值的节点，具体实现如下：

// 删除指定位置的节点
struct ListNode* deleteAtIndex(struct ListNode* head, int index) {struct ListNode* p = head;int i = 0;while (i < index && p != NULL) {p = p->next;i++;}if (p == NULL) {return head;}if (p->prev != NULL) {p->prev->next = p->next;} else {head = p->next;}if (p->next != NULL) {p->next->prev = p->prev;}free(p);return head;
}// 删除指定值的节点
struct ListNode* deleteNode(struct ListNode* head, int val) {struct ListNode* p = head;while (p != NULL && p->val != val) {p = p->next;}if (p == NULL) {return head;}if (p->prev != NULL) {p->prev->next = p->next;} else {head = p->next;}if (p->next != NULL) {p->next->prev = p->prev;}free(p);return head;
}

4.修改操作

双向链表的修改操作可以直接修改指定节点的值，具体实现如下：

// 修改指定位置的节点值
struct ListNode* updateAtIndex(struct ListNode* head, int index, int val) {struct ListNode* p = head;int i = 0;while (i < index && p != NULL) {p = p->next;i++;}if (p == NULL) {return head;}p->val = val;return head;
}

5.查找操作

双向链表的查找操作可以按位置或按值查找，具体实现如下：

// 按位置查找节点
struct ListNode* getNodeAtIndex(struct ListNode* head, int index) {struct ListNode* p = head;int i = 0;while (i < index && p != NULL) {p = p->next;i++;}return p;
}// 按值查找节点
struct ListNode* getNodeByValue(struct ListNode* head, int val) {struct ListNode* p = head;while (p != NULL && p->val != val) {p = p->next;}return p;
}

以上是双向链表的增删改查操作的实现，可以根据需要进行调用。需要注意的是，在使用完链表后要及时释放内存，避免内存泄漏。

如果觉得文章写的还不错，麻烦点赞，收藏加关注哦！