线性表之单向链表

数据结构数据结构线性表之单向链表苏丙榅2024-06-202025-02-201. 单向链表的结构在上一个章节中为大家详细讲解了静态链表，它解决了插入和删除数据的时候大量移动元素的问题，但是解决不了合理分配和使用内存的问题。解决这个问题的最优方案就是使用动态链表，简称链表。

链表和数组都可以称之为线性表，数组是一种顺序存储结构的线性表，而链表是一种链式存储结构的线性表，链表中的节点和节点之间的内存是不连续的，它们之间的前后关系需要通过指针来维系。

关于链表有很多种，比如：单向链表、单向循环链表，双向链表、双向循环链表，并且这些链表可以带头结点也可以不带头结点。

1.1 单向链表节点我们先从单向链表说起，所谓的单向链表就是链表的节点中只有一个指针域，并且这个指针域指向当前节点的下一个节点（后继节点）的地址。

假设单向链表的节点存储的是整形数据，那么该节点的定义如下：

123456// 定义一个节点，此为 C++ 语法struct Node{ int data = 0; Node* next = nullptr;};

对于上图这个单向链表而言：

链表第1个节点中的Next指针保存了第2个节点中Data1的起始地址

链表第2个节点中的Next1指针保存了第3个节点中Data2的起始地址

链表第3个节点中的Next2指针保存了第4个节点中Data3的起始地址

链表最后一个节点中的Next3指针指向了空地址nullptr

通过这种方式我们就可以使用指针维护一个链式结构的线性表了。

1.2 头结点和头指针1.2.1 头结点头结点是为了操作的方便和统一而设立的，放在第一个数据节点之前，其数据域一般没有意义（有时也用来存储链表的长度）。

有了头结点之后，在第一个数据节点前插入新节点和删除第一个数据节点，其操作流程和其他数据节点无异

链表可以有头结点，也可以没有头结点

下图是不带头结点的链表：

下图是带头结点的链表：

通过对比，二者的区别一目了然，平时建议使用带头结点的链表，它的优势在后边的链表操作章节大家会有深刻体会。

链表中的最后一个节点我们将其称之为尾节点，尾节点和其它节点的不同之处在于它的指针域指向的不是下一个数据节点的地址而是空，通常用 NULL（C语言）或者 nullptr（C++）表示。

1.2.2 头指针头指针顾名思义就是指向链表头结点地址的指针，对于链表的操作必须从头指针开始。在编码过程中一般都是通过头指针来辅助我们完成链表的节点插入、节点删除、节点遍历等操作。

对于不带头结点的链表，头指针指向的是第一个数据节点的地址

对于带头结点的链表，头指针指向的是头结点的地址

在进行链表操作的时候定义一个指针让其指向链表的头结点，此时这个指针就是上面所说的头指针了。它是我们操作链表的过程中的一个必要步骤，那么如何对链表进行节点的添加、删除以及遍历呢？接下来我们来逐一分析。

2. 单向链表的操作2.1 链表的遍历和搜索关于链表的遍历应该是链表操作中最简单的操作了，主要步骤如下：

定义一个辅助指针，让指针指向链表的第一个节点，得到头指针

根据头结点的next域指针，访问第二个链表节点，再根据第二个节点的next域指针访问第三个链表节点，以此类推……

判断如果某个链表节点的next域指针指向空(NUL或者nullptr)，遍历结束

如果掌握了链表的遍历，想要搜索链表中的某个节点，大家也就有思路了，只需要在遍历链表过程中，对每个节点进行判断即可。

关于链表的搜索无外乎有两种方式：

按照值搜索：遍历过程中将每个节点的值和要搜索的值进行比较

按照节点搜索：遍历过程中将每个节点的地址和要搜索的节点的地址进行比较

2.2 链表的插入2.2.1 带头结点的插入

场景1：在头部和中间位置插入新节点

对于带头节点的链表而言，在头部插入节点就是把新的数据节点作为链表的第一个数据节点，它是头结点的后继节点。

