定义

单链表是一种线性数据结构，用一组地址任意存储单元来存储数据，存储单元分散在内存任意地址上，存储单元之间用指针连接。

单链表一般有两种：

讯享网

• 带头结点的，头结点不存放数据，只是为了操作方便。
• 不带头结点的。

链表只要得到头指针就可以操作每一个结点。

示例

定义

//数据结点 template <typename T>struct linkeNode { T data; linkeNode * next{nullptr}; }; template <typename T> class singlyLinkedList { public: singlyLinkedList() { } ~singlyLinkedList() { freeAllNode(); } void append(const T &data);//在末尾插入 void freeOneNode(linkeNode<T> *node);//清空一个结点 void freeAllNode();//清空所有结点 void traverseSequenceList();//遍历 void insert(const unsigned int index, const T &data);//在index处插入一个结点 void removeOne(const unsigned int index);//移除index处的结点 private: linkeNode<T> * header{nullptr};//首结点指针 };

清除一个结点

讯享网//清除一个结点 template <typename T> void singlyLinkedList<T>::freeOneNode(linkeNode<T> * node) { node->next = nullptr; free(node); }

清除所有结点

//清除所有结点 template <typename T> void singlyLinkedList<T>::freeAllNode() { if(header) { linkeNode<T> * thisNode = header; while (thisNode) { linkeNode<T> * p = thisNode->next; freeOneNode(thisNode); thisNode = p; } header = nullptr; } }

在末尾插入 

讯享网//在末尾插入 template <typename T> void singlyLinkedList<T>::append(const T & data) { if(!header) { header = static_cast<linkeNode<T>*>(malloc(sizeof (linkeNode<T>))); header->data = data; header->next = nullptr; return; } linkeNode<T> * thisNode = header; while (thisNode) { if(thisNode->next) { thisNode = thisNode->next; } else { linkeNode<T> * node = static_cast<linkeNode<T>*>(malloc(sizeof (linkeNode<T>))); node->data = data; node->next = nullptr; thisNode->next = node; break; } } }

遍历 

//遍历 template <typename T> void singlyLinkedList<T>::traverseSequenceList() { if(header) { linkeNode<T> * thisNode = header; int index = {0}; while (thisNode) { qDebug()<<"index = "<<index<< thisNode->data; if(!thisNode->next) { break; } thisNode = thisNode->next; ++index; } } }

在index处插入 

讯享网//在index处插入 template <typename T> void singlyLinkedList<T>::insert(const unsigned int index, const T &data) { if(!header) { header = static_cast<linkeNode<T>*>(malloc(sizeof (linkeNode<T>))); header->data = data; header->next = nullptr; return; } linkeNode<T> * thisNode = header; int currentIndex = {1}; while (thisNode) { if(currentIndex == index) { linkeNode<T> * node = static_cast<linkeNode<T>*>(malloc(sizeof (linkeNode<T>))); node->data = data; linkeNode<T> * newNodeNext = thisNode->next; thisNode->next = node; node->next = newNodeNext; break; } thisNode = thisNode->next; ++currentIndex; } }

删除index处的数据 

//删除index处的数据 template <typename T> void singlyLinkedList<T>::removeOne(const unsigned int index) { if(!header) { return; } if(index == 0) { linkeNode<T> * headerNextNode = header->next; freeOneNode(header); header = headerNextNode; return; } linkeNode<T> * thisNode = header; linkeNode<T> * lastNode = nullptr; int currentIndex = {0}; while (thisNode) { if(currentIndex == index) { linkeNode<T> * willRemoveNode = thisNode; lastNode->next = thisNode->next; freeOneNode(willRemoveNode); break; } lastNode = thisNode; thisNode = thisNode->next; ++currentIndex; } }

汇总

讯享网#include <QDebug> //数据结点 template <typename T>struct linkeNode { T data; linkeNode * next{nullptr}; }; template <typename T> class singlyLinkedList { public: singlyLinkedList() { } ~singlyLinkedList() { freeAllNode(); } void append(const T &data);//在末尾插入 void freeOneNode(linkeNode<T> *node);//清空一个结点 void freeAllNode();//清空所有结点 void traverseSequenceList();//遍历 void insert(const unsigned int index, const T &data);//在index处插入一个结点 void removeOne(const unsigned int index);//移除index处的结点 private: linkeNode<T> * header{nullptr};//首结点指针 }; //清除一个结点 template <typename T> void singlyLinkedList<T>::freeOneNode(linkeNode<T> * node) { node->next = nullptr; free(node); } //清除所有结点 template <typename T> void singlyLinkedList<T>::freeAllNode() { if(header) { linkeNode<T> * thisNode = header; while (thisNode) { linkeNode<T> * p = thisNode->next; freeOneNode(thisNode); thisNode = p; } header = nullptr; } } //在末尾插入 template <typename T> void singlyLinkedList<T>::append(const T & data) { if(!header) { header = static_cast<linkeNode<T>*>(malloc(sizeof (linkeNode<T>))); header->data = data; header->next = nullptr; return; } linkeNode<T> * thisNode = header; while (thisNode) { if(thisNode->next) { thisNode = thisNode->next; } else { linkeNode<T> * node = static_cast<linkeNode<T>*>(malloc(sizeof (linkeNode<T>))); node->data = data; node->next = nullptr; thisNode->next = node; break; } } } //遍历 template <typename T> void singlyLinkedList<T>::traverseSequenceList() { if(header) { linkeNode<T> * thisNode = header; int index = {0}; while (thisNode) { qDebug()<<"index = "<<index<< thisNode->data; if(!thisNode->next) { break; } thisNode = thisNode->next; ++index; } } } //在index处插入 template <typename T> void singlyLinkedList<T>::insert(const unsigned int index, const T &data) { if(!header) { header = static_cast<linkeNode<T>*>(malloc(sizeof (linkeNode<T>))); header->data = data; header->next = nullptr; return; } linkeNode<T> * thisNode = header; int currentIndex = {1}; while (thisNode) { if(currentIndex == index) { linkeNode<T> * node = static_cast<linkeNode<T>*>(malloc(sizeof (linkeNode<T>))); node->data = data; linkeNode<T> * newNodeNext = thisNode->next; thisNode->next = node; node->next = newNodeNext; break; } thisNode = thisNode->next; ++currentIndex; } } //删除index处的数据 template <typename T> void singlyLinkedList<T>::removeOne(const unsigned int index) { if(!header) { return; } if(index == 0) { linkeNode<T> * headerNextNode = header->next; freeOneNode(header); header = headerNextNode; return; } linkeNode<T> * thisNode = header; linkeNode<T> * lastNode = nullptr; int currentIndex = {0}; while (thisNode) { if(currentIndex == index) { linkeNode<T> * willRemoveNode = thisNode; lastNode->next = thisNode->next; freeOneNode(willRemoveNode); break; } lastNode = thisNode; thisNode = thisNode->next; ++currentIndex; } }