数据结构 - C/C++ - 链表

结构特性

内存布局

结构样式

结构拓展

单链表

结构定义

节点关联

插入节点

删除节点

常见操作

双链表

环链表

结构容器

结构设计

结构特性

线性结构的存储方式
- 顺序存储 - 数组
- 链式存储 - 链表
线性结构的链式存储是通过任意的存储单元来存储线性表当中的数据元素。
- 存储单元可以是连续的也可以是不连续的。
- 线性结构的顺序存储中每个元素只需要存储其元素数据即可。
- 线性结构的链式存储除了存储元素数据外，还有存储后继元素的内存地址。
结构概念
- 节点(Node) - 链式存储结构中的元素单位为节点，通常由数据域和指针域共同组成。
- 数据域(Data) - 存储节点值。
- 指针域(Next) - 存储节点指向的下一个节点的内存地址。
- 头节点(Head) - 链表头部节点。
- 尾节点(Tail) - 链表的结束位置节点，其指针域指向NULL，表示了链表结束。

内存布局

链式存储
节点样式

结构样式

单链表
- 每个节点只有一个指针域，指向下一个节点。
双向链表
- 每个节点存在两个指针域，一个指向前节点，一个指向后节点。
循环链表
- 链表尾部节点指向头节点。

结构拓展

单链表

结构定义

typedef struct ListNode
{//数据域int value;//指针域ListNode* Next;//赋值域ListNode(int num) : value(num), Next(nullptr){}
};

节点关联

	ListNode* Node1 = new ListNode(1);ListNode* Node2 = new ListNode(2);ListNode* Node3 = new ListNode(3);ListNode* Node4 = new ListNode(4);ListNode* Node5 = new ListNode(5);Node1->Next = Node2;Node2->Next = Node3;Node3->Next = Node4;Node4->Next = Node5;Node5->Next = NULL;

插入节点

void Insert(ListNode* Cur, ListNode* Node)
{ListNode* Temp = Cur->Next;Cur->Next = Node;Node->Next = Temp;
}

删除节点

void Remove(ListNode* Cur)
{//当前节点.Next = 当前节点.下一个节点.下一个节点ListNode* Node6 = Cur->Next;ListNode* Node3 = Node6->Next;Cur->Next = Node3;delete Node6;
}

常见操作

	//遍历节点int nIndex = 0;ListNode* pTemp = Node1;while (pTemp != NULL){printf("Index -> [%d] -> Data -> [%d] \r\n", nIndex, pTemp->value);++nIndex;pTemp = pTemp->Next;}

双链表

#include <iostream>class ListNode
{
public://数据域int value;//指针域ListNode* Prev;ListNode* Next;//赋值域ListNode(int Num): value(Num), Prev(nullptr), Next(nullptr) {}
};//追加节点
void Append(ListNode* Head , int val)
{ListNode* newNode = new ListNode(val);ListNode* tempNode = Head;while (tempNode->Next != NULL){tempNode = tempNode->Next;}tempNode->Next = newNode;newNode->Prev = tempNode;newNode->Next = NULL;}//添加节点
void Insert(ListNode* Head, int val)
{ListNode* newNode = new ListNode(val);ListNode* HeadNext = Head->Next;Head->Next = newNode;newNode->Prev = Head;newNode->Next = HeadNext;HeadNext->Prev = newNode;/*Node2.Next = NodeCC;NodeCC.Prev = Node2;NodeCC.Next = Node3;Node3.Prev = NodeCC;*/}//移除节点
void Remove(ListNode* Head)
{ListNode* tempNode = Head;while (tempNode->Next != NULL){tempNode = tempNode->Next;}tempNode->Prev->Next = NULL;delete tempNode;
}//删除节点
void Erase(ListNode* Head)
{//当前节点.上一个.下一个 = 当前节点.下一个//当前节点.下一个.上一个 = 当前节点.上一个Head->Prev->Next = Head->Next;Head->Next->Prev = Head->Prev;
}int main()
{ListNode* Node1 = new ListNode(1);ListNode* Node2 = new ListNode(2);ListNode* Node3 = new ListNode(3);ListNode* Node4 = new ListNode(4);ListNode* Node5 = new ListNode(5);Node1->Prev = NULL;Node1->Next = Node2;Node2->Prev = Node1;Node2->Next = Node3;Node3->Prev = Node2;Node3->Next = Node4;Node4->Prev = Node3;Node4->Next = Node5;Node5->Prev = Node4;Node5->Next = NULL;Append(Node1 ,0xCC);Insert(Node2 ,0xDD);Remove(Node1);Erase(Node3);return 0;
}

环链表

#include <iostream>class ListNode
{
public://数据域int value;//指针域ListNode* Next;//赋值域ListNode(int Num) : value(Num), Next(nullptr){}
};int main()
{ListNode* Node1 = new ListNode(1);ListNode* Node2 = new ListNode(2);ListNode* Node3 = new ListNode(3);ListNode* Node4 = new ListNode(4);ListNode* Node5 = new ListNode(5);Node1->Next = Node2;Node2->Next = Node3;Node3->Next = Node4;Node4->Next = Node5;Node5->Next = Node1;ListNode* tempNode = Node1;do{printf("%d \r\n", tempNode->value);tempNode = tempNode->Next;} while (tempNode != Node1);return 0;
}

