链表 数据结构

链表, 一种抽象数据类型(ADT)的存储方式.

通过链式的动态存储, 用的时候创建节省空间.

想要删除某一个不想要的数据也更简单. 当找到这个节点的时候, 通过找到前驱节点, 将前驱节点与后继节点相连

再把当前节点释放掉就可以了.

同样数据增改也很轻松.

遍历, 不需要修改数据, 所以使用一级指针遍历就可以了

void
TransList(struct ListNode* header) {struct ListNode* walker = header;while (walker) {// printf("%d %s\n", walker->key, walker->value);walker = walker->next;}
}

头插法, 需要修改数据, 所以可以使用二级指针, 也可以使用一级指针(需要返回值)

void
InsertHead_ptrToptr(struct ListNode** hptr,struct ListNode* node) {struct ListNode** header = hptr;node->next = *header;*header = node;
}struct ListNode*
InsertHead_ptr(struct ListNode* hptr,struct ListNode* node) {struct ListNode* header = hptr;node->next = header;header = node;return header;
}

尾插法, 需要修改数据, 所以可以使用二级指针, 也可以使用一级指针(因为要修改next的内容,

next是一级指针保存了要修改的节点的首地址, 所以不需要返回值, 我在这里加上了返回值)

void
InsertTail_ptrToptr(struct ListNode** hptr,struct ListNode* node) {struct ListNode** walker = hptr;while (*walker) {walker = &((*walker)->next);}node->next = NULL;*walker = node;
}struct ListNode*
InsertTail_ptr(struct ListNode* hptr,struct ListNode* node) {struct ListNode* walker = hptr;while (walker->next) {walker = walker->next;}node->next = NULL;walker->next = node;return hptr;
}

删除节点元素, 遍历整个链表, 找到要删除的节点的前驱节点, 前驱节点的next指向删除的元素的后继节点.

我给出一级指针和二级指针的两种方法, 可以好好理解一下两种方法执行过程.

struct ListNode*
RemoveElement_ptr(struct ListNode* hptr,struct ListNode* node) {struct ListNode* walker = hptr;while (walker->next) {if (walker->next == node) {struct ListNode* deleteElem = walker->next;walker->next = deleteElem->next;deleteElem->next = NULL;}walker = walker->next;}return hptr;
}void
RemoveElement_ptrToptr(struct ListNode** hptr,struct ListNode* node) {struct ListNode** walker = hptr;while (*walker) {if (*walker == node) {struct ListNode* deleteElem = *walker;*walker = ((*walker)->next);deleteElem->next = NULL;}walker = &((*walker)->next);}
}