令狐掌门

令狐掌门

关注
发信
关注(28)粉丝(399)

C++手写链表、反转链表、删除链表节点、遍历、为链表增加迭代器

  本篇博客介绍如何使用C++实现链表，首先编写一个简单的链表，然后增加模板，再增加迭代器。

简单链表的实现

  链表的结构如下：
C++手写链表、反转链表、删除链表节点、遍历、为链表增加迭代器-LMLPHP

  首先需要定义链表的节点：

struct ListNode
{
    int data;
    ListNode* pNext;

    ListNode(int value = 0):
        data(value), pNext(nullptr){}
};

  再定义链表类

class LinkedList
{
public:
    LinkedList():m_pHead(nullptr)
    {

    }

    ~LinkedList()
    {
        Clear();
    }

    void Add(int value)
    {
        if(!m_pHead)
        {
            m_pHead = new ListNode(value);
        }
        else
        {
            ListNode* current = m_pHead;

            while(current->pNext)
            {
                current = current->pNext;
            }

            current->pNext = new ListNode(value);
        }
    }

    void PrintList()
    {
        if(!m_pHead)
        {
            cout << "LinkedList is empty" << endl;
            return;
        }

        ListNode* current = m_pHead;

        while (current)
        {
            cout << current->data << " ";
            current = current->pNext;
        }
        
        cout << endl;
    }

    // 反转链表
    void Reverse() {
        ListNode* prev = nullptr;
        ListNode* current = m_pHead;
        ListNode* next = nullptr;

        // 从头节点开始反转，让头节点指向空，让下一个节点指向头节点
        while (current != nullptr) {
            next = current->pNext;   // 保存下一个节点
            current->pNext = prev;   // 反转当前节点的指针
            prev = current;         // 更新prev到当前节点
            current = next;         // 移动到下一个节点
        }

        m_pHead = prev; // 更新头节点
    }

    // 删除第一个具有指定值的元素
    void Remove(int val) {
        if (!m_pHead)
            return;

        // 如果要删除的是头节点
        if (m_pHead->data == val) {
            ListNode* toDelete = m_pHead;
            m_pHead = m_pHead->pNext;
            delete toDelete;
            return;
        }

        ListNode* current = m_pHead;
        while (current->pNext && current->pNext->data != val) {
            current = current->pNext;
        }

        if (current->pNext) {
            ListNode* toDelete = current->pNext;
            current->pNext = current->pNext->pNext;
            delete toDelete;
        }
    }

    void Clear()
    {
        while (m_pHead)
        {
            ListNode* pDelete = m_pHead;
            m_pHead = m_pHead->pNext;
            delete pDelete;
            pDelete = nullptr;
        }
    }

private:
    ListNode* m_pHead;
};

  main代码测试：

#include <iostream>
#include "LinkedList0.h"

using namespace std;

int main()
{   
    LinkedList* pList = new LinkedList();
    pList->Add(1);
    pList->Add(4);
    pList->Add(7);
    pList->Add(10);

    pList->PrintList();

    pList->Reverse();

    pList->PrintList();

    pList->Remove(7);

    pList->PrintList();

    delete pList;
    pList = nullptr;

    return 0;
}

运行结果如下：
1 4 7 10
10 7 4 1
10 4 1

如何添加链表元素

  首先根据头指针的位置，将头指针移到末尾，当然这里使用的临时指针current 来移动，然后将头结点的next只想新的结点, 头指针m_pHead的地址并没有变化。

void Add(int value)
{
    if(!m_pHead)
    {
        m_pHead = new ListNode(value);
    }
    else
    {
        ListNode* current = m_pHead;

        while(current->pNext)
        {
            current = current->pNext;
        }

        current->pNext = new ListNode(value);
    }
}

如何清空链表

  从链表头开始依次清空

void Clear()
 {
     while (m_pHead)
     {
         ListNode* pDelete = m_pHead;
         m_pHead = m_pHead->pNext;
         delete pDelete;
         pDelete = nullptr;
     }
 }

  这里也是移动头指针，知道达到尾结点的next.

