下麵說的線性表主要是線性鏈表，這裡主要將雙向鏈表，單向鏈表迴圈鏈表等是類似的，不再累述。如果發現錯誤，還望不吝指正。 定義 線性表（linear list）是數據結構的一種，一個線性表是n個具有相同特性的數據元素的有限序列。數據元素是一個抽象的符號，其具體含義在不同的情況下一般不同。 在稍複雜的線性 ...
下麵說的線性表主要是線性鏈表，這裡主要將雙向鏈表，單向鏈表迴圈鏈表等是類似的，不再累述。如果發現錯誤，還望不吝指正。
定義
線性表（linear list）是數據結構的一種，一個線性表是n個具有相同特性的數據元素的有限序列。數據元素是一個抽象的符號，其具體含義在不同的情況下一般不同。 在稍複雜的線性表中，一個數據元素可由多個數據項（item）組成，此種情況下常把數據元素稱為記錄（record），含有大量記錄的線性表又稱文件（file）。 線性表中的個數n定義為線性表的長度，n=0時稱為空表。在非空表中每個數據元素都有一個確定的位置，如用ai表示數據元素，則i稱為數據元素ai線上性表中的位序。 線性表的相鄰元素之間存在著序偶關係。如用（a1，…，ai-1，ai，ai+1，…，an）表示一個順序表，則表中ai-1領先於ai，ai領先於ai+1，稱ai-1是ai的直接前驅元素，ai+1是ai的直接後繼元素。當i=1,2，…，n-1時，ai有且僅有一個直接後繼，當i=2，3，…，n時，ai有且僅有一個直接前驅。（來自百度百科）實現
採用的C++實現整個鏈表的操作過程，對於節點的記憶體的管理使用了C++11中提供的智能指針shared_ptr，以確保不會發生記憶體泄露的情況。
對鏈表操作的實現中採用了兩層封裝，將涉及到指針的操作封裝成了私有方法，避免泄露指針，導致無法控制對象析構的時刻，並且整個鏈表是非線程安全的。
節點數據結構：
template <typename T>
class Node {
public:
Node() { _prev = nullptr, _next = nullptr; }
Node(T data) : Node() { _data = data; }
void set_data(T data) { _data = data; }
void set_prev(std::shared_ptr<Node<T>> prev) { _prev = prev; }
void set_next(std::shared_ptr<Node<T>> next) { _next = next; }
std::shared_ptr<Node<T>> prev() { return _prev; }
std::shared_ptr<Node<T>> next() { return _next; }
T data() { return _data; }
private:
T _data;
std::shared_ptr<Node<T>> _prev;
std::shared_ptr<Node<T>> _next;
};
整個表結構：
整個表包含一個指向頭結點的指針和一個指向尾節點的指針，以及表的長度和表的大小的變數。
template <typename T>
class LinearList
{
public:
LinearList();
~LinearList();
void insert_node(T data, int64_t index);
void delete_node(int64_t index, T& data);
T get_element(int64_t index);
int64_t size();
int64_t length();
private:
std::shared_ptr<Node<T>> get_element_ptr(int64_t index);
void insert_node_ptr(std::shared_ptr<Node<T>> &data, int64_t index);
void delete_node_ptr(int64_t index, std::shared_ptr<Node<T>> &data);
private:
std::shared_ptr<Node<T>> _head;
std::shared_ptr<Node<T>> _tail;
int64_t _size;
int64_t _length;
};
插入新節點：
整個鏈表是一個帶空頭結點的鏈表：
1. 尋找插入點
2. 將待插入節點的next指針指向插入點指向的下一節點
3. 將待插入節點的prev指針指向插入點
4. 如果插入點的next指針不為空（不是頭結點），將插入點的下一節點的prev指針指向帶插入節點
5. 將插入點的next指針指向待插入點
template<typename T>
inline void LinearList<T>::insert_node(T data, int64_t index)
{
if (index < 0 || index > _length)
{
index = _length;
}
std::shared_ptr<Node<T>> data_ptr = std::make_shared<Node<T>>(data);
this->insert_node_ptr(data_ptr, index);
}
template<typename T>
inline void LinearList<T>::insert_node_ptr(std::shared_ptr<Node<T>> &data, int64_t index)
{
_ASSERTE(!(index < 0 || index > _length));
std::shared_ptr<Node<T>> tmp_ptr(_head);
// 查找插入位置
for (int64_t i = 0; i < index; ++i)
{
tmp_ptr = tmp_ptr->next();
}
// 將data插入到tmp_ptr的後面
data->set_next(tmp_ptr->next());
data->set_prev(tmp_ptr);
tmp_ptr->next() == nullptr ? tmp_ptr : tmp_ptr->next()->set_prev(data);
tmp_ptr->set_next(data);
++_length;
_size += sizeof(Node<T>);
}
刪除節點：
1. 查找待刪除節點
2. 斷開其prev和next指針
template<typename T>
inline void LinearList<T>::delete_node(int64_t index, T & data)
{
if (index < 0 || index > _length)
{
index = _length;
}
std::shared_ptr<Node<T>> tmp_ptr;
delete_node_ptr(index, tmp_ptr);
data = tmp_ptr->data();
}
template<typename T>
inline void LinearList<T>::delete_node_ptr(int64_t index, std::shared_ptr<Node<T>>& data)
{
_ASSERTE(!(index < 0 || index > _length));
std::shared_ptr<Node<T>> tmp_ptr(_head->next());
// 查找待刪除節點
for (int64_t i = 0; i < index; ++i)
{
tmp_ptr = tmp_ptr->next();
}
tmp_ptr->prev() == nullptr ? nullptr : tmp_ptr->prev()->set_next(tmp_ptr->next());
tmp_ptr->next() == nullptr ? nullptr : tmp_ptr->next()->set_prev(tmp_ptr->prev());
data = tmp_ptr;
--_length;
_size -= sizeof(Node<T>);
}
查看某個節點：
template<typename T>
inline T LinearList<T>::get_element(int64_t index)
{
return get_element_ptr(index)->data();
}
template<typename T>
inline std::shared_ptr<Node<T>> LinearList<T>::get_element_ptr(int64_t index)
{
if (index < 0 || index > _length) {
throw new std::exception("Invalid argument index.");
}
std::shared_ptr<Node<T>> tmp_ptr(_head->next());
for (int64_t i = 0; i < index; ++i)
{
tmp_ptr = tmp_ptr->next();
}
return tmp_ptr;
}
主函數：
int main() {
LinearList<int> linear_list;
for (int64_t i = 0; i < 10; i++)
{
linear_list.insert_node(i, i);
}
std::cout << "遍歷節點：" << std::endl;
for (int64_t i = 0; i < linear_list.length(); ++i) {
std::cout << linear_list.get_element(i) << " ";
}
std::cout << std::endl << std::endl;
std::cout << "刪除第2個節點： " << std::endl;
int data;
linear_list.delete_node(2, data);
std::cout << data << std::endl << std::endl;
std::cout << "第2個節點已刪除，再次遍歷結果為：" << std::endl;
for (int64_t i = 0; i < linear_list.length(); ++i) {
std::cout << linear_list.get_element(i) << " ";
}
std::cout << std::endl << std::endl;
std::cout << "刪除第2個節點： " << std::endl;
linear_list.delete_node(2, data);
std::cout << data << std::endl << std::endl;
std::cout << "第2個節點已刪除，再次遍歷結果為：" << std::endl;
for (int64_t i = 0; i < linear_list.length(); ++i) {
std::cout << linear_list.get_element(i) << " ";
}
std::cout << std::endl << std::endl;
return 0;
}
運行結果為：
代碼下載地址：https://github.com/wuhui2356/data_structure/tree/master/LinearList
