数据结构与算法——链表_链表是算法吗

作者：IT小白 | 2024-07-17 16:21:10

踩

链表是算法吗

数据结构与算法——链表

链表

链表

链表的概念

链表是一种通过指针串联在一起的线性数据结构
节点由两部分组成，一个数据域，一个是指针域（存放指向下一个节点的指针)
最后一个节点的指针域为 nullptr

链表的类型

单链表
双链表：双链表的每个节点有两个指针域，一个指向前一个节点，一个指向后一个节点
环形链表

链表的存储方式

链表在内存中不是连续分布的，
链表是通过指针域的指针来链接内存中各个节点的

链表的优缺点

优点：
链表可以轻松的添加元素，适用于经常需要添加删除的场景
缺点：
查询速度慢，指针域需要消耗额外的内存控件

链表节点的定义（C++）

struct Node
{
    int m_nValue;
    Node* m_pNext;
    
    Node(int nValue, Node* pNext = nullptr) : m_nValue(nValue), m_pNext(pNext)
    {
        
    }
};
1
2
3
4
5
6
7
8
9
10

链表类的代码实现

头文件 SingleLinkedList.h

#ifndef SINGLELINKEDLIST_H
#define SINGLELINKEDLIST_H


class SingleLinkedList
{
public:
    const static int ELEMENT_NOT_FIND = -1;

public:
    struct Node
    {
        int m_nValue;
        Node* m_pNext;

        Node(int nValue = 0, Node* pNext = nullptr) : m_nValue(nValue), m_pNext(pNext)
        {
            // ...
        }
    };

public:
    SingleLinkedList();
    ~SingleLinkedList();

public:
    void AddAtHead(int nValue);                                 // 在头部添加节点
    void AddAtTail(int nValue);                                 // 在尾部添加节点
    void Insert(int nValue, int nIndex);                        // 插入节点

    void RemoveAtHead();                                        // 删除头部节点
    void RemoveAtTail();                                        // 删除尾部节点
    void RemoveByValue(int nValue);                             // 删除指定节点（值）
    void RemoveByIndex(int nIndex);                             // 删除指定节点（索引）

    int Get(int nIndex);                                        // 获取 index 的 value
    int IndexOf(int nValue) const;                              // 获取 value 的 index
    bool Empty() const;                                         // 链表是否为空
    bool Contain(int nValue) const;                             // 链表是否包含某个元素
    int Size() const;                                           // 链表长度
    void Print() const;

    void Set(int nValue, int nIndex);                           // 修改 index 节点的 value 值
    void Clear();                                               // 清除链表数据

private:
    Node* FindPreByValue(int nValue);                           // 寻找前驱节点（值）
    Node* FindPreByIndex(int nIndex);                           // 寻找前驱节点（索引）
    void CheckInsertIndex(int nIndex);                          // 检查插入元素的 index
    void CheckIndex(int nIndex);                                // 检查一般操作的 index
    void RemoveNextNode(Node* pPrev);                           // 删除下一个节点（备注：参数为被删除节点的前一个节点）
    void Release();                                             // 释放内存

private:
    Node* m_pDummyHead;                                         // 虚拟头节点
    Node* m_pHead;                                              // 真实头节点
    int m_nSize;                                                // 链表长度
};


#endif // SINGLELINKEDLIST_H

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

源文件 SingleLinkedList.cpp

#include "SingleLinkedList.h"
#include <stdexcept>
#include <iostream>

using namespace std;

SingleLinkedList::SingleLinkedList() : m_pHead(nullptr), m_nSize(0)
{
    m_pDummyHead = new Node();
}

SingleLinkedList::~SingleLinkedList()
{
    Release();
}

void SingleLinkedList::AddAtHead(int nValue)
{
    // 虚拟头节点的后继便是头结点
    // 我们在插入链表的时候，只要找到这个插入结点位置的前一个节点
    // 一行代码便可搞定插入 pPrev->m_pNext = new Node(nValue, pPrev->m_pNext)
    // 这行代码的意义在于把新的节点放在 pPrev 后面， 将原有的 pPrev 后面节点给挪后一个位置
    // 即使 pPrev->m_pNext = nullptr 也适用

    m_pDummyHead->m_pNext = new Node(nValue, m_pDummyHead->m_pNext);

    // 更新头节点
    m_pHead = m_pDummyHead->m_pNext;
    ++m_nSize;
}