如何删除链表节点

  删除链表节点会改变当前节点的指向，如果删除的是头结点，则比较简单，删除其它结点相对复杂

如何反转链表

  反转链表也是面试中的经常考察的点，需要非常熟练，主要是思路，从头结点开始原地反转，只是代码的写法相对复杂点，一旦操作顺序不对，很容易出错，代码如下：

// 反转链表
void Reverse() {
    ListNode* prev = nullptr;
    ListNode* current = m_pHead;
    ListNode* next = nullptr;

    // 从头节点开始反转，让头节点指向空，让下一个节点指向头节点
    while (current != nullptr) {
        next = current->pNext;   // 保存下一个节点
        current->pNext = prev;   // 反转当前节点的指针
        prev = current;         // 更新prev到当前节点
        current = next;         // 移动到下一个节点
    }

    m_pHead = prev; // 更新头节点
}

链表模板的实现

  代码如下：

/*

自定义链表 
添加迭代器

*/


#pragma once
#include <iostream>

using namespace std;

template<class T>
struct ListNode
{
    T data;
    ListNode<T>* pNext;

    ListNode(T value = 0):
        data(value), pNext(nullptr){}
};

// 迭代器类
template<typename T>
class LinkedListIterator {
public:
    explicit LinkedListIterator(ListNode<T>* node) : m_node(node) {}

    T& operator*() const { 
        cout << "run T& operator*() const " << endl;
        return m_node->data; 
    }

    T* operator->() { 
        cout << "run T* operator->()" << endl;
        return &m_node->data; 
    }

    // 前缀递增
    LinkedListIterator& operator++() {
        cout << "run LinkedListIterator 前缀递增" << endl;
        m_node = m_node->pNext;
        return *this;
    }

    // 后缀递增
    LinkedListIterator operator++(int) {
        cout << "run LinkedListIterator 后缀递增" << endl;
        LinkedListIterator temp = *this;
        m_node = m_node->pNext;
        return temp;
    }

    friend bool operator==(const LinkedListIterator& a, const LinkedListIterator& b) {
        return a.m_node == b.m_node;
    };

    friend bool operator!=(const LinkedListIterator& a, const LinkedListIterator& b) {
        return a.m_node != b.m_node;
    };

private:
    ListNode<T>* m_node;
};

template<class T>
class LinkedList
{
public:
    using iterator = LinkedListIterator<T>;   // 先声明，并且是public, 不然在外部无法使用
 
public:
    LinkedList():m_pHead(nullptr)
    {

    }

    ~LinkedList()
    {
        Clear();
    }

    void Add(T value)
    {
        if(!m_pHead)
        {
            m_pHead = new ListNode<T>(value);
        }
        else
        {
            ListNode<T>* current = m_pHead;

            while(current->pNext)
            {
                current = current->pNext;
            }

            current->pNext = new ListNode<T>(value);
        }
    }

    void PrintList()
    {
        if(!m_pHead)
        {
            cout << "LinkedList is empty" << endl;
            return;
        }

        ListNode<T>* current = m_pHead;

        while (current)
        {
            cout << current->data << " ";
            current = current->pNext;
        }
        
        cout << endl;
    }

    // 反转链表
    void Reverse() {
        ListNode<T>* prev = nullptr;
        ListNode<T>* current = m_pHead;
        ListNode<T>* next = nullptr;

        // 从头节点开始反转，让头节点指向空，让下一个节点指向头节点
        while (current != nullptr) {
            next = current->pNext;   // 保存下一个节点
            current->pNext = prev;   // 反转当前节点的指针
            prev = current;         // 更新prev到当前节点
            current = next;         // 移动到下一个节点
        }

        m_pHead = prev; // 更新头节点
    }

    // 删除第一个具有指定值的元素
    void Remove(T val) {
        if (!m_pHead)
            return;

        // 如果要删除的是头节点
        if (m_pHead->data == val) {
            ListNode<T>* toDelete = m_pHead;
            m_pHead = m_pHead->pNext;
            delete toDelete;
            return;
        }

        ListNode<T>* current = m_pHead;
        while (current->pNext && current->pNext->data != val) {
            current = current->pNext;
        }

        if (current->pNext) {
            ListNode<T>* toDelete = current->pNext;
            current->pNext = current->pNext->pNext;
            delete toDelete;
        }
    }