带头结点的单向链表在进行新节点插入的时候需要判断的情况相对较少，在链表中插入第一个数据节点和在中间位置插入数据节点的处理流程是一样的。

在链表的头部和中间位置（pos）插入新节点需要分以下几步：

创建一个新的节点，并初始化，记作newNode

遍历链表找到pos-1位置的节点，记作preNode

将新节点的后继节点设置为pos位置的节点，也就是newNode->next = preNode->next

重置preNode节点的后继，设置为newNode，即：preNode->next = newNode

温馨提示：第三步、第四步操作是不能颠倒的。

下图是将新节点插入到链表的非第一个数据节点的位置：

下图是将新节点作为第一个数据节点插入到链表中：

有图有真相，证明在以上两种情况下插入新节点的操作流程是相同的。

场景2：在尾部插入新节点

在链表的尾部添加新节点就是让原来的尾节点指向新节点的地址，让新节点的指针域指向空地址。主要的操作步骤如下：

遍历链表并找到它的尾节点，记作tailNode

创建一个新的链表节点，记作newNode，并初始化，有两种方式：

newNode->next = nullptr

newNode->next = tailNode->next

让找到的尾节点的指针域指向新创建的节点的地址，tailNode->next = newNode

在链表尾部添加新节点的时候，上图中两条红色的线，先连接哪一条取决于 newNode 节点的 next 域的初始化方式（详见步骤2）。

2.2.2 不带头结点的插入如果是带头结点的链表，在进行链表操作的过程中永远不会出现链表中没有任何节点的情况。如果链表没有头结点在进行插入操作的时候就需要单独对这种情况进行判断。

场景1：空链表

如果链表为空链表，那么新添加的节点就是链表的第一个数据节点。另外，如果有头指针需要让头指针指向这个新添加的节点。

场景2：在头部插入新节点

将新的节点插入到链表头部的操作相对简单，操作流程如下：

创建一个新的链表节点

使用新的链表节点的next域指针指向原来的链表头结点

如果有头指针需要让头指针前移，指向这个新添加的节点

场景3：在链表中间位置插入新节点

在链表的中间位置（pos）插入新节点的操作步骤如下：

创建一个新的节点，并初始化，记作newNode

遍历链表找到pos-1位置的节点，记作preNode

将新节点的后继节点设置为pos位置的节点，也就是newNode->next = preNode->next

重置preNode节点的后继，设置为newNode，即：preNode->next = newNode

温馨提示：第三步、第四步操作是不能颠倒的。

场景4：在链表尾部插入新节点

在链表的尾部添加新节点主要的操作步骤如下：

遍历链表并找到它的尾节点，记作tailNode

创建一个新的链表节点，记作newNode，并初始化，有两种方式：

newNode->next = nullptr

newNode->next = tailNode->next

让找到的尾节点的指针域指向新创建的节点的地址，tailNode->next = newNode

通过上面的分析可以得出结论，对于不带头结点的链表而言，在处理插入节点的过程中比带头结点的链表要判断更多的情况。另外，两种链表在中间位置以及尾部添加新节点的时候，处理流程是相同的。

2.3 链表的删除2.3.1 带头结点的删除

场景1：删除头部和中间位置的节点

对于带头结点的链表而言，所谓的删除头部节点指的就是删除链表中的第一个数据节点。

删除带头结点的链表中的第一个数据节点和中间位置的数据节点的流程是一样的，不会出现链表中没有节点的情况。

删除头部和中间位置（pos）的节点的处理流程如下：

遍历链表，搜索链表的节点，找到要删除的节点的上一个节点（pos-1），记作preNode

通过preNode找到要删除的节点，记作delNode

delNode = preNode->next

将delNode从链表中移除，即preNode->next = delNode->next

释放delNode节点指向的内存资源

下图为删除链表第一个数据节点的示意图:

下图为删除链表中间位置的数据节点的示意图:

场景2：删除尾部节点

删除链表尾部节点的处理流程如下:

遍历链表找到链表的倒数第二个节点，记作preNode

通过preNode找到要删除的节点，记作delNode