void SingleLinkedList::AddAtTail(int nValue)
{
    Node* pCur = m_pDummyHead;

    // 找到链表的最后一个节点
    while (nullptr != pCur->m_pNext)
        pCur = pCur->m_pNext;

    // 添加链表
    pCur->m_pNext = new Node(nValue);

    // 更新头节点，为什么要更新，因为调用这个函数的时候，链表可能还一个节点没有
    // 只有个虚拟的头节点
    m_pHead = m_pDummyHead->m_pNext;

    ++m_nSize;
}

void SingleLinkedList::Insert(int nValue, int nIndex)
{
    // 检查插入的索引是否合理
    CheckInsertIndex(nIndex);

    if (0 == nIndex)
        return AddAtHead(nValue);

    if (m_nSize == nIndex)
        return AddAtTail(nValue);

    // 找到被插入位置的前驱节点
    Node* pPrev = FindPreByIndex(nIndex);

    // 问题 pPrev 一定不为空么？ 答案是一定，为空的可能是 nIndex == m_nSize
    // 在上面代码中已经处理了

    // 这行代码上面有解释
    pPrev->m_pNext  = new Node(nValue, pPrev->m_pNext);
    ++m_nSize;
}

void SingleLinkedList::RemoveAtHead()
{
    // 此时为空链表
    if (nullptr == m_pHead)
        return;

    RemoveNextNode(m_pDummyHead);
}

void SingleLinkedList::RemoveAtTail()
{
    // 此时为空链表
    if (nullptr == m_pHead)
        return;

    Node* pPrev = m_pDummyHead;
    Node* pCur = m_pHead;

    // 让 pCur 指向链表最后一个节点
    while (nullptr != pCur->m_pNext)
    {
        pPrev = pCur;
        pCur = pCur->m_pNext;
    }

    RemoveNextNode(pPrev);
}

void SingleLinkedList::RemoveByValue(int nValue)
{
    // 找到要删除节点的前一个节点
    Node* pPrev = FindPreByValue(nValue);

    RemoveNextNode(pPrev);
}

void SingleLinkedList::RemoveByIndex(int nIndex)
{
    Node* pPrev = FindPreByIndex(nIndex);

    RemoveNextNode(pPrev);
}

int SingleLinkedList::Get(int nIndex)
{
    CheckIndex(nIndex);

    Node* pCur = m_pHead;

    while ((nIndex--) > 0 && nullptr != pCur)
        pCur = pCur->m_pNext;

    return pCur->m_nValue;
}

int SingleLinkedList::IndexOf(int nValue) const
{
    Node* pCur = m_pHead;
    int nIndex = 0;

    while (nullptr != pCur)
    {
        if (pCur->m_nValue == nValue)
            return nIndex;

        pCur = pCur->m_pNext;
        ++nIndex;
    }

    return ELEMENT_NOT_FIND;
}

bool SingleLinkedList::Empty() const
{
    return 0 == m_nSize;
}

bool SingleLinkedList::Contain(int nValue) const
{
    return ELEMENT_NOT_FIND != IndexOf(nValue);
}

int SingleLinkedList::Size() const
{
    return m_nSize;
}

void SingleLinkedList::Print() const
{
    cout << "List Data : [ ";

    Node* pCur = m_pHead;
    while(nullptr != pCur)
    {
        cout << pCur->m_nValue;

        if (nullptr == pCur->m_pNext)
        {
            cout << " ]\n";
            return;
        }
        else
        {
            cout << ", ";
        }

        pCur = pCur->m_pNext;
    }

    cout << " ]\n";
}

void SingleLinkedList::Set(int nValue, int nIndex)
{
    CheckIndex(nIndex);

    // 让 pCur 指向要被修改数据的节点
    Node* pCur = m_pHead;
    while ((nIndex--) > 0 || nullptr != pCur)
        pCur = pCur->m_pNext;

    pCur->m_nValue = nValue;
}

void SingleLinkedList::Clear()
{
    // 备注：虚拟头结点不要删除
    Node* pCur = m_pHead;

    // 一个一个删除节点
    while (nullptr != pCur)
    {
        Node* pDelete = pCur;
        pCur = pCur->m_pNext;
        delete pDelete;
    }

    m_pDummyHead->m_pNext = m_pHead = nullptr;
    m_nSize = 0;
}

SingleLinkedList::Node* SingleLinkedList::FindPreByValue(int nValue)
{
    Node* pPrev = m_pDummyHead;
    Node* pCur = m_pHead;

    while (nullptr != pCur)
    {
        if (nValue == pCur->m_nValue)
            return pPrev;

        pPrev = pCur;
        pCur = pCur->m_pNext;
    }

    // 没找到返回值为 nullptr
    return nullptr;
}

