如果你對鏈表《第2篇 C++ 數(shù)據(jù)結(jié)構(gòu)-鏈表概述》請先閱讀前文，我們前一篇已經(jīng)羅列單鏈表的類接口清單，本篇會依據(jù)接口文件，逐步實現(xiàn)鏈表的各個函數(shù)接口。
我們首先看一下Node類的接口實現(xiàn)，這部分沒什么好說的，我本篇都使用C++模板來說，如果你對模板毫無了解的話請自行去補充這方面的知識。
#include "../headers/LinkedList.hh"
//節(jié)點類的默認構(gòu)造函數(shù)
template <class T>
Node<T>::Node() : d_data(), d_next(nullptr) {}
//節(jié)點類的用戶自定義構(gòu)造函數(shù)
template <class T>
Node<T>::Node(T val) : d_data(val), d_next(nullptr) {}
//節(jié)點類的析構(gòu)函數(shù)
template <class T>
Node<T>::~Node() {}
//返回節(jié)點上的元素實體
template <class T>
const T &Node<T>::elem()
{
return d_data;
}
//返回當(dāng)前節(jié)點的下一個節(jié)點的地址
template <class T>
Node<T> *Node<T>::next()
{
return d_next;
}
//輸出單個節(jié)點的值
template <class R>
std::ostream &operator<<(std::ostream &out, const Node<R> &nod)
{
if (nod.d_next != nullptr)
{
out << nod.elem();
}
return out;
}
單向鏈表的實現(xiàn)
初始化一個LinkedList的默認構(gòu)造函數(shù)，應(yīng)該是一個空的鏈表，LinkedList的頭指針d_head應(yīng)該指向nullptr;如下圖所示
1. 構(gòu)造/析構(gòu)函數(shù)
//構(gòu)造函數(shù)
template <class T>
LinkedList<T>::LinkedList()
: d_head(nullptr), d_last(nullptr), d_mid(nullptr), d_size(0) {}
//構(gòu)造函數(shù)2
template <class T>
LinkedList<T>::LinkedList(size_t n)
: d_head(new Node<T>()), d_last(d_head), d_mid(nullptr), d_size(n)
{
Node<T> *tmp;
for (auto i = 0; i < n; i++)
{
tmp = new Node<T>();
tmp->d_next = nullptr;
d_last->d_next = tmp;
d_last = tmp;
}
}
//析構(gòu)函數(shù)
template <class T>
LinkedList<T>::~LinkedList() { clear(); }
2.首端元素插入操作
在鏈表首部插入元素存在兩種情況
- 1)鏈表本身是空表，即鏈表的新節(jié)點的next指針會指向nullptr,然后LinkedList對象的頭指針(head)會指向新節(jié)點
push_head情景1
- 2)鏈表本身已含其他節(jié)點，此時
- 此時新節(jié)點的next指針先指向LinkedList的head指針指向的節(jié)點(當(dāng)前該節(jié)點是第一個節(jié)點)。
- 然后,LinkedList的head指針指向新節(jié)點.
push_head情景2
push_head()的實現(xiàn)
//析構(gòu)函數(shù)
template <class T>
LinkedList<T>::~LinkedList() { clear(); }
//表頭插入操作
template <class T>
void LinkedList<T>::push_head(T val)
{
//tmp是一個新節(jié)點
Node<T> *tmp = new Node<T>(val);
if (d_head == nullptr)
{
tmp->d_next = nullptr;
d_head = tmp;
}
else
{
//首先讓新節(jié)點指向原來首端元素
tmp->d_next = d_head;
//讓LinkedList頭指針指向新的元素節(jié)點
d_head = tmp;
}
++d_size;
}
3.追加元素操作
我們前文提到，在末端插入元素操作
- 實例化一個Node節(jié)點,并在該新節(jié)點上拷貝元素實體，由于新節(jié)點是“將要”作為鏈表最后一個元素追加到末端的，因此該節(jié)點的next指針需要指向nullptr.
- 注意，我們前一步實例化的節(jié)點還是“孤立”的節(jié)點，因此我們需要遍歷到鏈表中的最后一個節(jié)點，最后一個節(jié)點的next指向新創(chuàng)建的節(jié)點。整個過程如下動畫所示。
尾部插入
push_back方法實現(xiàn)
//末端插入操作
template <class T>
void LinkedList<T>::push_back(T val)
{
Node<T> *tmp = new Node<T>(val);
//判斷鏈表是否為空
if (d_head == nullptr)
{
tmp->d_next = nullptr;
d_head = tmp;
}
else
{
Node<T> *cur = d_head;
while (cur->d_next != nullptr)
{
cur = cur->d_next;
}
cur->d_next = tmp;
tmp->d_next = nullptr;
}
++d_size;
}
其他靜態(tài)語言,如C#,Java等，對于尾部插入還有不同的叫法，用的比較多的是“append”，而頭部插入也叫“prepend”，除了頭部插入和尾部插入之外，的其他位置插入操作，我這里統(tǒng)稱insert操作
4.insert插入操作
該操作同樣每次插入前需要將一個臨時指針副本偏移到指定索引的位置,需要注意的，如果我們插入的位置是位于索引k(注意k的索引計數(shù)從0開始算起),那么我們只遍歷到第k-1個節(jié)點，終止循環(huán)即可。
- 新節(jié)點的next指針指向第i個節(jié)點的下一個節(jié)點
- 第k-i個位置的節(jié)點的next指針指向新節(jié)點
中間位置插入操作
insert方法實現(xiàn)
//中間插入操作
template <class T>
void LinkedList<T>::insert(size_t k, T val){
if (k > d_size){
return;
}
Node<T> *tmp = new Node<T>(val);
if (d_size == 0){
tmp->d_next = nullptr;
d_head = tmp;
}else{
Node<T> *cur = d_head;
size_t i = 0;
while (cur->d_next){
if (i == k - 1){
break;
}
cur = cur->d_next;
i++;
}
tmp->d_next = cur->d_next;
cur->d_next = tmp;
}
++d_size;
}
關(guān)于超找節(jié)點與刪除節(jié)點的問題
很多應(yīng)用場景中,我們需要根據(jù)元素的值查找它所在的節(jié)點，在刪除某個元素中也要用到查找的算法，但我們特別需要注意,例如我們查找的元素值在元素的第k個索引的節(jié)點，我們不能遍歷到第k個節(jié)點，因為對于單向鏈表來說,一但我們的遍歷的指針位于第k個節(jié)點時已經(jīng)無法返回到位于k-1位置的節(jié)點，此時我們將位于第k個位置的節(jié)點執(zhí)行delete操作，那么第k-1個位置的節(jié)點與第k+1個位置的節(jié)點本應(yīng)要建立的鏈接關(guān)系已經(jīng)無法建立，那么從第k+1個位置的節(jié)點算起的部分與鏈表就“斷鏈”了，這也是造成鏈表內(nèi)存泄漏的重要原因之一。
因此，我們考慮到上面的問題，我們在實現(xiàn)查找算法時，已經(jīng)要將刪除操作的特殊情況優(yōu)先考慮到查找算法當(dāng)中，那么只需在查找算法中返回找到元素值所在節(jié)點的前一個節(jié)點即可。
5.search方法實現(xiàn)
//按值查找所在節(jié)點的前一個節(jié)點
template <class T>
Node<T> *LinkedList<T>::_search(const T &val)
{
if (d_head != nullptr)
{
Node<T> *prev = d_head;
while (prev->d_next && val != prev->d_next->d_data)
{
prev = prev->d_next;
}
return prev;
}
return nullptr;
}
上面的方法是私有的，那么如果要想常規(guī)的查找應(yīng)用提供一個通用版本的查找函數(shù)接口，怎么辦呢？easy job,我們可以下面這樣實現(xiàn)。
//按元素值查找元素的公開查找算法
template <class T>
Node<T> *LinkedList<T>::search(const T &val)
{
Node<T> *nod = _search(val);
if (val)
{
return nod->d_next;
}
return nullptr;
}
6.按值查找需要刪除的節(jié)點
該操作,我們只要調(diào)用我們私有版本的_search方法找到目標(biāo)節(jié)點的前一個節(jié)點。在刪除節(jié)點前，我們要將查找到的節(jié)點(位于k位置)的前一個節(jié)點的next指針指向k+1位置的節(jié)點。，最后放心將查找的節(jié)點刪除即可。
下面是刪除鏈表的中間某個節(jié)點的過程
remove方法實現(xiàn)(按值查找)
//按值查找要刪除的節(jié)點
template <class T>
void LinkedList<T>::remove(const T &val)
{
//按值查找所在節(jié)點的前一個節(jié)點
Node<T> *prev = _search(val);
if (prev != nullptr)
{
//要刪除的節(jié)點
Node<T> *cur = prev->d_next;
prev->d_next = cur->d_next;
delete cur;
}
}
7.清空鏈表操作
清空鏈表，我們從頭鏈表的頭部元素一直遍歷到鏈表的末端，遍歷過程中,在每次循環(huán)偏移鏈表的頭指針時,我們需要一個臨時指針變量來緩存前一個節(jié)點然后對其執(zhí)行內(nèi)存釋放操作。鏈表清空操作如下圖所示。
//清空整個鏈表
template <class T>
void LinkedList<T>::clear()
{
Node<T> *cur;
while (d_head)
{
cur = d_head;
d_head = d_head->d_next;
delete cur;
cur = nullptr;
}
}
8.順序反轉(zhuǎn)操作
反轉(zhuǎn)順序操作應(yīng)該是整個基礎(chǔ)鏈表中的難點，其實該操作中用到遍歷操作是毫無疑問，其實就是把每個節(jié)點的next指針的方向?qū)Φ簦久總€節(jié)點指向下一個后繼節(jié)點,現(xiàn)在分別需要指向它們的前一個。如下圖所示。
那邊實現(xiàn)該算法算是本篇基礎(chǔ)鏈表的難點，我們可以稍微通過下圖來解釋一下算法
首先，我們需要三個臨時Node<T>類型的指針，并且我們將三個指針分別初始指向鏈表三個不同的節(jié)點。
- pre是前任節(jié)點的指針，指向末端節(jié)點的空指針nullptr
- cur是當(dāng)前節(jié)點的指針,指向首個節(jié)點
- sor是后繼節(jié)點的指針，指向鏈表中的第二個節(jié)點
在遍歷過程中，注意我們始終以指向后繼節(jié)點的指針sor為“主動變量”在判斷sor未指向未端節(jié)點之前，pre指針和cur指針完成兩件事
- cur指針?biāo)诘墓?jié)點的next指針指向pre所在節(jié)點的指針，即完成鏈接順序?qū)φ{(diào)
-
之后cur指針和pre指針繼續(xù)前進分別指向后續(xù)需要對調(diào)鏈接順序的節(jié)點。
當(dāng)sor指針到達了末端節(jié)點之后,此時程序已經(jīng)結(jié)束了遍歷，此時的狀態(tài),cur指針指向倒數(shù)第二個節(jié)點，pre指針指向倒數(shù)第三個節(jié)點。
- cur指針?biāo)诘墓?jié)點的next指針指向pre指針?biāo)诘闹羔槨?/li>
- 鏈表的頭指針指向最后一個指針
reverse方法實現(xiàn)
//反轉(zhuǎn)鏈表順序
template <class T>
void LinkedList<T>::reverse()
{
Node<T> *pre, *cur, *sor;
pre = nullptr;
cur = d_head;
sor = d_head->d_next;
while (sor->d_next)
{
cur->d_next = pre;
pre = cur;
cur = sor;
sor = sor->d_next;
}
cur->d_next = pre;
d_head = sor;
d_head->d_next = cur;
}
剩余的函數(shù)接口實現(xiàn)
9.獲取末端最后一個元素
//獲取最后一個節(jié)點
template <class T>
T LinkedList<T>::last()
{
Node<T> *cur = d_head;
while (cur->d_next)
{
cur = cur->d_next;
}
return cur->d_data;
}
10.打印鏈表的operator<<函數(shù)重載
//打印鏈表
template <class R>
std::ostream &operator<<(std::ostream &out, const LinkedList<R> &list)
{
Node<R> *cur = list.d_head;
while (cur != nullptr)
{
out << cur->elem() << "? ";
cur = cur->next();
}
if (cur == nullptr)
{
out << "?";
}
out << std::endl;
return out;
}
operator[]訪問操作符
//索引訪問
template <class T>
T LinkedList<T>::operator[](size_t k)
{
Node<T> *cur = d_head;
size_t i = 0;
if (d_head == nullptr)
{
return;
}
else
{
while (cur->d_next)
{
if (i == k)
{
break;
}
cur = cur->d_next;
i++;
}
return cur->d_data;
}
}
last()方法
//獲取最后一個節(jié)點
template <class T>
T LinkedList<T>::last()
{
Node<T> *cur = d_head;
while (cur->d_next)
{
cur = cur->d_next;
}
return cur->d_data;
}
獲取中點元素
這個其實用到了兩個指針，一個叫快速指針，一個叫慢速指針。在整個遍歷過程中，快速指針到達末端元素，此時慢速指針正好位于中間節(jié)點。很多對辦拆分鏈表基本上都需要用到這個技術(shù)。
//獲取中間節(jié)點
template <class T>
Node<T> *LinkedList<T>::mid_node()
{
if (d_head != nullptr)
{
Node<T> *s_ptr = d_head;
Node<T> *f_ptr = d_head;
while (f_ptr != nullptr && f_ptr->d_next != nullptr)
{
f_ptr = f_ptr->d_next->d_next;
s_ptr = s_ptr->d_next;
}
return s_ptr;
}
}
//獲取中間節(jié)點,并返回傳入的變量的引用
template <class T>
Node<T> *LinkedList<T>::mid_node(size_t &k)
{
if (d_head != nullptr)
{
Node<T> *s_ptr = d_head;
Node<T> *f_ptr = d_head;
while (f_ptr != nullptr && f_ptr->d_next != nullptr)
{
f_ptr = f_ptr->d_next->d_next;
s_ptr = s_ptr->d_next;
k++;
}
return s_ptr;
}
}
實現(xiàn)迭代接口
這個實現(xiàn)了LinkedList的迭代接口，由于迭代接口基本上不會更改，所以我將Iterator的實現(xiàn)寫在LinkedList接口的內(nèi)部。
class LinkedList{
....
class Iterator;
Iterator begin() { return Iterator(d_head); }
Iterator end(){
return Iterator(nullptr);
}
class Iterator{
private:
const Node<T> *d_cur; //當(dāng)前節(jié)點
public:
Iterator() noexcept : d_current(d_head) {}
Iterator(const Node<T> *nod) noexcept : d_cur(nod) {}
Iterator &operator=(Node<T> *nod){
this->d_cur = nod;
return *this;
}
Iterator &operator++(){
if (d_cur){
d_cur = d_cur->d_next;
return *this;
}
}
Iterator &operator++(int){
Iterator iter = *this;
++*this;
return iter;
}
bool operator!=(const Iterator &iter){
return d_cur != iter.d_cur;
}
T operator*(){
return d_cur->d_data;
}
};
}
小結(jié)
剩下來的部分就是接口測試，我打算留到下一篇在優(yōu)化前和優(yōu)化后做性能測試對比，因為上面說的都是鏈表的常規(guī)實現(xiàn),只能算是一個入門的鏈表實現(xiàn)，其實鏈表可以做到時間復(fù)雜度縮減到最低。不論"增/刪/改/查"的，它們的痛點就是那O(n)的遍歷操作。這些問題，我們會留到下一篇再說。