delNode = preNode->next

让preNode节点的指针域指向空地址，有两种处理方式

preNode->next = nullptr

preNode->next = delNode->next

释放delNode节点指向的内存资源

通过以上两种场景下操作流程的对比可以得到一个结论：对于带头结点的单向链表，删除链表中任意位置的节点的处理流程都是相同的。

2.3.2 不带头结点的删除如果是不带头结点的链表，在进行节点删除的时候会出现链表为空（没有任何节点）的情况，对于这种特殊情况需要单独进行处理。

场景1：删除链表中唯一的数据节点

删除了链表中唯一的数据节点之后，链表中就没有任何节点了。另外，如果有头指针，在进行了删除操作之后，应该让它指向一个空地址。

场景2：删除链表的第一个数据节点

删除链表的第一个数据节点的操作如下：

通过头指针找到链表的第一个数据节点，将其记作delNode

链表头指针后移一个节点

释放delNode节点占用的内存资源

场景3：删除链表中间位置的数据节点

删除链表中间位置的节点的处理流程如下：

遍历链表并搜索，找到要删除的节点的上一个节点，记作preNode

通过preNode找到要删除的节点，记作delNode

delNode = preNode->next

将delNode从链表中移除，即preNode->next = delNode->next

释放delNode节点指向的内存资源

场景4：删除链表尾部的数据节点

删除链表尾部节点的处理流程如下:

遍历链表找到链表的倒数第二个节点，记作preNode

通过preNode找到要删除的节点，记作delNode

delNode = preNode->next

让preNode节点的指针域指向空地址，有两种处理方式

preNode->next = nullptr

preNode->next = delNode->next

释放delNode节点指向的内存资源

通过上面的分析可以得出结论：不论是带头结点的链表还是不带头结点的链表，在删除中间位置或者尾部数据节点的时候，操作流程是相同的。

3. 单向链表的实现3.1 带头结点的单向链表在进行链表操作的时候，为了能够提高操作效率以及使用起来更加方便，除了给链表添加一个头指针以外，还可以提供一个尾指针，有了尾指针之后访问链表尾节点的时候时间复杂度就从O(n)变成了O(1)。同理，给链表添加了长度成员之后，每次想要得到链表的长度，就不需要进行遍历了。

头文件1234567891011121314151617181920212223242526272829303132333435363738394041// SLinkList.h#pragma oncestruct Node{ int data = 0; Node* next = nullptr;};// 定义单向链表类class LinkList{public: LinkList(); ~LinkList(); // 判断链表是否为空 bool isEmpty(); // 获取链表节点数量 int length(); // 数据添加到链表头部 void prepend(int data); // 数据添加到链表尾部 void append(int data); // 数据插入到链表任意位置, 第一个数据元素 pos=1 bool insert(int pos, int data); // 搜索数值, 返回节点和位置, 没找到返回nullptr Node* find(int data, int& pos); // 删除节点 bool remove(int pos); // 遍历链表 void display(); // 返回头结点 inline Node* head() { return m_head; } // 返回指定位置的节点的值 int value(int pos);private: int m_length = 0; Node* m_head = nullptr; Node* m_tail = nullptr;};

关于上面链表类中的各个操作函数都有对应的注释说明，在此就不再赘述了。

