链表概念
链表一般分为单向链表，双向链表，环形链表，链表实际是线性表的顺序存储结构，和数组不同的是，它用一组任意的存储单元来存储线性表中的数据，存储单元不是连续的
链表的长度不是固定的，链表这一数据结构的特点可以非常方便的实现节点的插入和删除操作
链表的每一个元素称为一个节点，每个节点可以储存在内存中的不同位置，每个节点除了存储每个节点本身的信息外，还要存储下一个节点的位置信息
单链表中，每个节点包含一个指向下一节点的指针变量，链表最后一个节点指针字段的值为NULL，提示链表不再包含后续节点，找到链表的第一个节点后，指针就可以带你访问剩余的所有节点
单链表使用根指针（root pointer）指向链表的第一个节点，注意根指针只是一个指针，它不包含任何数据
注意：链表只能顺序访问，不能随机访问，链表这种存储方式最大的缺点是容易出现断链，一旦某个节点的指针域数据丢失，该节点后的数据也会完全丢失
- 链表和数组比较
数值是线性表的一种顺序存储方式，优点是使用直观，支持快速，随机访问
缺点是对数组插入和删除需要移动大量的数组元素，定义时必须指定数组的长度，一旦运行，长度就不能再改变，空间效率低
单链表的初始化
typedef struct Node_s {
struct Node_s *next;
uint32_t value;
} stNode;
// root pointer point to first element
stNode* root = NULL;
static stNode *createListNode(uint32_t data) {
stNode *list = (stNode*)malloc(sizeof(stNode));
list->value = data;
list->next = NULL;
return list;
单链表插入操作
- 插入单链表头部
- 插入单链表的末尾
单链表_头插和尾插.jpg
单链表的头插和尾插都只需要一个指针
- 插入单链表头部，获取根指针值就可以获取链表首元素的地址，这种情形需要改变根指针变量的值
- 插入单链表尾部，根据根指针变量遍历链表，直到current->next 为NULL，就可以认为指向了最后一个节点
static void insertListNodeBack(stNode *rootp, stNode *lstn) {
stNode *current = rootp;
while (current->next != NULL) {
current = current->next;
}
current->next = lstn;
lstn->next = NULL;
}
static void insertListNodeFront(stNode **rootp, stNode *lstn) {
lstn->next = *rootp;
*rootp = lstn;
}
-
通用的插入函数
通用的插入函数考虑了插入首节点，尾结点还有中间节点的情形，使用两个指针顺序遍历链表，初始化时 previous 设置为NULL，current 指向第一个节点
单链表_中间插入.jpg
int insertListNodeCommon(stNode **rootp, stNode *lstn) {
//current 指向第一个节点
stNode *current = *rootp;
stNode *previous = NULL;
while (current != NULL && current->value < lstn->value) {
previous = current;
current = current->next;
}
// 此时 current->value >= lstn->value lstn 应该插入 current 指针之前
lstn->next = current;
// 此时插入的是首节点
if (previous == NULL)
*rootp = lstn;
else
previous->next = lstn;
return TRUE;
}
单链表删除操作
- 删除单链表的首元素
- 删除单链表的末尾元素
- 删除单链表的首元素使用一个指针即可，通过 rootp 指向第一个节点，但是要改变根指针的指向
- 删除单链表的末尾元素，需要使用两个指针，因为需要将倒数第二个节点的 next 字段重新指向新的元素
单链表的头部和尾部删除.jpg
void deleteNodefront(stNode **rootp)
{
stNode *deleteNode = *rootp;
*rootp = deleteNode->next;
free(deleteNode);
deleteNode = NULL;
}
void deleteNodeback(stNode *rootp)
{
stNode *previous = NULL;
stNode *current = rootp;
while (current->next != NULL) {
previous = current;
current = current->next;
}
// 此时 current->next = NULL current 指向最后一个节点 previous 指向倒数第二个节点
free(current);
current = NULL;
previous->next = NULL;
}
3.通用的删除函数
通用的删除函数需要使用两个指针，包含了头尾和中间的情形：
单链表的中间删除.jpg
int deleteListNodeCommon(stNode **rootp, uint32_t value) {
stNode *current = *rootp;
stNode *previous = NULL;
while (current->next != NULL && current->value != value) {
previous = current;
current = current->next;
}
// 如果遍历到最后一个节点, 最后一个节点的值任然不符合
if (current->next == NULL && current->value != value) {
printf("cannot find element value %d \n", value);
return FALSE;
}
// previous = NULL current = *rootp 删除第一个节点
// previous != NULL 中间节点 或者 尾结点
if(previous != NULL) {
previous->next = current->next;
} else {
*rootp = current->next;
}
free(current);
current == NULL;
return TRUE;
}
单链表遍历操作
只要获取到根指针，就可以顺次遍历到单链表的所有节点：
static void dumpAllListNode(stNode *plist) {
printf("dump list: ");
stNode *p = plist;
while (p != NULL) {
printf(" %d", p->value);
p = p->next;
}
printf("\n");
}
单链表的反转操作
反转操作，实际就是将链表整体反过来，头变为尾，尾变成头，实现反转操作的算法有四种：
迭代反转法、递归反转法、就地逆置法和头插法
-
迭代反转法
该算法的思是从当前链表的第一个节点开始，一直遍历到最后一个节点，定义三个指针，顺次指向三个节点，每次三个指针都一起移动 如下图所示：
迭代反转法翻转链表.jpg
定义三个指针分别为 begp，midp，endp
- endp 的 next 域保持不变，这样可以保证找到下一节点
- 改变 midp 的 next 域指向 begp，midp 的移动依靠 endp的赋值
- begp 的赋值依靠 midp
int iteration_reverse(stNode **rootp) {
// current 指向第一个节点
stNode *current = *rootp;
if (current == NULL) {
printf("empty list !!\n");
return FALSE;
}
stNode *begp = NULL;
stNode *midp = current;
stNode *endp = current->next;
while (1) {
midp->next = begp;
if (endp == NULL) {
break;
}
begp = midp;
midp = endp;
endp = endp->next;
}
//最后修改 head 头指针的指向
*rootp = midp;
return TRUE;
}
单链表反转操作文章：http://c.biancheng.net/view/8105.html
网友评论