在C語言中,雙向鏈表可以通過結構體和指針來實現。一個典型的雙向鏈表節點結構體可以定義如下:
typedef struct Node {
int data;
struct Node* prev;
struct Node* next;
} Node;
在雙向鏈表中,每個節點包含一個數據域和兩個指針域,分別指向前一個節點和后一個節點。接下來可以定義一個雙向鏈表結構體來保存鏈表的頭節點和尾節點:
typedef struct {
Node* head;
Node* tail;
} DoublyLinkedList;
實現雙向鏈表的基本操作,包括初始化、插入節點、刪除節點等操作。以下是一個簡單的雙向鏈表的實現示例:
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* prev;
struct Node* next;
} Node;
typedef struct {
Node* head;
Node* tail;
} DoublyLinkedList;
DoublyLinkedList* createDoublyLinkedList() {
DoublyLinkedList* list = (DoublyLinkedList*)malloc(sizeof(DoublyLinkedList));
list->head = NULL;
list->tail = NULL;
return list;
}
void insertNode(DoublyLinkedList* list, int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->prev = NULL;
newNode->next = NULL;
if (list->head == NULL) {
list->head = newNode;
list->tail = newNode;
} else {
list->tail->next = newNode;
newNode->prev = list->tail;
list->tail = newNode;
}
}
void deleteNode(DoublyLinkedList* list, int data) {
Node* current = list->head;
while (current != NULL) {
if (current->data == data) {
if (current == list->head) {
list->head = current->next;
if (list->head != NULL) {
list->head->prev = NULL;
}
} else if (current == list->tail) {
list->tail = current->prev;
list->tail->next = NULL;
} else {
current->prev->next = current->next;
current->next->prev = current->prev;
}
free(current);
return;
}
current = current->next;
}
}
void printList(DoublyLinkedList* list) {
Node* current = list->head;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
int main() {
DoublyLinkedList* list = createDoublyLinkedList();
insertNode(list, 1);
insertNode(list, 2);
insertNode(list, 3);
printList(list);
deleteNode(list, 2);
printList(list);
return 0;
}
在上面的示例中,首先定義了Node和DoublyLinkedList結構體來表示雙向鏈表的節點和鏈表。然后實現了創建雙向鏈表、插入節點、刪除節點和打印鏈表的操作函數。在main函數中,創建一個雙向鏈表并對其進行操作,最后打印出鏈表的內容。