结构容器

std:list
构造函数
- 默认构造函数
- 有参构造函数
- 拷贝构造函数
- 列表构造函数
- 默认析构函数
大小函数
- 节点数量
- 是否为空
- 清空数据
功能函数
- 插入元素
- 头部插入
- 尾部插入
- 指定插入
- 删除元素
- 修改元素
- 访问元素

结构设计

#include <iostream>class Node
{
public://数据域int value;//指针域Node* Prev;Node* Next;//赋值域Node(int Num, Node* p = nullptr, Node* n = nullptr) : value(Num), Prev(p), Next(n) {}
};class List
{
public://头部节点Node* Head;//尾部节点Node* Tail;//节点数量size_t size;public://默认构造List();//有参构造List(int Count, int value);//拷贝构造List(const List& ref);//列表构造List(std::initializer_list<int> initList);//默认析构~List();public://是否为空bool IsEmpty();//节点数量size_t GetSize();//清空容器void Clear();public://尾部插入void Push_Back(int value);//头部插入void Push_Front(int value);//指定插入void Insert(int InsertValue, int value);//尾部移除void Pop_Back();//头部移除void Pop_Front();//按值匹配void Remove(int value);//查找节点bool Find(int value);public://赋值运算符List& operator=(const List & other);//下标运算符int& operator[](int Index);};std::ostream& operator<<(std::ostream& output, const List& obj);List::List()
{this->Head = nullptr;this->Tail = nullptr;this->size = 0;
}List::List(int Count, int value) : Head(nullptr), Tail(nullptr), size(0)
{while (Count--){Push_Back(value);}
}List::List(const List& ref) : Head(nullptr), Tail(nullptr), size(0)
{Node* node = ref.Head;while (node){Push_Back(node->value);node = node->Next;}
}List::List(std::initializer_list<int> initList) : Head(nullptr), Tail(nullptr), size(0)
{for (auto value : initList){Push_Back(value);}
}List::~List()
{Clear();
}bool List::IsEmpty()
{return this->size == 0 ? true : false;
}size_t List::GetSize()
{return this->size;
}void List::Clear()
{if (IsEmpty()) return;Node* node = this->Head;while (node){Node* Temp = node->Next;delete node;node = Temp;}Head = Tail = nullptr;size = 0;
}void List::Push_Back(int value)
{//创建对象时关联前后节点对象Node* node = new Node(value, Tail, nullptr);//当前容器是否存在尾节点if (Tail != nullptr){Tail->Next = node;}//修正尾部节点Tail = node;//判断头部节点if (Head == nullptr){Head = node;}++this->size;
}void List::Push_Front(int value)
{Node* node = new Node(value, nullptr, Head);if (Head != nullptr){Head->Prev = node;}Head = node;if (Tail == nullptr){Tail = node;}++this->size;
}void List::Insert(int InsertValue, int value)
{Node* node = Head;while (node != nullptr && node->value != InsertValue){node = node->Next;}if (node != nullptr){Node* InsertNode = new Node(value, node, node->Next);if (node->Next != nullptr){node->Next->Prev = InsertNode;}else{Tail = InsertNode;}node->Next = InsertNode;++this->size;}}void List::Pop_Back()
{if (Tail == nullptr){return;}//保存尾节点Node* temp = Tail;//修正尾节点Tail = Tail->Prev;if (Tail == nullptr){Head = nullptr;}else{Tail->Next = nullptr;}delete temp;--this->size;
}void List::Pop_Front()
{if (Head == nullptr){return;}Node* temp = Head;Head = Head->Next;if (Head == nullptr){Tail = nullptr;}else{Head->Prev = nullptr;}delete temp;--this->size;
}void List::Remove(int value)
{Node* node = Head;while (node != nullptr && node->value != value){node = node->Next;}if (node != nullptr){if (node == Head) Pop_Front();else if (node == Tail) Pop_Back();else{node->Prev->Next = node->Next;node->Next->Prev = node->Prev;delete node;--this->size;}}}bool List::Find(int value)
{Node* node = Head;while (node != nullptr){if (node->value == value) return true;node = node->Next;}return false;
}List& List::operator=(const List& other)
{if (this != &other){//删除默认数据Clear();Node* node = other.Head;while (node){Push_Back(node->value);node = node->Next;}}return *this;
}int& List::operator[](int Index)
{Node* node = Head;int Count = 0;while (node != nullptr && Count < Index){node = node->Next;++Count;}if (node != nullptr){return node->value;}
}std::ostream& operator<<(std::ostream& output, const List& obj)
{Node* node = obj.Head;while (node != nullptr){output << node->value;if (node->Next != nullptr){output << " | ";}node = node->Next;}return output;
}int main()
{//默认构造函数List myList1;//有参构造函数List myList3(3, 0xCC);//列表构造函数List myList4 = { 1,2,3,4,5 };//拷贝构造函数List myList5 = myList4;//赋值运算符List myList6;myList6 = myList5;std::cout << myList6 << std::endl;return 0;
}