C++數據結構之：鏈List

摘要：

??it人員無論是使用哪種高級語言開發東東，想要更高效有層次的開發程序的話都躲不開三件套：數據結構，算法和設計模式。數據結構是相互之間存在一種或多種特定關系的數據元素的集合，即帶“結構”的數據元素的集合，“結構”就是指數據元素之間存在的關系，分為邏輯結構和存儲結構。

??此系列專注講解數據結構數組、鏈表、隊列、棧、樹、哈希表、圖，通過介紹概念以及提及一些可能適用的場景，并以C++代碼簡易實現，多方面認識數據結構，最后為避免重復造輪子會淺提對應的STL容器。本文介紹的是鏈List。

（開發環境：VScode，C++17）

關鍵詞： C++，數據結構，鏈表，List

聲明：本文作者原創，轉載請附上文章出處與本文鏈接。

文章目錄

- - 摘要：
  - 正文：
  - - 介紹：
    - - 特性：
      - 應用：
    - 代碼實現：
    - 對應STL：
  - 推薦閱讀

正文：

介紹：

??鏈表（Linked List）是一種常見的數據結構，它通過一系列的節點（Node）來存儲數據，每個節點包含兩個部分：一個是數據域（Data Field），用于存儲數據；另一個是鏈接域（Link Field），用于存儲指向下一個節點的引用（在單鏈表中）或前一個節點和下一個節點的引用（在雙向鏈表中）。鏈表數據一般都是分散存儲于內存中的，無須存儲在連續空間內。

雙向鏈表：

在這里插入圖片描述

特性：

動態性：鏈表不需要在內存中預先分配固定大小的空間，可以根據需要動態地創建和刪除節點。這使得鏈表在處理不確定大小的數據集合時非常靈活。
多種類型：鏈表有多種類型，包括單向鏈表、雙向鏈表、循環鏈表等。每種類型的鏈表都有其特定的應用場景和優缺點。
插入和刪除效率高：在鏈表中插入或刪除一個節點時，只需要修改相關節點的指針（或引用）即可，而不需要移動大量數據。
非連續性：鏈表中的節點在內存中不一定是連續存儲的。每個節點都包含一個指向下一個節點的指針（或引用），這些指針（或引用）將節點連接在一起。

應用：

實現堆棧（Stack）和隊列（Queue）等抽象數據類型。
在數據庫中實現鄰接列表來表示圖（Graph）。
在瀏覽器中表示歷史記錄或書簽。
在操作系統中表示進程列表或文件列表。
在許多算法中，如歸并排序（Merge Sort）和快速排序（Quick Sort）的鏈表實現等。

代碼實現：

#clist.h
#ifndef CLIST_H
#define CLIST_H
#include <iostream>
#include <cstdlib>using namespace std;
// 鏈表結點
template <class T>
class DNode
{
public:DNode<T> *next;DNode<T> *prev;T data;
};// 雙向列表類
template <class T>
class CList
{
public:CList();                     // 默認構造函數CList(const CList& ln);      // 拷貝構造函數~CList();                    // 析構函數void add(T e);               // 向鏈表添加數據void remove(T index);        // 移除某個結點T find(int index);           // 查找結點bool empty();                // 判斷是否為空int size();                  // 鏈表長度void print();                // 顯示鏈表void print_reverse();        // 鏈表反向顯示void clear();                // 刪除全部結點
private:DNode<T> *head;DNode<T> *tail;int length;
};// 默認構造函數
template <typename T>
CList<T>::CList()
{head = new DNode<T>;tail = new DNode<T>;head->next = tail;head->prev = nullptr;tail->next = nullptr;tail->prev = head;length = 0;
}// 拷貝構造函數
template <typename T>
CList<T>::CList(const CList &ln)
{head = new DNode<T>;head->prev = nullptr;tail = new DNode<T>;head->next = tail;tail->prev = head;length = 0;DNode<T>* temp = ln.head;while (temp->next != ln.tail){temp = temp->next;tail->data = temp->data;DNode<T> *p = new DNode<T>;p->prev = tail;tail->next = p;tail = p;length++;}tail->next = nullptr;
}// 析構函數
template <typename T>
CList<T>::~CList()
{if (length == 0){delete head;delete tail;head = nullptr;tail = nullptr;return;}while (head->next != nullptr){DNode<T> *temp = head;head = head->next;delete temp;}delete head;head = nullptr;
}// 向鏈表添加數據
template <typename T>
void CList<T>::add(T e)
{DNode<T>* temp = this->tail;tail->data = e;tail->next = new DNode<T>;DNode<T> *p = tail;tail = tail->next;tail->prev = p;tail->next = nullptr;length++;
}// 查找結點
template <typename T>
T CList<T>::find(int index)
{if (length == 0){cout << "CList is empty";return -1;}if (index >= length){cout << "Out of bounds";return -1;}int x = 0;DNode<T> *p;p = head->next;while (p->next != nullptr && x++ != index){p = p->next;}return p->data;
}// 刪除結點
template <typename T>
void CList<T>::remove(T index)
{if (length == 0){cout << "CList is empty";return;}DNode<T> *p = head;while (p->next != nullptr){p = p->next;if (p->data == index){DNode<T> *temp = p->prev;temp->next = p->next;p->next->prev = temp;delete p;length--;return;}}
}// 刪除所有結點
template <typename T>
void CList<T>::clear()
{if (length == 0){return;}DNode<T> *p = head->next;while (p != tail){DNode<T>* temp = p;p = p->next;delete temp;}head->next = tail;tail->prev = head;length = 0;
}// 判斷是否為空
template <typename T>
bool CList<T>::empty()
{if (length == 0){return true;}else {return false;}
}// 鏈表長度
template <typename T>
int CList<T>::size()
{return length;
}// 輸出鏈表
template <typename T>
void CList<T>::print()
{if (length == 0){cout << "CList is empty" << endl;return;}DNode<T> *p = head->next;while (p != tail){cout << p->data << " ";p = p->next;}cout << endl;
}// 反向輸出鏈表
template <typename T>
void CList<T>::print_reverse()
{if (length == 0)return;DNode<T> *p = tail->prev;while (p != head){cout << p->data << " ";p = p->prev;}cout << endl;
}#endif // !CLIST_H

#clist.cpp
#include "clist.h"
#include <iostream>
using namespace std;int main(int argc, char**argv)
{CList<int> list;list.add(6);list.add(443);list.add(767);list.add(56);CList<int> list2(list);list2.print_reverse();list2.print();cout << "list2.size(): " << list2.size() << endl;cout << "list2.find(2): " << list2.find(2) << endl;list2.remove(443);list2.print();return 0;
}