前言
上篇文章學(xué)習(xí)了線性表的順序存儲結(jié)構(gòu)，不過，在代碼的實(shí)現(xiàn)過程中，發(fā)現(xiàn)了順序表的一個很大的問題：插入和刪除需要移動大量的數(shù)據(jù)元素，那如何解決這個問題?
鏈?zhǔn)酱鎯Y(jié)構(gòu)
前篇文章有談到過線性表的存儲方式绢掰，一種是順序存儲結(jié)構(gòu)，另一種是鏈?zhǔn)酱鎯Y(jié)構(gòu)童擎。我們再來回顧一下鏈?zhǔn)酱鎯Φ亩x
為了表示每個數(shù)據(jù)元素與其直接后繼元素之間的邏輯關(guān)系滴劲，每個元素除了存儲本身的信息外，還需要存儲指示其直接后繼的信息
單鏈表
上面的定義有提到邏輯關(guān)系顾复，有一種常見的鏈?zhǔn)酱鎯壿嫿Y(jié)構(gòu)可以體現(xiàn)：單鏈表班挖。
n個結(jié)點(diǎn)鏈接成一個鏈?zhǔn)骄€性表的結(jié)構(gòu)叫做鏈表，當(dāng)每個結(jié)點(diǎn)中包含一個指針域時芯砸，叫做單鏈表
鏈表的基本概念
上面的定義有提到鏈表萧芙，一個鏈表一般可以分為三個部分：
-
表頭結(jié)點(diǎn)
鏈表中的第一個結(jié)點(diǎn)，包含指向第一個數(shù)據(jù)元素的指針以及鏈表自身的一些信息
-
數(shù)據(jù)結(jié)點(diǎn)
鏈表中代表數(shù)據(jù)元素的結(jié)點(diǎn)假丧，包含指向下一個數(shù)據(jù)元素的指針和數(shù)據(jù)元素的信息
-
尾結(jié)點(diǎn)
鏈表中的最后一個數(shù)據(jù)結(jié)點(diǎn)双揪，其下一個元素指針為空，也就是指針域?yàn)榭瞻悖硎緹o后繼
單鏈表結(jié)構(gòu)圖
實(shí)現(xiàn)單鏈表
在頭文件中聲明需要實(shí)現(xiàn)單鏈表的操作
typedef void LinkList;
typedef struct _tag_LinkListNode LinkListNode;
/**在C語言中可以用結(jié)構(gòu)體來定義鏈表中指針域*/
struct _tag_LinkListNode {
/**指向下個元素的指針*/
LinkListNode *next;
};
/**數(shù)據(jù)元素結(jié)點(diǎn)*/
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);
在實(shí)現(xiàn)的文件中定義頭節(jié)點(diǎn)
/**
* 定義表頭結(jié)點(diǎn)
*/
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處的下一個元素就是要插入的位置，也就
* 是當(dāng)前元素的current->next。
*/
current = current->next;
}
/**
* step 3 交換當(dāng)前元素和插入元素的指針域
* 注：這兩步順序不能搞反疯趟，否則會導(dǎo)致單鏈
* 表斷鏈
*/
node->next = current->next;
current->next = node;
/**更新單鏈表長度*/
linkList->length++;
}
return ret;
}
這里的核心算法就是step 2和step 3這兩步拘哨。我們可以通過圖來加深理解。請注意圖中的第2步與第1步是順序是不能搞反的信峻，否則會導(dǎo)致斷鏈
單鏈表的刪除元素操作
/**
* 刪除鏈表中指定的元素
* @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;
}
獲取元素
/**
* 獲取指定位置的元素
* @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 當(dāng)前元素的next指針即指向要獲取的元素*/
node = current->next;
}
return node;
}
總結(jié)
單鏈表的一些主要操作就都已經(jīng)實(shí)現(xiàn)完了，代碼中注釋很清楚盹舞，再加上圖一起來理解就更非常容易了(完整代碼)产镐。那它與上篇文章學(xué)過的順序表有哪些優(yōu)缺點(diǎn)了？
-
優(yōu)點(diǎn)：
- 無需一次性定制鏈表的容量
- 插入和刪除無需移動數(shù)據(jù)元素
-
缺點(diǎn)
- 數(shù)據(jù)元素必須保存后繼元素的位位置信息
- 獲取指定數(shù)據(jù)的元素操作需要順序訪問之前的元素
