实现双向链表（用于 Arduino 板）

• 下载源码 - 170 KB

目录

• 引言
  • 为什么不使用 std::list？
• 风险
• 背景
  • 双向链表的工作原理
• Using the Code
  • 模板 ListItem 的声明
  • 私有结构和变量
  • 构造函数
  • 公共方法
    • void Add (ListItem)
    • void RemoveAt (int)
    • ListItem GetAt (int)
    • ListItem First ()
    • ListItem Last ()
    • int Count ()
    • void Clr ()
  • 析构函数

引言

在做一个个人项目时，我遇到了一个用例，我需要一个表示命令的类，该命令具有未知数量的命令参数。你说这没什么难的？好吧，该项目是一个在 Arduino 板上运行的程序，它通过串行接口与一个程序通信（我之前写过一篇关于该主题的 文章），我希望一个命令拥有一个尚未知的命令参数数量。那么该怎么办？对于固定大小的数组进行动态内存重新分配将会非常耗时，尤其是在 Arduino 板上，而且它比简单的双向链表需要更多的内存，因为双向链表的每个元素的内存都是单独分配（和删除）的。

为什么不使用 std::list？

我需要一个命令类，它存储命令参数，使其行为与 Windows 或 Arduino 环境的编译方式完全相同——由于 Arduino 编译器使用自己的 C++ 方言，其中不包含 std::list，因此我无法使用它，这是我决定自己实现列表的主要因素。

另一个重要的决定因素是 Arduino 板的存储能力有限——即使是源代码。std::list 的 STL-Port 会对源代码的大小产生重大影响，因为它实现了许多我可能永远不需要的操作，因此决定采用了自己动手的方法——使用 std::list 并将其缩减到我需要的内容是没有意义的，尤其是我不会拥有完整源代码的版权。

顺便说一下：是的，有一个 适用于 Arduino 的 STL-Port——但据称 STL-Port 会影响板卡的 Flash 和 SRAM 使用。此外，GitHub 页面上列出了一些问题，其中一些问题会影响 List 功能，这是另一个风险——我认为这是一个很棒的特性，但还远未达到生产就绪。

风险

当然，Arduino 平台还没有内置列表实现是有原因的：试想一下，一个板子可能只有 512 字节的 RAM。如果您现在有一个对象，每个对象需要 2 字节的 RAM，并将其动态添加 256 个副本（实际上更少，因为列表本身也需要 RAM）到列表中，脚本执行将（可怕地）停滞，因为板卡 RAM 已满——发生了溢出。使用此列表时要小心，并且在设置边界之前不要动态添加内容。我主要关心的是 AList::Add(ListItem)：如果您添加了一个列表项，并且添加的项导致板卡 RAM 中的总对象溢出，板卡将进入崩溃状态，或重启并重新执行所有操作。有些人问我为什么在这种情况下不抛出异常。我不能，即使我想抛出异常，因为 Arduino C++ 方言不支持异常。

背景

实现一个只有添加、删除和清空列表（以及获取列表计数器）等基本功能的列表并不难——我决定使用 双向链表方法 来避免内存分配操作造成的较大延迟。

双向链表的工作原理

双向链表是元素的集合，通过单个元素之间的指针链接在一起。每个元素有两个指针：一个指向前一个元素，另一个指向列表中的下一个元素。此外，每个元素都有一个变量来存储元素的值。因此，双向链表的图形表示如下所示

上图显示了一个双向链表，包含三个元素（值为 '1'、'2' 和 '3'）。箭头表示从一个双向链表元素到另一个元素的指针。

使用代码

代码主要包含表示列表的类，称为 AList。

实例化该类的一个实例很容易，对于整数值列表，AList 类只需在您的源代码中键入以下内容（不要忘记 #include "AList.h"）

AList<int> myListOfIntegers;

它在头文件 AList.h 中声明如下

#ifndef ALIST_H
#define ALIST_H
template <typename ListItem>
class AList{
  private:
      /** Intended for private representation 
          of a ListItem within the AList class - Internal use only!
      @author Marco Bertschi
      */
      struct PrivateListItem{
        PrivateListItem* prv;
        PrivateListItem* nxt;
        ListItem crnt;
      };
    