SingleLinkedList::Node* SingleLinkedList::FindPreByIndex(int nIndex)
{
    // nIndex 的值不合理返回值为 nullptr
    if (nIndex < 0 || nIndex >= m_nSize)
        return nullptr;

    Node* pPrev = m_pDummyHead;
    Node* pCur = m_pHead;

    // 让 pCur 节点指向 index 的节点
    while ((nIndex--) > 0 && nullptr != pCur)
    {
        pPrev = pCur;
        pCur = pCur->m_pNext;
    }

    return pPrev;
}

void SingleLinkedList::CheckInsertIndex(int nIndex)
{
    // 插入的位置最大可以为 m_nSize ，也就是链表尾部
    if (nIndex < 0 || nIndex > m_nSize)
        throw out_of_range("CheckInsertIndex(int nIndex) index out of range");
}

void SingleLinkedList::CheckIndex(int nIndex)
{
    if (0 < nIndex || nIndex >= m_nSize)
        throw out_of_range("CheckIndex(int nIndex) index out of range");
}

void SingleLinkedList::RemoveNextNode(SingleLinkedList::Node* pPrev)
{
    if (nullptr == pPrev || nullptr == pPrev->m_pNext)
        return;

    // 找到要被删除的节点
    Node* pDelete = pPrev->m_pNext;

    // 空出要被删除的链表
    pPrev->m_pNext = pPrev->m_pNext->m_pNext;

    // 更新 m_pHead 节点
    m_pHead = m_pDummyHead->m_pNext;

    delete pDelete;
    --m_nSize;
}

void SingleLinkedList::Release()
{
    // 在清除链表的基础上并清除虚拟头节点

    Clear();
    delete m_pDummyHead;
    m_pDummyHead = nullptr;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289

链表的练习

移除链表元素

【题目需求】在链表中删除指定的元素
【示例】
输入：[1,4,2,4], value = 4
输出：[1,2]
解题代码：

//
//  main.cpp
//  ConsoleApp
//
//  Created by Xming on 2022/2/24.
//

#include <iostream>
#include <vector>

using namespace std;

struct Node
{
    int m_nValue;
    Node* m_pNext;
    
    Node(int nValue, Node* pNext = nullptr) : m_nValue(nValue), m_pNext(pNext)
    {
        
    }
};



class Solution
{
public:
    // 删除链表中指定元素的节点
    static Node* RemoveElement(Node* pHead, int nEle)
    {
        Node* pDummyHead  = new Node(0, pHead);
        Node* pPre = pDummyHead;
        Node* pCur = pHead;
        
        while (nullptr != pCur)
        {
            if (pCur->m_nValue == nEle)
            {
                Node* pDelete = pCur;
                pPre->m_pNext = pPre->m_pNext->m_pNext;
                pCur = pCur->m_pNext;
                delete pDelete;
            }
            else
            {
                pPre = pCur;
                pCur = pCur->m_pNext;
            }
        }
        
        pHead = pDummyHead->m_pNext;
        delete pDummyHead;
        return pHead;
    }
    
    // 创建链表
    static Node* CreateList(const vector<int>& vecData)
    {
        if (vecData.empty())
            return nullptr;
        
        Node* pHead = new Node(vecData[0]);
        Node* pCur = pHead;
        for(size_t i = 1; i < vecData.size(); ++i)
        {
            pCur->m_pNext = new Node(vecData[i]);
            pCur = pCur->m_pNext;
        }
        
        return pHead;
    }
    
    // 打印输出链表
    static void PrintList(Node* pHead)
    {
        Node* pCur = pHead;
        cout << "List Data:[ ";
        
        while (nullptr != pCur)
        {
            if (nullptr != pCur->m_pNext)
            {
                cout << pCur->m_nValue << ", ";
            }
            else
            {
                cout << pCur->m_nValue << " ]\n";
            }
            
            pCur = pCur->m_pNext;
        }
    }
    
    // 测试函数
    static void Test()
    {
        vector<int> vecData = { 1, 2, 2, 3, 5 };
        
        Node* pHead = CreateList(vecData);
        PrintList(pHead);
        
        pHead = RemoveElement(pHead, 2);
        PrintList(pHead);
    }
};

int main(int argc, const char * argv[]) {
    
    Solution::Test();
    
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

备注：后续会持续更新链表的相关练习题笔记

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/840881