    void Clear()
    {
        while (m_pHead)
        {
            ListNode<T>* pDelete = m_pHead;
            m_pHead = m_pHead->pNext;
            delete pDelete;
            pDelete = nullptr;
        }
    }

    iterator begin() {
        return iterator(m_pHead);
    }

    iterator end() {
        return iterator(nullptr);
    }

private:
    ListNode<T>* m_pHead;
};

  在简单链表的基础上增加模板，这个不难，难得是如何给链表增加迭代器。

  main函数测试：

int main()
{   
    LinkedList<int>* pList = new LinkedList<int>();
    pList->Add(10);
    pList->Add(40);
    pList->Add(70);
    pList->Add(100);

    pList->PrintList();

    pList->Reverse();

    pList->PrintList();

    pList->Remove(70);

    pList->PrintList();

    cout << "使用迭代器" << endl;

    //for(LinkedList<int>::iterator it = pList->begin(); it != pList->end(); it++)
    for(auto it = pList->begin(); it != pList->end(); it++)
    {
        cout << *it << " ";
    }

    cout << endl;

    delete pList;
    pList = nullptr;

    return 0;
}

运行结果如下：
10 40 70 100
100 70 40 10
100 40 10
使用迭代器
run T& operator*() const
100 run LinkedListIterator 后缀递增
run T& operator*() const
40 run LinkedListIterator 后缀递增
run T& operator*() const
10 run LinkedListIterator 后缀递增

如何为链表添加迭代器

  迭代器可以理解为是一个类，在类里封装了对象的++操作之类的方法，声明迭代器类，然后在链表类里声明begin()和end()来获取迭代器，begin()返回指向容器第一个元素的迭代器，而end()返回指向容器末尾的下一个位置的迭代器。比如上面的迭代器声明如下：

// 迭代器类
template<typename T>
class LinkedListIterator {
public:
    explicit LinkedListIterator(ListNode<T>* node) : m_node(node) {}

    T& operator*() const { 
        cout << "run T& operator*() const " << endl;
        return m_node->data; 
    }

    T* operator->() { 
        cout << "run T* operator->()" << endl;
        return &m_node->data; 
    }

    // 前缀递增
    LinkedListIterator& operator++() {
        cout << "run LinkedListIterator 前缀递增" << endl;
        m_node = m_node->pNext;
        return *this;
    }

    // 后缀递增
    LinkedListIterator operator++(int) {
        cout << "run LinkedListIterator 后缀递增" << endl;
        LinkedListIterator temp = *this;
        m_node = m_node->pNext;
        return temp;
    }

    friend bool operator==(const LinkedListIterator& a, const LinkedListIterator& b) {
        return a.m_node == b.m_node;
    };

    friend bool operator!=(const LinkedListIterator& a, const LinkedListIterator& b) {
        return a.m_node != b.m_node;
    };

private:
    ListNode<T>* m_node;
};

  然后再链表类里声明begin和end方法：

using iterator = LinkedListIterator<T>;   // 先声明，并且是public, 不然在外部无法使用

iterator begin() {
    return iterator(m_pHead);
}

iterator end() {
    return iterator(nullptr);
}

  需要注意的是在迭代器类里重写了“前加加”和“后加加”运算符，他们二者有区别

前加加

// 前缀递增
LinkedListIterator& operator++() {
    cout << "run LinkedListIterator 前缀递增" << endl;
    m_node = m_node->pNext;
    return *this;
}

注意这里返回的是引用。