源文件123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190// SLinkList.cpp#include "SLinkList.h"#include #include using namespace std;LinkList::LinkList() : m_head(new Node){ if (m_head == nullptr) { return; } m_head->next = nullptr; m_tail = m_head;}LinkList::~LinkList(){ Node* p = m_head; while (p != nullptr) { Node* tmp = p; cout << "释放资源: " << tmp->data << endl; p = p->next; delete tmp; }}bool LinkList::isEmpty(){ bool flag = m_head->next == nullptr; return flag;}int LinkList::length(){ return m_length;}void LinkList::prepend(int data){ // 创建新节点 Node* pNode = new Node; if (pNode == nullptr) { cout << "头部添加链表节点失败!\n" << endl; return; } // 初始化 pNode->data = data; pNode->next = m_head->next; if (m_head->next == nullptr) { m_tail = pNode; } m_head->next = pNode; m_length++;}void LinkList::append(int data){ Node* pNode = new Node; pNode->data = data; m_tail->next = pNode; m_tail = pNode; m_length++;}bool LinkList::insert(int pos, int data){ if (pos < 1 || pos > length()+1) { return false; } Node* p = m_head; int j = 0; while (p != nullptr && j < pos - 1) { p = p->next; j++; } Node* pNode = new Node; pNode->data = data; if (length()+1 == pos) { m_tail = pNode; } pNode->next = p->next; p->next = pNode; m_length++; return true;}Node* LinkList::find(int data, int& pos){ pos = 1; Node* p = m_head->next; while (p != nullptr && p->data != data) { p = p->next; pos++; } return p;}bool LinkList::remove(int pos){ if (pos < 1 || pos > length()) { cout << "删除失败, 无效的节点位置" << endl; return false; } Node* p = m_head; for (int i = 0; i < pos - 1; ++i) { p = p->next; } Node* delNode = p->next; p->next = delNode->next; if (delNode->next == nullptr) { m_tail = p; } delete delNode; m_length--; return true;}void LinkList::display(){ Node* p = m_head->next; if (p == nullptr) { cout << "空链表" << endl; return; } cout << "链表值: "; while (p != nullptr) { cout << p->data << " "; p = p->next; } cout << endl;}int LinkList::value(int pos){ assert(pos > 0 && pos <= length()); Node* p = m_head; for (int i = 0; i < pos; ++i) { p = p->next; } return p->data;}int main(){ LinkList lst; bool flag = lst.isEmpty(); cout << "链表是否为空: " << flag << endl; lst.insert(1, 88); lst.prepend(10); lst.append(20); lst.prepend(30); lst.insert(2, 40); lst.insert(1, 50); lst.insert(6, 60); lst.append(100); cout << "链表长度尾: " << lst.length() << endl; lst.display(); int pos = 0; Node* node = lst.find(50, pos); cout << "元素的位置: " << pos << ", 元素值: " << node->data << endl; lst.remove(pos); lst.display(); node = lst.find(100, pos); cout << "元素的位置: " << pos << ", 元素值: " << node->data << endl; lst.remove(pos); lst.display(); node = lst.find(10, pos); cout << "元素的位置: " << pos << ", 元素值: " << node->data << endl; lst.remove(pos); lst.display(); lst.append(200); lst.display(); return 0;}

在上面的代码中，insert和remove函数支持操作的链表位置有三处：头部（第一个数据节点）、中间、尾部。

执行程序，终端输出的信息为：

1234567891011121314151617链表是否为空: 1链表长度尾: 8链表值: 50 30 40 10 88 60 20 100元素的位置: 1, 元素值: 50链表值: 30 40 10 88 60 20 100元素的位置: 7, 元素值: 100链表值: 30 40 10 88 60 20元素的位置: 3, 元素值: 10链表值: 30 40 88 60 20链表值: 30 40 88 60 20 200释放资源: 0释放资源: 30释放资源: 40释放资源: 88释放资源: 60释放资源: 20释放资源: 200

对于上面链表类中的某些API函数带有一个整形的节点位置pos，该位置的值是从1开始的，也就是说链表中第一个数据节点的位置是1。

3.2 不带头节点的单向链表头文件12345678910111213141516171819202122232425262728293031323334353637// SLinkList1.h#pragma once// 定义节点struct Node{ int data = 0; Node* next = nullptr;};class LinkList1{public: LinkList1(); ~LinkList1(); // 判断链表是否为空 bool isEmpty(); // 得到链表长度 int length(); // 数据添加到链表头部 void prepend(int data); // 数据添加到链表尾部 void append(int data); // 数据插入到链表任意位置, 第一个数据元素 pos=1 bool insert(int pos, int data); // 搜索数值, 返回节点和位置, 没找到返回nullptr Node* find(int data, int& pos); // 删除节点 bool remove(int pos); // 遍历链表 void display();private: int m_length = 0; Node* m_head = nullptr; Node* m_tail = nullptr;};

