鏈表
一在扰、 何為鏈表
引用維基百科的介紹, 鏈表(Linked list)是一種常見的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu), 是一種線性表, 但是并不會(huì)按照線性的順序存儲(chǔ)結(jié)構(gòu),是一種"在物理空間上非連續(xù)袋励、非順序的存儲(chǔ)結(jié)構(gòu)"挚瘟。
由于不必須按順序存儲(chǔ)抄瑟，鏈表在插入的時(shí)候可以達(dá)到O(1)的復(fù)雜度摩梧，比另一種線性表順序表快得多普气，但是查找一個(gè)節(jié)點(diǎn)或者訪問特定編號(hào)的節(jié)點(diǎn)則需要O(n)的時(shí)間唐断，而順序表相應(yīng)的時(shí)間復(fù)雜度分別是O(logn)和O(1)麸祷。
鏈表通常由一連串節(jié)點(diǎn)組成撮抓，每個(gè)節(jié)點(diǎn)包含:
- 鏈域： 它的值是線性表的上一個(gè)/下一個(gè)元素的位置，即地址摇锋。
- 數(shù)據(jù)域： 它的值是存儲(chǔ)的相應(yīng)實(shí)例數(shù)據(jù)的值丹拯。
二、鏈表的優(yōu)缺點(diǎn)
優(yōu)點(diǎn) ：
- 使用鏈表結(jié)構(gòu)可以克服數(shù)組鏈表需要預(yù)先知道數(shù)據(jù)大小的缺點(diǎn)荸恕，鏈表結(jié)構(gòu)可以充分利用計(jì)算機(jī)內(nèi)存空間乖酬，實(shí)現(xiàn)靈活的內(nèi)存動(dòng)態(tài)管理。
- 相比數(shù)組結(jié)構(gòu)融求，對(duì)于元素的插入和刪除操作來說咬像，鏈表的效率要比數(shù)組高，因?yàn)槊總€(gè)節(jié)點(diǎn)都有鏈域存儲(chǔ)指向下一個(gè)節(jié)點(diǎn)的指針，因此進(jìn)行插入和刪除的操作時(shí)不需要頻繁的移動(dòng)其他的元素县昂，只需要修改對(duì)應(yīng)位置附近節(jié)點(diǎn)的鏈域的值即可肮柜。
缺點(diǎn)
- 查詢鏈表只能通過指針順序訪問，效率相對(duì)低下倒彰，查詢可能需要O(n)的時(shí)間復(fù)雜度审洞。
- 因?yàn)殒湵淼拿總€(gè)節(jié)點(diǎn)都含有鏈域，所占用的空間較多待讳。
三芒澜、單鏈表的實(shí)現(xiàn)(C++)
- 定義節(jié)點(diǎn)的結(jié)構(gòu)
template<class T>
struct ListNode
{
T m_tElement; // 數(shù)據(jù)域
ListNode<T>* m_pNext; // 鏈域
// 構(gòu)造函數(shù)
ListNode(){}
ListNode(const T& theElement) {this->m_tElement = theElement;}
ListNode(const T& theElement, ListNode<T>* theNext)
{
this->m_tElement = theElement;
this->m_pNext = theNext;
}
}
- 定義鏈表類
template<class T>
class SingleList
{
public:
// 構(gòu)造函數(shù)與析構(gòu)函數(shù)
SingleList();
SingleList(const SingleList<T>& theList);
~SingleList();
// 類方法
bool empty() const {return m_iLength == 0;} // 判斷鏈表是否為空
int size() const {return m_iLength;} // 返回鏈表長度
int indexOf(const T& theElement) const;
T& get(int theIndex) const;
void insert(int theIndex, const T& theElement);
void delete(int theIndex);
void update(int theIndex, const T& theElement);
private:
void checkIndex(theIndex); // 確認(rèn)是否索引值是否合法
int m_iLength; // 鏈表的長度
ListNode<T>* m_pFirstNode; // 鏈表的頭節(jié)點(diǎn)
}
- 構(gòu)造函數(shù)的實(shí)現(xiàn)
// 無參構(gòu)造函數(shù)
template<class T>
SingleList<T>::SingleList()
{
m_pFirstNode = NULL;
m_iLength = 0;
}
// 復(fù)制構(gòu)造函數(shù)
template<class T>
SingleList<T>::SingleList(const SingleList<T>& theList)
{
m_iLength = theList.m_iLength;
// 判斷源鏈表是否為空鏈表
if(m_iLength == 0)
{
m_pFirstNode = NULL;
return;
}
ListNode<T>* otherNode = theList.m_pFirstNode;
m_pFirstNode = new ListNode<T>(otherNode->m_tElement);
ListNode<T>* thisNode = m_pFirstNode;
otherNode = otherNode->m_pNext;
while (otherNode != NULL)
{
// 當(dāng)源鏈表后續(xù)還有節(jié)點(diǎn)時(shí)，復(fù)制鏈表剩下的其他節(jié)點(diǎn)
thisNode->m_pNext = new ListNode<T>(otherNode->m_tElement);
thisNode = thisNode->m_pNext;
otherNode = otherNode->m_pNext;
}
thisNode->next = NULL;
}
- 析構(gòu)函數(shù)的實(shí)現(xiàn)
template<class T>
SingleList<T>::~SingleList()
{
while (m_pFirstNode != NULL)
{
ListNode<T>* tempNode = m_pFirstNode;
delete m_pFirstNode;
m_pFirstNode = tempNode;
}
}
-
類方法的實(shí)現(xiàn)
int indexOf(const T& theElement) const
// 返回指定元素的索引值
template<class T>
int SingleList<T>::indexOf(const T& theElement) const
{
ListNode<T>* currNode = m_pFirstNode;
int index = 0;
while (currNode != NULL && currNode->m_tElement != theElement)
{
currNode = currNode->m_pNext;
++index;
}
if (currNode == NULL)
{
return -1;
}
if (currNode != NULL)
return index;
}
? T& get(int theIndex) const
// 返回指定索引的元素
template<class T>
T& SingleList<T>::get(int theIndex) const
{
checkIndex(theIndex);
ListNode<T>* currNode = m_pFirstNode;
// 找到索引值對(duì)應(yīng)的元素
for(int i = 0; i < theIndex; ++i)
currNode = currNode->m_pNext;
// 返回元素的值
return currNode->m_tElement;
}
? void insert(int theIndex, T& theElement)
// 在指定位置插入元素
template<class T>
void SingleList<T>::insert(int theIndex, const T& theElement)
{ // 判斷索引值是否合法
checkIndex(theIndex);
if (theIndex == 0)
{
m_pFirstNode = new ListNode<T>(theElement, m_pFirstNode)
}
if (theIndex > 0)
{
ListNode<T>* currNode = m_pFirstNode;
// 因?yàn)橐谥付ㄎ恢貌迦朐? 因此去找指定位置的前一個(gè)元素
for (int i = 0; i < theIndex - 1; ++i)
currNode = currNode->m_pNext;
ListNode<T>* newNode = new ListNode<T>(theElement, currNode->m_pNext);
}
++m_iLength;
}
? void delete(int theIndex)
// 刪除指定位置的元素
template<class T>
void SingleList<T>::delete(int theIndex)
{
checkIndex(theIndex);
ListNode<T>* targetNode;
if (theIndex == 0)
{
targetNode = m_pFirstNode;
m_pFirstNode = m_pFirstNode->m_pNext;
}
if (theIndex > 0)
{
ListNode<T>* prevNode = m_pFirstNode;
for (int i = 0; i < theIndex - 1; ++i)
prevNode = prevNode->m_pNext;
targetNode = prevNode->m_pNext;
prevNode->m_pNext = targetNode->m_pNext;
}
delete targetNode;
--m_iLength;
}
? void update(int theIndex, const T& theElement)
// 修改指定位置元素的值
template<class T>
void SingleList<T>::update(int theIndex, const T& theElement)
{
// 判斷索引值是否合法
checkIndex(theIndex);
//
if (theIndex == 0)
{
m_pFirstNode->m_tElement = theElement;
return ;
}
ListNode<T>* currNode = m_pFirstNode;
for (int i = 0; i < theIndex; ++i)
currNode = currNode->m_pNext;
currNode->m_tElement = theElement;
}
? void checkIndex(int theIndex)
// 檢查索引值是否合法
template<class T>
void SingleList<T>::checkIndex(int theIndex)
{
if (theIndex < 0 || theIndex > m_iLength - 1)
std::cout << "Error Index Value" << std::endl;
}
四创淡、結(jié)語
這是我第一次做類似的學(xué)習(xí)筆記痴晦，借鑒了網(wǎng)上許多的博客以及書籍的資料和內(nèi)容，在這里做個(gè)記錄琳彩，若是有錯(cuò)誤或不恰當(dāng)之處誊酌，希望各路大神能不吝賜教，指點(diǎn)小弟不足之處露乏。
