目录

链表

单向链表

单向链表结构与基本操作

插入节点

删除节点

搜索节点

遍历链表

反转链表

双向链表

双向链表结构与基本操作

节点定义和创建

插入节点

删除节点

搜索节点

遍历链表

转链表反

---

在开始讲线性表之前，先给各位读者重新回顾一下链表

链表

单向链表

单向链表是一种基本的数据结构，由一系列节点组成，每个节点包含两部分：数据域和指针域。数据域存储数据，而指针域存储指向列表中下一个节点的指针。单向链表的特点是数据元素的排列呈现单一方向，即每个节点仅指向下一个节点，直到最后一个节点的指针通常指向NULL，表示链表的结束。

单向链表结构与基本操作

在C语言中，单向链表的节点可以这样定义

typedef struct Node {int data;                 // 数据域，存储节点的数据struct Node* next;        // 指针域，指向下一个节点的指针
} Node;

 创建节点：初始化一个节点，通常需要提供数据，节点的next指针设置为NULL。

Node* createNode(int data) {Node* newNode = (Node*)malloc(sizeof(Node));if (newNode != NULL) {newNode->data = data;newNode->next = NULL;}return newNode;
}

插入节点

插入节点的基本过程：首先找到正确位置p，然后申请新结点t并对t的结点信息赋值，最后讲t插在p之后

插入到头部

void insertAtHead(Node** head, int data) {Node* newNode = createNode(data);newNode->next = *head;*head = newNode;
}

插入到尾部
在链表尾部插入节点需要遍历整个链表，直到找到最后一个节点。

void insertAtTail(Node** head, int data) {Node* newNode = createNode(data);if (*head == NULL) {*head = newNode;} else {Node* temp = *head;while (temp->next != NULL) {temp = temp->next;}temp->next = newNode;}
}

插入到特定位置

在链表的特定位置插入节点需要遍历链表直到达到指定位置的前一个节点。

void insertAtPosition(Node** head, int data, int position) {Node* newNode = createNode(data);if (position == 1) {insertAtHead(head, data);} else {Node* temp = *head;for (int i = 1; temp != NULL && i < position - 1; i++) {temp = temp->next;}if (temp == NULL) {printf("Position exceeds the length of the list.\n");} else {newNode->next = temp->next;temp->next = newNode;}}
}

删除节点

注意：删除一个节点后必须释放该节点的空间

删除头部节点

void deleteFromHead(Node** head) {if (*head != NULL) {Node* temp = *head;*head = (*head)->next;free(temp);}
}

删除尾部节点

删除尾部节点需要遍历整个链表以找到倒数第二个节点。

void deleteFromTail(Node** head) {if (*head == NULL) return;if ((*head)->next == NULL) {free(*head);*head = NULL;} else {Node* temp = *head;while (temp->next->next != NULL) {temp = temp->next;}free(temp->next);temp->next = NULL;}
}

删除特定位置的节点

删除特定位置的节点需要遍历链表直到找到该位置的前一个节点。

void deleteAtPosition(Node** head, int position) {if (*head == NULL) return;if (position == 1) {deleteFromHead(head);} else {Node* temp = *head;for (int i = 1; temp != NULL && i < position - 1; i++) {temp = temp->next;}if (temp == NULL || temp->next == NULL) {printf("Position exceeds the length of the list.\n");} else {Node* next = temp->next->next;free(temp->next);temp->next = next;}}
}

搜索节点

搜索节点涉及遍历链表以查找具有特定值的节点。

Node* search(Node* head, int key) {Node* current = head;while (current != NULL) {if (current->data == key) {return current;}current = current->next;}return NULL;
}

遍历链表

遍历链表是访问链表中每个节点的基本操作。

void printList(Node* head) {Node* current = head;while (current != NULL) {printf("%d -> ", current->data);current = current->next;}printf("NULL\n");
}

反转链表

反转链表需要改变每个节点的指针方向。

Node* reverseList(Node* head) {Node* prev = NULL;Node* current = head;Node* next = NULL;while (current != NULL) {next = current->next;current->next = prev;prev = current;current = next;}return prev;
}

双向链表

