C语言数据结构 - 链表(双向链表实现)
#include <stdlib.h>
typedef int bool;
#define TRUE 1
#define FALSE 0
// 节点值类型(初始默认为int,后期可以改为需要的类型)
typedef int E;
// 链表节点结构体
typedef struct ListNode {
E ele; // 节点值
struct ListNode *prev; // 前驱节点
struct ListNode *next; // 后继节点
} Node;
// 链表结构体
typedef struct List {
Node *head; // 头节点
Node *tail; // 尾节点
int size; // 链表长度
} LinkedList;
/*!
* 初始化链表
* @return 链表指针
*/
LinkedList *init() {
// 申请内存
LinkedList *list = (LinkedList *) malloc(sizeof(LinkedList));
// 申请内存失败
if (list == NULL) {
return NULL;
}
// 初始化链表成员
list->head = NULL;
list->tail = NULL;
list->size = 0;
return list;
}
/*!
* 释放链表
* @param list 链表
*/
void destroy(LinkedList* list) {
Node* cur = list->head;
// 释放链表各个节点的内存
while(cur != NULL) {
Node* tmp = cur->next;
free(cur);
cur = tmp;
}
// 释放链表结构体内存
free(list);
}
/*!
* 插入元素
* @param list 链表
* @param index 插入位置
* @param ele 元素值
* @return 操作结果
*/
bool add(LinkedList *list, int index, E ele) {
// 注意:越界位置中尾巴位置list->size可以插入
if (index < 0 || index > list->size) {
return FALSE;
}
// 申请内存,创建一个新节点
Node *node = (Node *) malloc(sizeof(Node));
// 申请内存失败
if (node == NULL) {
return FALSE;
}
// 初始化节点
node->ele = ele;
node->prev = NULL;
node->next = NULL;
if (list->size == 0) {
// 空链表插入
list->head = node;
list->tail = node;
} else if (index == 0) {
// 头插
node->next = list->head;
list->head->prev = node;
list->head = node;
} else if (index == list->size) {
// 尾插
list->tail->next = node;
node->prev = list->tail;
list->tail = node;
} else {
// 中间位置插入
Node *cur = list->head;
for (int i = 0; i < index; i++) {
cur = cur->next;
}
Node *prevIndexNode = cur->prev;
prevIndexNode->next = node;
node->prev = prevIndexNode;
Node *nextIndexNode = cur;
node->next = nextIndexNode;
nextIndexNode->prev = node;
}
// 节点数+1
list->size++;
return TRUE;
}
/*!
* 删除元素
* @param list 链表
* @param index 指定删除位置
* @return 被删除的元素的地址(注意:返回值是特地开辟了一块内存来存储的,因此使用完该返回值,需要注意释放内存,避免内存泄露)
*/
E *delete(LinkedList *list, int index) {
// 越界位置不能删除
if (index < 0 || index >= list->size) {
return NULL;
}
// 指向将被删除节点
Node *removeNode;
if (list->size == 1) {
// 单节点链表删除唯一节点
removeNode = list->head;
list->head = NULL;
list->tail = NULL;
} else if (index == 0) {
// 头删
removeNode = list->head;
list->head = list->head->next;
list->head->prev = NULL;
} else if (index == list->size - 1) {
// 尾删
removeNode = list->tail;
list->tail = list->tail->prev;
list->tail->next = NULL;
} else {
// 中间位置删除
Node *cur = list->head;
for (int i = 0; i < index; i++) {
cur = cur->next;
}
removeNode = cur;
Node *prev = cur->prev;
Node *next = cur->next;
prev->next = next;
next->prev = prev;
}
// 链表节点个数-1
list->size--;
// 申请一块内存用于存放被删除节点的值
E *p = (E *) malloc(sizeof(E));
*p = removeNode->ele;
// 释放被删除节点的空间
free(removeNode);
return p;
}
/*!
* 修改元素
* @param list 链表
* @param index 指定修改位置
* @param ele 元素值
* @return 操作结果
*/
bool set(LinkedList *list, int index, E ele) {
// 越界位置无法操作
if (index < 0 || index >= list->size) {
return FALSE;
}
// 找到index位置的节点cur
Node *cur = list->head;
for (int i = 0; i < index; i++) {
cur = cur->next;
}
// 修改节点值
cur->ele = ele;
return TRUE;
}
/*!
* 查找元素
* @param list 链表
* @param index 查找位置
* @return 指定位置的元素值
*/
E *get(LinkedList *list, int index) {
// 越界位置无法操作
if (index < 0 || index >= list->size) {
return NULL;
}
// 找到index位置的节点cur
Node *cur = list->head;
for (int i = 0; i < index; i++) {
cur = cur->next;
}
// 返回元素值
return &cur->ele;
}
还没有评论,来说两句吧...