问题：重写"前加加"为什么返回引用？

  在C++中，迭代器的前缀递增（++it）操作符通常返回一个到自身的引用，这样做有几个原因：

  1. 链式操作：返回引用允许连续调用操作符或方法。例如，++(++it)或(*++it).method()。如果不返回自身的引用，这样的操作将无法执行，因为递增操作将不会在原始迭代器上进行。
  2. 性能：通过返回自身的引用，可以避免不必要的对象复制。如果递增操作返回一个新的迭代器实例而不是引用，那么每次递增操作都会产生一个临时迭代器对象，这将增加额外的构造和析构开销。返回引用避免了这些潜在的性能问题。
  3. 一致性和期望：在STL（Standard Template Library，标准模板库）中，迭代器遵循一定的惯例和模式，其中前缀递增返回引用就是这些标准操作之一。遵循这些惯例可以使自定义迭代器的行为与STL中的迭代器保持一致，从而减少使用时的困惑。
  4. 语义清晰：返回自身的引用清楚地表明了前缀递增操作是在修改迭代器本身，而不是创建一个新的迭代器实例。这使得代码的意图更加明确，有助于代码的阅读和维护。

  考虑到这些理由，迭代器设计时通常会使得前缀递增操作符返回迭代器的引用。这是一种约定，也是一种优化设计和实现的方法。而后缀递增（it++）通常返回迭代器的值，这需要创建当前迭代器的一个副本，然后对原迭代器进行递增操作，最后返回副本。这种区别设计允许区分前缀和后缀递增的语义和性能特点。

后加加

代码如下

// 后缀递增
LinkedListIterator operator++(int) {
    cout << "run LinkedListIterator 后缀递增" << endl;
    LinkedListIterator temp = *this;
    m_node = m_node->pNext;
    return temp;
}

问题：为什么“后加加不返回引用”？

  后缀递增操作符（it++）不返回引用的原因是它的语义和行为要求。后缀递增操作的预期行为是先返回迭代器当前的值，然后再对其进行递增。这意味着必须先创建当前状态的一个副本，然后递增原迭代器，最后返回那个副本。这个过程涉及到以下几个关键点：

  1. 值的保留：后缀递增需要保留迭代器递增前的状态。为了实现这一点，它通过创建当前迭代器的一个副本来保存当前状态，然后递增原迭代器，最后返回副本。如果后缀递增返回了引用，那么它将无法满足“先返回当前状态然后递增”的语义要求。
  2. 避免修改返回的迭代器：由于后缀递增返回的是递增前的状态，如果这个返回值是引用，使用者可能会错误地认为对返回的迭代器进行修改会影响到原始迭代器，这与后缀递增的预期行为不符。返回一个副本可以明确表明返回的迭代器是一个全新的、与原迭代器无关的实例。
  3. 语义清晰性：通过返回一个副本而不是引用，后缀递增明确表示了它和前缀递增的不同。前缀递增(++it)表示对原迭代器自身的修改并返回修改后的自身，更适合效率要求较高的场合；而后缀递增(it++)则强调返回原始状态的副本，适用于先使用当前值再递增的场景，即使这意味着可能有额外的性能开销。
  4. 性能考虑：后缀递增的性能通常比前缀递增低，因为它涉及到复制操作。这是设计选择的一部分，开发者在意识到这一点的情况下会倾向于在不需要副本的场景中使用前缀递增，以提高代码的效率。

  综上所述，后缀递增不返回引用是为了满足其特定的语义需求，保证操作的正确性，同时也是为了与前缀递增明确区分，让两者的用途和性能特点更加清晰。

迭代时如何取值

  在使用迭代器中，会有“*it”的取值方法，代码如下：

//for(LinkedList<int>::iterator it = pList->begin(); it != pList->end(); it++)
    for(auto it = pList->begin(); it != pList->end(); it++)
    {
        cout << *it << " ";
    }

  这种“*it”写法，需要重写星号操作符来实现，代码如下：

T& operator*() const { 
    cout << "run T& operator*() const " << endl;
    return m_node->data; 
}

  以上是本篇博客的主要内容，这是链表的基本实现，当然还可以增加锁来实现线程安全，如果在多线程环境担心std容器的安全性，大家可以使用线程安全的容器，比如TBB库提供的容器。TBB链接如下： https://www.intel.com/content/www/us/en/developer/tools/oneapi/onetbb.html

03-16 01:52
Powered by LMLPHP ©2024 令狐掌门 0.002165