双向链表（Doubly Linked List）是一种链式数据结构，其中每个节点包含数据部分以及两个指针，分别指向前一个节点和后一个节点。这种结构允许从两个方向遍历链表：向前和向后。双向链表在插入和删除操作中比单向链表更加灵活，因为可以直接访问前驱和后继节点。

双向链表结构与基本操作

节点定义和创建

创建一个双向链表节点，需要初始化数据和两个指针：

typedef struct Node {int data;                 // 数据域，存储节点的数据struct Node* prev;        // 指向前一个节点的指针struct Node* next;        // 指向下一个节点的指针
} Node;Node* createNode(int data) {Node* newNode = (Node*)malloc(sizeof(Node));if (newNode != NULL) {newNode->data = data;newNode->prev = NULL;newNode->next = NULL;}return newNode;
}

插入节点

插入到头部

在头部插入节点，需要更新头节点的prev指针和新节点的next指针。

void insertAtHead(Node** head, int data) {Node* newNode = createNode(data);newNode->next = *head;if (*head != NULL) {(*head)->prev = newNode;}*head = newNode;
}

插入到尾部

在尾部插入节点，需要遍历链表找到尾节点，然后更新尾节点的next指针和新节点的prev指针。

void insertAtTail(Node** head, int data) {Node* newNode = createNode(data);if (*head == NULL) {*head = newNode;} else {Node* temp = *head;while (temp->next != NULL) {temp = temp->next;}temp->next = newNode;newNode->prev = temp;}
}

插入到特定位置

在特定位置插入节点，需要更新前一个节点的next指针和新节点的prev指针，以及新节点的next指针和后一个节点的prev指针。

void insertAtPosition(Node** head, int data, int position) {Node* newNode = createNode(data);if (position == 1) {insertAtHead(head, data);} else {Node* temp = *head;for (int i = 1; temp != NULL && i < position - 1; i++) {temp = temp->next;}if (temp == NULL) {printf("Position exceeds the length of the list.\n");} else {newNode->next = temp->next;newNode->prev = temp;if (temp->next != NULL) {temp->next->prev = newNode;}temp->next = newNode;}}
}

删除节点

删除头部节点：删除头部节点，需要更新头节点的prev指针和新头节点的next指针。

void deleteFromHead(Node** head) {if (*head == NULL) return;Node* temp = *head;*head = (*head)->next;if (*head != NULL) {(*head)->prev = NULL;}free(temp);
}

删除尾部节点：删除尾部节点，需要遍历链表找到倒数第二个节点，然后更新其next指针

void deleteFromTail(Node** head) {if (*head == NULL) return;if ((*head)->next == NULL) {free(*head);*head = NULL;} else {Node* temp = *head;while (temp->next->next != NULL) {temp = temp->next;}free(temp->next);temp->next = NULL;}
}

删除特定位置的节点：删除特定位置的节点，需要更新前一个节点的next指针和后一个节点的prev指针

void deleteAtPosition(Node** head, int position) {if (*head == NULL) return;if (position == 1) {deleteFromHead(head);} else {Node* temp = *head;for (int i = 1; temp != NULL && i < position; i++) {temp = temp->next;}if (temp == NULL) {printf("Position exceeds the length of the list.\n");} else {if (temp->prev != NULL) {temp->prev->next = temp->next;}if (temp->next != NULL) {temp->next->prev = temp->prev;}free(temp);}}
}

搜索节点

搜索节点，需要遍历链表直到找到具有特定值的节点。

Node* search(Node* head, int key) {Node* current = head;while (current != NULL) {if (current->data == key) {return current;}current = current->next;}return NULL;
}

遍历链表

向前遍历

void printListForward(Node* head) {Node* current = head;while (current != NULL) {printf("%d -> ", current->data);current = current->next;}printf("NULL\n");
}

向后遍历

void printListBackward(Node* head) {Node* current = head;while (current != NULL) {printf("%d <- ", current->data);current = current->prev;}printf("NULL\n");
}

转链表反

void reverseList(Node** head) {Node* temp = NULL;Node* current = *head;while (current != NULL) {temp = current->prev;current->prev = current->next;current->next = temp;current = current->prev;}if (temp != NULL) {*head = temp->prev;}
}