链接列表示例 - 为什么使用它们？

Question

我正在研究如何获取Unix / iOS / Mac OS X的接口信息（IP地址，接口名称等）的代码块，并希望了解更多使用链接列表的原因。我不是一名全职程序员，但我可以编码并且总是在努力学习。我确实理解基本的C / C ++，但从未有过经验或不得不使用链表。

我正在尝试学习OS X和iOS开发，并试图获取网络接口信息并遇到这个：https://developer.apple.com/library/mac/documentation/Darwin/Reference/ManPages/man3/getifaddrs.3.html

如果我理解正确，它会出现一个链表，用于为每个接口链接一堆结构。为什么在这种情况下使用链表？为什么结构不仅仅是创建并存储在数组中？

谢谢

Answer 1

[...]并希望了解更多使用链接列表的原因。我不是一名全职程序员，但我可以编码并且总是在努力学习。我确实理解基本的C / C ++，但从未有过经验或不得不使用链表。

链表实际上是一个非常简单的数据结构。它们有几种不同，但整体概念只是分配节点并通过索引或指针将它们链接在一起，如下所示：

为什么在这种情况下使用链表？

链接列表有一些有趣的属性，其中一个在上图中注明，如恒定时间删除和从中间插入。

为什么结构不仅仅是创建并存储在数组中？

他们实际上可能是。在上图中，节点可以直接存储在数组中。然后，链接节点的目的是允许快速插入和删除等操作。元素数组不提供这种灵活性，但是如果你存储一个节点数组来存储next和previous元素的索引或指针，那么你可以开始重新排列结构并删除东西并将东西插入到中间所有的常量 - 只需玩链接即可。

链表的最有效用途通常是连续或部分连续存储节点（例如：使用空闲列表）并将它们链接在一起以允许快速插入和删除。您可以将节点存储在一个大数组中，如vector，然后链接起来并通过索引取消链接。链表的另一个有趣特性是，只需更改几个指针，即可快速将元素从一个列表的中间转移到另一个列表。

它们还有一个属性，当它们分配时，它们非常有效地连续存储，因为每个节点都具有相同的大小。例如，如果它们都使用自己的类似数据的容器，那么有效地表示一堆可变大小的桶可能会很棘手，因为每个桶都想分配不同数量的内存。但是，如果它们只是存储指向列表节点的索引/指针，则它们可以轻松地将所有节点存储在一个巨型阵列中以用于所有存储桶。

也就是说，在C ++中，链接列表经常被滥用。尽管它们具有算法优势，但如果没有以提供空间局部性的方式分配节点，那么其中许多实际上并没有转化为优越的性能。否则，您可能会导致缓存未命中，并且可能会出现访问每个节点的页面错误。

尽管如此，小心使用节点在内存中的位置，它们可能非常有用。以下是一个示例用法：

在这种情况下，我们可能会进行粒子模拟，其中每个粒子都在每个帧周围移动并进行碰撞检测，我们将屏幕划分为网格单元格。这允许我们避免二次复杂度碰撞检测，因为粒子仅需要检查与同一细胞中的其他粒子的碰撞。真实版本可能存储100x100网格单元（10,000个网格单元）。

但是，如果我们为所有10,000个网格单元使用基于数组的数据结构（如std::vector），那么这将在内存中具有爆炸性。最重要的是，将每个粒子从一个细胞转移到另一个细胞将是昂贵的线性时间操作。通过使用这里的链接列表（以及只使用整数到链接的数组中），我们可以在这里和那里更改一些索引（指针），以便在移动时将粒子从一个单元格传输到另一个单元格，同时记忆使用非常便宜（10,000个网格单元意味着10,000个32位整数，转换为大约39千字节，每个粒子4个字节的开销用于链接）。

仔细使用，链表是一个非常有用的结构。然而，它们经常被滥用，因为想要分别针对通用内存分配器分配每个单独节点的简单实现往往会导致高速缓存未命中，因为节点将在内存中非常碎片化。链接列表的用处往往是最近遗忘的一个细节，特别是在C ++中，因为除非与自定义分配器一起使用，否则std::list实现就是在那个天真的缓存未命中 - 类别中。但是，它们在操作系统中使用的方式往往非常有效，在不失去参考局部性的情况下获得上述算法优势。

Answer 2

当你开始时不知道列表中有多少元素，或者你可以随着时间的推移添加或删除元素时，链接列表算法是非常好的。如果要在列表末尾以外的任何位置添加或删除元素，链接列表尤其强大。链接列表在Unix中很常见。可能最好的研究地点是Wikipedia，它讨论了优点，缺点和其他细节。但主要的教训是链表对于动态数据结构非常有用，而当事物是静态时，数组往往更好。

如果您将网络接口视为“网卡”，网络接口可能会感觉非常静态，但它们会用于许多其他事情，例如VPN连接，并且可能会经常更改。

Answer 3

有多种方法可以存储数据。在c ++中，第一个选择通常是std::vector，但有std::list和其他容器 - 选择将取决于几个因素，例如你想插入/删除东西的频率和位置（向量非常适合删除/添加结束，但在中间插入是坏的 - 链接列表在中间插入所需的少得多，但迭代过程不太好。

但是，这个函数的API是经典的C（而不是C ++），所以我们必须有一个“可变长度的容器”，当然，我们可以在C中实现类似于std::vector的东西（一个包含多个元素的值）和指向实际元素的指针。我不确定为什么设计师在这种情况下不会这样做，但链表有很大的优势，即用一个元素扩展它几乎是零成本。如果你事先不知道会有多少，这是一个很好的好处。而我的猜测是，这些对象并没有足够多的担心性能[调用者总是可以在以后将其重新排列成更合适的形式]。

Answer 4

链表是非常完美的数据结构，用于存储大量数据，其元素数量未知。它是一种非常灵活的数据结构，可在运行时扩展和收缩。它还减少了额外的内存分配或浪费，因为它们使用动态内存来存储数据。当我们完成使用数据时，它会删除数据以及内存分配。

Answer 5

我同意这里的每个人关于链表对数组的动态数据长度的好处，但我需要添加一些东西

如果ifaddrs分配的结构长度相同...没有任何使用链表重叠的优势..如果是这样我可以认为它是一个“糟糕的设计”

但如果不是（可能是这种情况..请注意“ifaddrs结构至少包含以下条目”......数组将不是可变长度结构的正确表示，考虑这个例子

struct ifaddrs
{
     struct ifaddrs   *ifa_next;         /* Pointer to next struct */
     char             *ifa_name;         /* Interface name */
     u_int             ifa_flags;        /* Interface flags */
     struct sockaddr  *ifa_addr;         /* Interface address */
     struct sockaddr  *ifa_netmask;      /* Interface netmask */
     struct sockaddr  *ifa_dstaddr;      /* P2P interface destination */
     void             *ifa_data;         /* Address specific data */
};

struct ifaddrs_ofothertype
{
     struct ifaddrs   ifaddrs;         /* embed the original structure */
     char             balhblah[256];         /* some other variable */
};

提到的函数可以返回一个混合结构列表，如（ifaddrs_ofothertype *转换为ifaddrs *）和（ifaddrs *），而不必担心每个元素的结构长度

Answer 6

如果你想学习iOS，你必须从基础学习指针和内存分配知识。虽然Objective-C是C编程语言的下一代编程语言，但在语法调用和定义方面有一点区别。在进入iOS / Mac OSX之前，您应该了解Pointers知识，MVC知识并了解iOS Frameworks的核心信息，然后您就可以成为专业的iOS开发人员。访问RayWenderLich iOS Tutiorials