    PrivateListItem* last;        //!< The last item of the list.
    PrivateListItem* first;        //!< The first item of the list.
    int count;            //!< Zero-based count of items within the list.
  public:
    AList();
    ~AList();
    ListItem First();
        ListItem Last();
    
    int Count();
    void Add(ListItem listItem);
    void RemAt(int index);
    ListItem GetAt(int index);
    void Clr();
};
#endif //ALIST_H 

模板 ListItem 的声明

template <typename ListItem>
class AList{ //....

保护符之后的第一行声明了 AList 类在方法参数和字段变量中内部使用 ListItem 类型。ListItem 在此用作列表将在编译后保存的类型的占位符——例如，如果一个 AList<int>，编译器将生成一个新的类，它将 ListItem 的每个实例替换为 int。您实际上不会注意到它，但这通常是模板的工作方式。

私有结构和变量

struct PrivateListItem{
  PrivateListItem* prv;
  PrivateListItem* nxt;
  ListItem crnt;
}; 

AList 类有一个名为 PrivateListItem 的内部结构——它用于封装单个双向链表元素。如前一章所述，它包含一个指向下一个（nxt）和上一个（prv）PrivateListItem 的指针，以及一个存储列表中当前项的值（crnt，类型为 ListItem）的变量。

PrivateListItem* last;        //!< The last item of the list.
PrivateListItem* first;        //!< The first item of the list. 
int count;            //!< Zero-based count of items within the list.

AList 类还包含两个指向 PrivateListItem 的私有指针：一个指向列表的第一个项，另一个指向列表的最后一个项。此外，还有一个私有的整数变量，名为 count，用于存储 AList 中的项的零基计数（-1 表示列表为空）。

构造函数

AList 类只有一个默认构造函数，不接受任何参数。为什么还要提到它？

这是因为默认构造函数对于 AList 类的内部功能相当重要，因为它将内部 count 变量初始化为 -1。如果跳过该变量的初始化步骤，其值将是未定义的，导致依赖于 count 变量或 AList<ListItem>::Count() 方法（在 AList 类内外！）的每个方法都出现故障。您可能在想为什么是 -1 而不是零？很简单，因为我决定使 count 为零基，这意味着零值表示列表中存储了一个元素。

