为了提高单向链表或者单向循环链表的访问速度，则可以在链表中的结点中再添加一个指针域，让新添加的指针域指向当前结点的直接前驱的地址，也就意味着一个结点中有两个指针域（prev+next），也被称为双向链表（DoubleLinked List）。
1.节点结构体
typedef int DataType_t;
typedef struct Node{DataType_t data;struct Node* next;struct Node* prev;
}Node_t;
2.创建双链表
- 新建一个头节点用于管理链表
Node_t* CreatedoubList()
{Node_t* head = (Node_t*)malloc(sizeof(Node_t));if(head == NULL){printf("内存分配失败\n");exit(-1);}head->next = NULL;head->prev = NULL;return head;
}
- 新建一个节点
Node_t* CreateNode(DataType_t value)
{Node_t* newNode = (Node_t*)malloc(sizeof(Node_t));if(newNode == NULL){printf("内存分配失败\n");exit(-1);}newNode->data = value;newNode->next = NULL;newNode->prev = NULL;return newNode;
}
3.向链表插入新节点
- 头插
bool AddNodeAtHead(Node_t* head, DataType_t value)
{Node_t* newNode = CreateNode(value);if(newNode == NULL){return false;}if(head->next == NULL){ // 双链表为空head->next = newNode;newNode->prev = head; //首节点的前驱指向头节点return true;}newNode->next = head->next; head->next->prev = newNode; //原首节点的前驱指向新节点head->next = newNode;newNode->prev = head; //新节点的前驱指向头节点return true;
}
- 尾插
bool AddNodeAtTail(Node_t* head, DataType_t value)
{Node_t* newNode = CreateNode(value);if(newNode == NULL){return false;}if(head->next == NULL){ // 双链表为空head->next = newNode;newNode->prev = head;return true;}Node_t* current = head;while(current->next){ //遍历完成current就是末尾节点current = current->next;}current->next = newNode;newNode->prev = current; //当前节点的前驱指向原来尾节点return true;
}
- 指定位置插入
bool InsertNodeAtPosition(Node_t* head, int position, DataType_t value)
{if(position < 1){ //首结点开始算1printf("position should be greater than 1");return false;}Node_t* newNode = CreateNode(value);if(newNode == NULL){return false;}Node_t* current = head;for(int i=1;i<position;i++){ //找第position节点的前驱current = current->next;if(current == NULL){free(newNode);printf("插入位置超出双链表长度\n");return false;}}newNode->next = current->next; if(current->next) //如果不是尾节点current->next->prev = newNode;current->next = newNode;newNode->prev = current;return true;
}
4.删除链表节点
- 头删
bool DeleteHeadNode(Node_t* head)
{if(head->next == NULL){ // 双链表为空printf("双链表为空，无法删除节点\n");return false;}Node_t* temp = head->next;head->next = temp->next;if(temp->next) //只有一个节点的情况temp->next->prev = head;free(temp);return true;
}
- 尾删
bool DeleteTailNode(Node_t* head)
{if(head->next == NULL){ // 双链表为空printf("双链表为空，无法删除节点\n");return false;}Node_t* current = head;while(current->next->next){ // 找到倒数第二个节点current = current->next;}Node_t* temp = current->next;current->next = NULL;free(temp);return true;
}
- 删除指定值的节点
bool DeleteNodeByValue(Node_t* head, DataType_t value)
{if(head->next == NULL){ // 双链表为空printf("双链表为空，无法删除节点\n");return false;}Node_t* current = head;while(current->next && current->next->data != value){current = current->next;}if(current->next == NULL){ // 未找到值为value的节点printf("未找到值为%d的节点\n", value);return false;}Node_t* temp = current->next;current->next = temp->next;if(temp->next) //如果不是尾节点temp->next->prev = current;free(temp);return true;
}
5.遍历输出链表
bool PrintList(Node_t* head)
{if(head->next == NULL){ // 双链表为空printf("双链表为空\n");return false;}Node_t* current = head->next;while(current){printf("%d -> ", current->data); current = current->next; }printf("NULL\n");return true;
}