源文件123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184// SLinkList1.cpp#include "SLinkList1.h"#include using namespace std;LinkList1::LinkList1(){}LinkList1::~LinkList1(){ Node* p = m_head; while (p != nullptr) { Node* tmp = p; cout << "释放资源: " << tmp->data << endl; p = p->next; delete tmp; }}bool LinkList1::isEmpty(){ return m_head == nullptr;}int LinkList1::length(){ return m_length;}void LinkList1::prepend(int data){ Node* pNode = new Node; pNode->data = data; if (m_head == nullptr) { m_tail = pNode; } pNode->next = m_head; m_head = pNode; m_length++;}void LinkList1::append(int data){ Node* pNode = new Node; pNode->data = data; if (isEmpty()) { m_head = m_tail = pNode; } else { m_tail->next = pNode; m_tail = pNode; } m_length++;}bool LinkList1::insert(int pos, int data){ if (pos<1 || pos>length() + 1) { cout << "插入数据失败, 位置无效" << endl; return false; } Node* pNode = new Node; pNode->data = data; if (pos == length()+1) { m_tail = pNode; } if (pos == 1) { pNode->next = m_head; m_head = pNode; m_length++; return true; } Node* p = m_head; int j = 1; while (p != nullptr && j < pos - 1) { p = p->next; j++; } pNode->next = p->next; p->next = pNode; m_length++; return true;}Node* LinkList1::find(int data, int& pos){ pos = 1; Node* p = m_head; while (p != nullptr && p->data != data) { p = p->next; pos++; } return p; }bool LinkList1::remove(int pos){ if (pos<1 || pos>length()) { return false; } Node* p = m_head; if (pos == 1) { m_head = p->next; delete p; m_length--; return true; } for (int i = 2; i < pos; ++i) { p = p->next; } Node* delNode = p->next; p->next = delNode->next; if (delNode->next == nullptr) { m_tail = p; } delete delNode; m_length--; return true;}void LinkList1::display(){ if (m_head == nullptr) { cout << "空链表" << endl; return; } Node* p = m_head; cout << "链表值: "; do { cout << p->data << " "; p = p->next; } while (p != nullptr); cout << endl;}int main(){ LinkList1 lst; bool flag = lst.isEmpty(); cout << "链表是否为空: " << flag << endl; lst.insert(1, 88); lst.prepend(10); lst.append(20); lst.prepend(30); lst.insert(2, 40); lst.insert(1, 50); lst.insert(7, 60); lst.append(100); cout << "链表长度: " << lst.length() << endl; lst.display(); int pos = 0; Node* node = lst.find(50, pos); cout << "元素的位置: " << pos << ", 元素值: " << node->data << endl; lst.remove(pos); lst.display(); node = lst.find(100, pos); cout << "元素的位置: " << pos << ", 元素值: " << node->data << endl; lst.remove(pos); lst.display(); node = lst.find(10, pos); cout << "元素的位置: " << pos << ", 元素值: " << node->data << endl; lst.remove(pos); lst.display(); lst.append(200); lst.display(); return 0;}

在上面的代码中，insert和remove函数支持操作的链表位置有三处：头部、中间、尾部。

执行程序，终端打印的信息如下：

12345678910111213141516链表是否为空: 1链表长度: 8链表值: 50 30 40 10 88 20 60 100元素的位置: 1, 元素值: 50链表值: 30 40 10 88 20 60 100元素的位置: 7, 元素值: 100链表值: 30 40 10 88 20 60元素的位置: 3, 元素值: 10链表值: 30 40 88 20 60链表值: 30 40 88 20 60 200释放资源: 30释放资源: 40释放资源: 88释放资源: 20释放资源: 60释放资源: 200

比较上面的两份代码，证明不带头结点的链表在进行节点插入、删除的时候确实是要处理更多的情况，这样无疑就给bug的滋生提供了更多的生存空间。