 //! Instantiates a new instance of an AList.
/*!
\return        AList<ListItem>        A new instance of an AList.
*/
template <typename ListItem>
AList<ListItem>::AList(){
    count = -1;//-1 == "The list is empty!
}

公共方法

本章解释了 AList 类公开的每个公共方法。

void AList<ListItem>::Add(ListItem)

template <typename ListItem>
void AList<ListItem>::Add(ListItem li){
    PrivateListItem* pLItem = new PrivateListItem;
    pLItem->crnt = li;
    if (count > -1){//If the list contains one or more items
        pLItem->nxt = first;
        pLItem->prv = last;
        last->nxt = pLItem;
        first->prv = pLItem; // Missed fix of head to point to new tail
        last = pLItem;
        count++;
    }
     else if (count == -1){//If no items are present in the list
        first = pLItem;
        last = pLItem;
        pLItem->nxt = pLItem; // He is alone and point to himself
        pLItem->prv = pLItem;
        count = 0; 
    }
}

此方法将 ListItem 添加到列表的末尾。代码看起来有点特别，因为我必须注意列表为空的情况——在这种情况下，列表的最后一个和第一个项指向同一个 PrivateListItem。如果列表中已经至少有一个项，那么只需重新连接（前一个）最后一个项、第一个项和新添加的列表项之间的指针。

void AList<ListItem>::RemoveAt(int)

template <typename ListItem>
void AList<ListItem>::RemAt(int index){
    if (index <= count){
        PrivateListItem* pLItem = last;
        for (int i = 0; i <= index; i++){
            pLItem = pLItem->nxt;
        }
        pLItem->prv->nxt = pLItem->nxt;
        pLItem->nxt->prv = pLItem->prv;
        delete pLItem;
        count--;
    }
}

此方法从列表中删除给定索引处的项。index 必须小于 count 变量，如果未在给定 index 处找到项，则不会通知方法调用者移除失败（方法也不会崩溃——只是我还没有时间实现该功能）。该方法的工作方式是首先检查 index 是否在 count 的范围内——如果 index 大于 count，则跳过方法执行。然后，方法遍历列表中的每个项，同时计数器 i 小于或等于 index（此时，循环跳过，项在列表中的邻居相互连接，项的内存空间被释放，这等于项的删除）。

ListItem AList<ListItem>::GetAt(int)

template <typename ListItem>
ListItem AList<ListItem>::GetAt(int index){
    PrivateListItem* pLItem = first;
    if (index <= count && index > -1){
        int i = 0;
        while(i < index){
            pLItem = pLItem->nxt;
            i++;
        }
    }
    
    return pLItem->crnt;
} 

此方法返回列表中给定 index 处的项—— index 必须小于 <code>count 变量，如果未在给定 index 处找到项（或列表为空），则后续进度未定义——程序可能会崩溃或表现出其他意外行为。

首先，该方法获取列表中的第一个 ListItem。如果索引为正值且小于或等于 AList<ListItem> 的 count 变量，则程序继续遍历列表直到找到给定的 index，然后返回该位置的 ListItem。

CodeProject 会员 Meir Michanie 提交了另一种方法，他修改了此过程以允许负索引，以便获取列表末尾的项。

template <typename ListItem>
ListItem AList<ListItem>::GetAt(int index){
    PrivateListItem* pLItem = first;
    if (index < 0 ) index =count +1 + index;
    if (index <= count && index > -1){
        int i = 0;
        while(i < index){
            pLItem = pLItem->nxt;
            i++;
        }
    }
 
    return pLItem->crnt;
}

例如，GetAt(-2) 将返回倒数第二个项。

ListItem AList<ListItem>::First()

AList<ListItem>::First() 
template <typename ListItem>
ListItem AList<ListItem>::First(){
    return first->crnt;
}

此方法将列表中的第一个项（索引 = 0）作为 ListItem 类型的值返回。注意：如果列表中只存储了一个项，此方法返回的值与 AList<ListItem>::Last() 相同。如果列表为空，请勿调用此方法——它可能导致系统崩溃。

ListItem AList<ListItem>::Last()

template <typename ListItem>
ListItem AList<ListItem>::Last(){
    return last->crnt;
}

此方法将列表中的最后一个项作为 ListItem 类型的值返回。注意：如果列表中只存储了一个项，此方法返回的值与 AList<ListItem>::First() 相同。如果列表为空，请勿调用此方法——它可能导致系统崩溃。

int AList<ListItem>::Count()

template <typename ListItem>
int AList<ListItem>::Count(){
    return count;
}

此方法返回列表中 ListItem 的零基计数，由变量 AList<ListItem>::count 表示。

void AList<ListItem>::Clr()

template <typename ListItem>
void AList<ListItem>::Clr(){
    PrivateListItem* pLItem = first;
    while(count > -1){
        PrivateListItem* tbdListItem = pLItem;
        pLItem = pLItem->nxt;
        delete tbdListItem;
        count--;
    }
}

此方法通过遍历列表中的所有项（从列表索引 0 开始）来删除所有存储在列表中的项。每个 PrivateListItem 的内存空间都被释放，从而有效地删除它们（不建议调用 AList<ListItem>::RemoveAt(int)，因为它会在每次删除单个列表项后重新连接列表项，从而影响操作的执行时间）。

析构函数

template <typename ListItem>
AList<ListItem>::~AList(){
    if (count > -1){
        Clr(); //Clear the List in order to free memory
    }
}

AList 类的析构函数对于避免内存泄漏很重要，因为它调用 AList<ListItem>::Clr()，该函数释放动态分配的内存空间，否则这些空间将一直被 PrivateListItem 占用。