核心代码:
int insertDoubleLinkedList(DoubleLinkedList *list, int index, int value) {
if (list == NULL || list->head == NULL || list->tail == NULL) {
return -1;
}
// 当一个元素都没有的时候,或者index=size的时候,是支持插入的
if (index < 0 || index > list->size) {
return -1;
}
// 创建节点
DoubleLinkedListNode *newNode = newDoubleLinkedListNode(value);
// 元素个数增加
list->size++;
// 插入到头部
if (index == 0) {
DoubleLinkedListNode *oldNode = list->head->next;
list->head->next = newNode;
newNode->prev = list->head;
newNode->next = oldNode;
oldNode->prev = newNode;
return 0;
}
// 插入到尾部
if (index == list->size) {
DoubleLinkedListNode *oldNode = list->tail->prev;
oldNode->next = newNode;
newNode->prev = oldNode;
newNode->next = list->tail;
list->tail->prev = newNode;
return list->size;
}
// 插入到中间
int i = 0;
DoubleLinkedListNode *current = list->head->next;
while (i < index) {
i++;
current = current->next;
}
// 此时,current就是索引位置的节点,将该节点往后移动
DoubleLinkedListNode *oldPrev = current->prev;
oldPrev->next = newNode;
newNode->prev = oldPrev;
newNode->next = current;
current->prev = newNode;
// 返回
return index;
}
double_linked_list.h
#ifndef ZDPC_ALGORITHM_DEV_DOUBLE_LINKED_LIST_H
#define ZDPC_ALGORITHM_DEV_DOUBLE_LINKED_LIST_H
// 公共头文件
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
// 双向链表的节点
typedef struct doubleLinkedListNode {
int data;
struct doubleLinkedListNode *next; // 下一个节点
struct doubleLinkedListNode *prev; // 上一个节点
} DoubleLinkedListNode;
// 双向链表
typedef struct doubleLinkedList {
DoubleLinkedListNode *head; // 头节点
DoubleLinkedListNode *tail; // 尾节点
int size; // 节点的个数
} DoubleLinkedList;
extern DoubleLinkedList *newDoubleLinkedList(); // 创建双向链表
extern void freeDoubleLinkedList(DoubleLinkedList *list); // 释放双向链表内存
extern int isEmptyDoubleLinkedList(DoubleLinkedList *list); // 判断是否为空链表
extern int sizeDoubleLinkedList(DoubleLinkedList *list); // 获取链表的元素个数
extern void printDoubleLinkedList(DoubleLinkedList *list); // 打印链表的内容
extern void appendDoubleLinkedList(DoubleLinkedList *list, int value); // 将元素添加到链表末尾
extern int removeDoubleLinkedList(DoubleLinkedList *list, int value); // 从链表中移除元素,成功返回其索引,失败返回-1
extern int insertDoubleLinkedList(DoubleLinkedList *list, int index, int value); // 将数据插入到链表指定索引位置,成功返回其索引,失败返回-1
#endif //ZDPC_ALGORITHM_DEV_DOUBLE_LINKED_LIST_H
double_linked_list.c
#include "double_linked_list.h"
// 创建头节点
DoubleLinkedListNode *newDoubleLinkedListNode(int value) {
// 申请节点的空间
DoubleLinkedListNode *node = malloc(sizeof(DoubleLinkedListNode));
// 初始化
node->next = NULL;
node->prev = NULL;
node->data = value;
// 返回
return node;
}
// 创建双向链表
DoubleLinkedList *newDoubleLinkedList() {
// 申请链表的内存
DoubleLinkedList *list = malloc(sizeof(DoubleLinkedList));
// 头节点
DoubleLinkedListNode *head = newDoubleLinkedListNode(0);
// 尾结点
DoubleLinkedListNode *tail = newDoubleLinkedListNode(0);
// 初始化
list->head = head;
list->tail = tail;
list->size = 0;
// 关系
list->head->next = list->tail;
list->tail->prev = list->head;
// 返回
return list;
}
// 释放双向链表内存
void freeDoubleLinkedList(DoubleLinkedList *list) {
// 释放节点内存
DoubleLinkedListNode *node = list->head->next;
while (node->next != list->tail) {
DoubleLinkedListNode *next = node->next;
free(node);
node = next;
}
// 释放首尾节点的内存
free(list->head);
free(list->tail);
// 释放链表内存
free(list);
}
// 判断是否为空链表
int isEmptyDoubleLinkedList(DoubleLinkedList *list) {
return list != NULL && list->head->next == list->tail;
}
// 获取链表的元素个数
int sizeDoubleLinkedList(DoubleLinkedList *list) {
return list->size;
}
// 打印链表的内容
void printDoubleLinkedList(DoubleLinkedList *list) {
if (list == NULL) {
return;
}
if (list->head == NULL || list->head->next == NULL) {
return;
}
DoubleLinkedListNode *current = list->head->next;
while (current != list->tail) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
// 将元素添加到链表末尾
void appendDoubleLinkedList(DoubleLinkedList *list, int value) {
insertDoubleLinkedList(list, list->size, value);
}
// 弃用旧的追加方法
void appendDoubleLinkedList2(DoubleLinkedList *list, int value) {
if (list == NULL || list->head == NULL || list->tail == NULL) {
return;
}
// 构造新节点
DoubleLinkedListNode *node = newDoubleLinkedListNode(value);
// 插入到末尾
DoubleLinkedListNode *oldPrev = list->tail->prev;
oldPrev->next = node;
node->prev = oldPrev;
node->next = list->tail;
list->tail->prev = node;
// 元素个数增加
list->size++;
}
// 从链表中移除元素
int removeDoubleLinkedList(DoubleLinkedList *list, int value) {
int index = -1;
if (list == NULL || list->head == NULL || list->tail == NULL || list->size <= 0) {
return index;
}
// 查找对应的元素
DoubleLinkedListNode *current = list->head->next;
while (current != list->tail) {
index++;
if (current->data == value) {
break;
}
current = current->next;
}
// 如果找到了,则删除
if (index >= 0 && index < list->size) {
DoubleLinkedListNode *oldPrev = current->prev;
DoubleLinkedListNode *oldNext = current->next;
oldPrev->next = oldNext;
oldNext->prev = oldPrev;
free(current); // 记得释放节点的内存
}
// 元素个数减少
list->size--;
// 返回
return index;
}
// 将数据插入到链表指定索引位置
int insertDoubleLinkedList(DoubleLinkedList *list, int index, int value) {
if (list == NULL || list->head == NULL || list->tail == NULL) {
return -1;
}
// 当一个元素都没有的时候,或者index=size的时候,是支持插入的
if (index < 0 || index > list->size) {
return -1;
}
// 创建节点
DoubleLinkedListNode *newNode = newDoubleLinkedListNode(value);
// 元素个数增加
list->size++;
// 插入到头部
if (index == 0) {
DoubleLinkedListNode *oldNode = list->head->next;
list->head->next = newNode;
newNode->prev = list->head;
newNode->next = oldNode;
oldNode->prev = newNode;
return 0;
}
// 插入到尾部
if (index == list->size) {
DoubleLinkedListNode *oldNode = list->tail->prev;
oldNode->next = newNode;
newNode->prev = oldNode;
newNode->next = list->tail;
list->tail->prev = newNode;
return list->size;
}
// 插入到中间
int i = 0;
DoubleLinkedListNode *current = list->head->next;
while (i < index) {
i++;
current = current->next;
}
// 此时,current就是索引位置的节点,将该节点往后移动
DoubleLinkedListNode *oldPrev = current->prev;
oldPrev->next = newNode;
newNode->prev = oldPrev;
newNode->next = current;
current->prev = newNode;
// 返回
return index;
}
main.c
#include "double_linked_list.h"
int main(void) {
// 创建链表
DoubleLinkedList *list = newDoubleLinkedList();
// 添加数据
appendDoubleLinkedList(list, 11);
appendDoubleLinkedList(list, 22);
appendDoubleLinkedList(list, 33);
printDoubleLinkedList(list);
// 插入到前面
insertDoubleLinkedList(list,0,333);
printDoubleLinkedList(list);
// 插入到后面
insertDoubleLinkedList(list,list->size,333);
printDoubleLinkedList(list);
// 插入到中间
insertDoubleLinkedList(list,2,333);
printDoubleLinkedList(list);
printf("元素个数:%d\n",list->size);
// 释放链表
freeDoubleLinkedList(list);
return 0;
}
输出:
11 22 33
333 11 22 33
333 11 22 33 333
333 11 333 22 33 333
元素个数:6