前言
上篇文章学习了线性表的顺序存储结构，不过，在代码的实现过程中，发现了顺序表的一个很大的问题：插入和删除需要移动大量的数据元素，那如何解决这个问题?
链式存储结构
前篇文章有谈到过线性表的存储方式，一种是顺序存储结构，另一种是链式存储结构。我们再来回顾一下链式存储的定义
为了表示每个数据元素与其直接后继元素之间的逻辑关系，每个元素除了存储本身的信息外，还需要存储指示其直接后继的信息
链式存储结构.png
单链表
上面的定义有提到逻辑关系，有一种常见的链式存储逻辑结构可以体现：单链表。
n个结点链接成一个链式线性表的结构叫做链表，当每个结点中包含一个指针域时，叫做单链表
链表.png
链表的基本概念
上面的定义有提到链表，一个链表一般可以分为三个部分：
-
表头结点
链表中的第一个结点，包含指向第一个数据元素的指针以及链表自身的一些信息
-
数据结点
链表中代表数据元素的结点，包含指向下一个数据元素的指针和数据元素的信息
-
尾结点
链表中的最后一个数据结点，其下一个元素指针为空，也就是指针域为空，表示无后继
单链表结构图
单链表.png
实现单链表
在头文件中声明需要实现单链表的操作
typedef void LinkList;
typedef struct _tag_LinkListNode LinkListNode;
/**在C语言中可以用结构体来定义链表中指针域*/
struct _tag_LinkListNode {
/**指向下个元素的指针*/
LinkListNode *next;
};
/**数据元素结点*/
typedef struct Value {
LinkListNode next;
int value;
} TValue;
LinkList *createLinkList();
void destroyLinkList(LinkList *list);
void clearLinkList(LinkList *list);
int getLinkListLen(LinkList *list);
int addLinkListEle(LinkList *list, LinkListNode *node, int position);
LinkListNode *getLinkListEle(LinkList *list, int position);
LinkListNode *deleteLinkListEle(LinkList *list,int position);
在实现的文件中定义头节点
/**
* 定义表头结点
*/
typedef struct _tag_LinkList {
/**指向第一个元素的头指针*/
LinkListNode header;
/**整个单链表的长度*/
int length;
} TLinkList;
单链表的添加元素操作
/**
* 添加元素到单链表中指定位置
* @param list
* @param node
* @param position 在链表中的索引值
* @return
*/
int addLinkListEle(LinkList *list, LinkListNode *node, int position) {
TLinkList *linkList = (TLinkList *) list;
/**判断单链表、插入的元素以及插入的位置的合法性*/
int ret = (linkList != NULL) && (node != NULL) && (position >= 0);
int i;
if (ret) {
/** step 1 开始位置指向表头*/
LinkListNode *current = (LinkListNode *) linkList;
for (i = 0; i < position && current->next != NULL; i++) {
/**
* step 2 由表头开始通过next指针移动position次
* 第position处的下一个元素就是要插入的位置，也就
* 是当前元素的current->next。
*/
current = current->next;
}
/**
* step 3 交换当前元素和插入元素的指针域
* 注：这两步顺序不能搞反，否则会导致单链
* 表断链
*/
node->next = current->next;
current->next = node;
/**更新单链表长度*/
linkList->length++;
}
return ret;
}
这里的核心算法就是step 2和step 3这两步。我们可以通过图来加深理解。请注意图中的第2步与第1步是顺序是不能搞反的，否则会导致断链
插入.png
单链表的删除元素操作
/**
* 删除链表中指定的元素
* @param list
* @param position 被删除元素在链表中的索引值
* @return
*/
LinkListNode *deleteLinkListEle(LinkList *list, int position) {
TLinkList *linkList = (TLinkList *) list;
LinkListNode *node = NULL;
if (linkList != NULL && position >= 0 && position < linkList->length) {
LinkListNode *current = (LinkListNode *) linkList;
/**获取第position处元素，该元素的next指针域就是需要删除的元素*/
for (int i = 0; i < position; i++) {
current = current->next;
}
node = current->next;
current->next = node->next;
linkList->length--;
}
return node;
}
删除.png
获取元素
/**
* 获取指定位置的元素
* @param list
* @param position 被获取元素在链表中的索引值
* @return
*/
LinkListNode *getLinkListEle(LinkList *list, int position) {
TLinkList *linkList = (TLinkList *) list;
LinkListNode *node = NULL;
int i;
if (linkList != NULL && position >= 0 && position < linkList->length) {
/** step 1 开始位置指向表头*/
LinkListNode *current = (LinkListNode *) linkList;
for (i = 0; i < position; i++) {
/** step 2 由表头开始通过next指针移动position次*/
current = current->next;
}
/** step 3 当前元素的next指针即指向要获取的元素*/
node = current->next;
}
return node;
}
总结
单链表的一些主要操作就都已经实现完了，代码中注释很清楚，再加上图一起来理解就更非常容易了(完整代码)。那它与上篇文章学过的顺序表有哪些优缺点了？
-
优点：
- 无需一次性定制链表的容量
- 插入和删除无需移动数据元素
-
缺点
- 数据元素必须保存后继元素的位位置信息
- 获取指定数据的元素操作需要顺序访问之前的元素
