链接列表示例 - 为什么使用它们？
Linked Lists example - Why are they used?
我正在查看有关如何获取 Unix 接口信息的代码块/iOS/MacOSX（IP 地址、接口名称等），以及想了解更多为什么使用 linked 列表。我不是全职程序员，但我可以编码并且一直在努力学习。我确实了解基本的 C/C++ 但从未有过经验或不得不使用 linked 列表。
我正在尝试学习 OS X 和 iOS 开发，并试图获取网络接口信息并遇到了这个：
https://developer.apple.com/library/mac/documentation/Darwin/Reference/ManPages/man3/getifaddrs.3.html
如果我理解正确的话，似乎 linked 列表用于 link 每个接口的一堆结构。为什么在这种情况下使用 linked 列表？为什么不只是创建结构并将其存储在数组中？
谢谢
当您在开始时不知道列表中将有多少元素，或者您可能会随着时间的推移添加或删除元素时，链表算法非常好用。如果您想在列表末尾以外的任何地方添加或删除元素，链表将特别强大。链表在 Unix 中很常见。可能最好的研究地点是 Wikipedia，它讨论了优点、缺点和其他细节。但主要的教训是，链表非常适合动态数据结构，而数组在静态时往往更好。
如果您将网络接口视为 "network cards,"，它们可能会感觉非常静态，但它们用于许多其他用途，例如 VPN 连接，并且可以经常更改。
存储数据的方式多种多样。在 c++ 中，首选通常是 std::vector，但也有 std::list 和其他容器 - 选择将取决于几个因素，例如您想要 insert/delete 的频率和位置（向量对于最后的 deleting/adding 非常有用，但插入中间是不好的——链表插入中间的时间要少得多，但迭代起来就不那么好了）。
然而，这个函数的 API 是经典的 C（而不是 C++），所以我们必须有一个 "variable length container"，当然，我们可以用 C 实现类似于std::vector（一个包含元素数量的值和指向实际元素的指针）。我不确定为什么设计者在这种情况下不这样做，但是链表具有很大的优势，即用更多元素扩展它的成本几乎为零。如果您事先不知道会有多少，这是一个很好的好处。我的猜测是，这些对象中没有足够多的担心性能 [调用者以后总是可以将它重新排列成更合适的形式]。
链表是非常完美的数据结构，可以存储大量未知元素的数据。它是一种非常灵活的数据结构，可以在 运行 时间内扩展和收缩。它还减少了额外的内存分配或浪费，因为它们使用动态内存来存储数据。当我们完成使用数据时，它会删除数据以及内存分配。
如果你想学习iOS你必须从最基础的学习指针和内存分配知识。 Objective-C虽然是C编程语言的下一代编程语言，但是在语法上还是有一些区别，特别是在方法调用和定义上。在进入 iOS/Mac OSX 之前，您应该了解 Pointers 知识、MVC 知识并了解 iOS Frameworks 的核心信息，然后您才能成为专业的 iOS Developer。
对于那次访问 RayWenderLich iOS Tutiorials
我同意这里的每个人关于链表在动态数据长度方面优于数组的好处，但我需要补充一些东西
如果 ifaddrs 分配的结构长度相同......使用链表优于数组没有任何优势..如果是这样我可以将其视为 "bad design"
但如果不是（并且可能是这种情况..请注意“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 */
};
提到的函数可以 return 混合结构列表，如 (ifaddrs_ofothertype* 转换为 ifaddrs*) 和 (ifaddrs*)，而不用担心每个元素的结构长度
[...] and wanted to understand more of why linked lists are used. I'm not a full-time programmer, but I can code and always trying to learn. I do understand basic C/C++ but never had experience or had to use linked lists.
链表其实是一种极其简单的数据结构。它们有几个变体，但总体概念只是分配节点并 link 通过索引或指针将它们组合在一起，如下所示：
Why is a linked list used in this situation?
链表有一些有趣的属性，其中一个在上图中已经注明，例如恒定时间删除和插入 from/to 中间。
How come the structs aren't just created and stored in an array?
他们实际上可以。在上图中，节点可以直接存储在数组中。然后 linking 节点的目的是允许快速插入和删除之类的事情。元素数组不提供这种灵活性，但是如果您存储一个节点数组，这些节点存储指向 next 和可能的 previous 元素的索引或指针，那么您可以开始重新排列结构并删除内容和只需玩 links.
就可以在恒定时间内将东西插入中间
linked 列表最有效的使用方式通常是连续或部分连续地存储节点（例如：使用空闲列表）并且 link 将它们放在一起以允许快速插入和删除。您可以将节点存储在一个大数组中，例如 vector，然后 link 并通过索引取消 link 它们。 linked 列表的另一个有趣的 属性 是，您只需更改几个指针即可将元素从一个列表的中间快速转移到另一个列表。
它们还有一个 属性，这使得它们在注意分配时非常有效地连续存储，因为每个节点的大小都相同。例如，如果它们都使用自己的类似数组的容器，那么有效地表示一堆可变大小的桶可能会很棘手，因为每个桶都想分配不同数量的内存。但是，如果他们只是将 index/pointer 存储到列表节点，他们可以轻松地将所有节点存储在一个巨大的数组中，用于所有存储桶。
也就是说，在 C++ 中，linked 列表经常被误用。尽管它们具有算法优势，但如果节点未以提供空间局部性的方式分配，那么其中很多实际上并不会转化为卓越的性能。否则，您可能会导致缓存未命中，并可能在访问每个节点时出现一些页面错误。
然而，在使用时注意节点在内存中的位置，它们会非常有用。这是一个示例用法：
在这种情况下，我们可能会有一个粒子模拟，其中每个粒子都在每个帧周围移动，并进行碰撞检测，我们将屏幕划分为网格单元。这使我们能够避免二次复杂性碰撞检测，因为粒子只需要检查与同一单元中的其他粒子的碰撞。真实版本可能存储 100x100 个网格单元（10,000 个网格单元）。
但是，如果我们对所有 10,000 个网格单元都使用像 std::vector 这样的基于数组的数据结构，那将在内存中爆炸。最重要的是，将每个粒子从一个细胞转移到另一个细胞将是一项代价高昂的线性时间操作。通过在此处使用 linked 列表（以及仅将整数用于 links 的数组的列表），我们可以在这里和那里更改一些索引（指针）以从一个粒子转移一个粒子单元格移动时移动到另一个单元格，而内存使用非常便宜（10,000 个网格单元格意味着 10,000 个 32 位整数，转换为大约 39 KB，link 每个粒子的开销为 4 字节）。
谨慎使用，linked 列表是一种非常有用的结构。然而，它们经常被误用，因为想要针对通用内存分配器单独分配每个节点的天真实现往往会导致大量缓存未命中，因为节点在内存中非常分散。 linked 列表的有用之处往往是最近被遗忘的细节，尤其是在 C++ 中，因为 std::list 实现除非与自定义分配器一起使用，否则属于那种天真的缓存未命中类别。但是，它们在操作系统中的使用方式往往非常高效，可以在不丢失参考位置的情况下获得上述这些算法优势。
我正在查看有关如何获取 Unix 接口信息的代码块/iOS/MacOSX（IP 地址、接口名称等），以及想了解更多为什么使用 linked 列表。我不是全职程序员，但我可以编码并且一直在努力学习。我确实了解基本的 C/C++ 但从未有过经验或不得不使用 linked 列表。
我正在尝试学习 OS X 和 iOS 开发，并试图获取网络接口信息并遇到了这个： https://developer.apple.com/library/mac/documentation/Darwin/Reference/ManPages/man3/getifaddrs.3.html
如果我理解正确的话，似乎 linked 列表用于 link 每个接口的一堆结构。为什么在这种情况下使用 linked 列表？为什么不只是创建结构并将其存储在数组中？
谢谢
当您在开始时不知道列表中将有多少元素，或者您可能会随着时间的推移添加或删除元素时，链表算法非常好用。如果您想在列表末尾以外的任何地方添加或删除元素，链表将特别强大。链表在 Unix 中很常见。可能最好的研究地点是 Wikipedia，它讨论了优点、缺点和其他细节。但主要的教训是，链表非常适合动态数据结构，而数组在静态时往往更好。
如果您将网络接口视为 "network cards,"，它们可能会感觉非常静态，但它们用于许多其他用途，例如 VPN 连接，并且可以经常更改。
存储数据的方式多种多样。在 c++ 中，首选通常是 std::vector，但也有 std::list 和其他容器 - 选择将取决于几个因素，例如您想要 insert/delete 的频率和位置（向量对于最后的 deleting/adding 非常有用，但插入中间是不好的——链表插入中间的时间要少得多，但迭代起来就不那么好了）。
然而，这个函数的 API 是经典的 C（而不是 C++），所以我们必须有一个 "variable length container"，当然，我们可以用 C 实现类似于std::vector（一个包含元素数量的值和指向实际元素的指针）。我不确定为什么设计者在这种情况下不这样做，但是链表具有很大的优势，即用更多元素扩展它的成本几乎为零。如果您事先不知道会有多少，这是一个很好的好处。我的猜测是，这些对象中没有足够多的担心性能 [调用者以后总是可以将它重新排列成更合适的形式]。
链表是非常完美的数据结构，可以存储大量未知元素的数据。它是一种非常灵活的数据结构，可以在 运行 时间内扩展和收缩。它还减少了额外的内存分配或浪费，因为它们使用动态内存来存储数据。当我们完成使用数据时，它会删除数据以及内存分配。
如果你想学习iOS你必须从最基础的学习指针和内存分配知识。 Objective-C虽然是C编程语言的下一代编程语言，但是在语法上还是有一些区别，特别是在方法调用和定义上。在进入 iOS/Mac OSX 之前，您应该了解 Pointers 知识、MVC 知识并了解 iOS Frameworks 的核心信息，然后您才能成为专业的 iOS Developer。 对于那次访问 RayWenderLich iOS Tutiorials
我同意这里的每个人关于链表在动态数据长度方面优于数组的好处，但我需要补充一些东西
如果 ifaddrs 分配的结构长度相同......使用链表优于数组没有任何优势..如果是这样我可以将其视为 "bad design"
但如果不是（并且可能是这种情况..请注意“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 */
};
提到的函数可以 return 混合结构列表，如 (ifaddrs_ofothertype* 转换为 ifaddrs*) 和 (ifaddrs*)，而不用担心每个元素的结构长度
[...] and wanted to understand more of why linked lists are used. I'm not a full-time programmer, but I can code and always trying to learn. I do understand basic C/C++ but never had experience or had to use linked lists.
链表其实是一种极其简单的数据结构。它们有几个变体，但总体概念只是分配节点并 link 通过索引或指针将它们组合在一起，如下所示：
Why is a linked list used in this situation?
链表有一些有趣的属性，其中一个在上图中已经注明，例如恒定时间删除和插入 from/to 中间。
How come the structs aren't just created and stored in an array?
他们实际上可以。在上图中，节点可以直接存储在数组中。然后 linking 节点的目的是允许快速插入和删除之类的事情。元素数组不提供这种灵活性，但是如果您存储一个节点数组，这些节点存储指向 next 和可能的 previous 元素的索引或指针，那么您可以开始重新排列结构并删除内容和只需玩 links.
linked 列表最有效的使用方式通常是连续或部分连续地存储节点（例如：使用空闲列表）并且 link 将它们放在一起以允许快速插入和删除。您可以将节点存储在一个大数组中，例如 vector，然后 link 并通过索引取消 link 它们。 linked 列表的另一个有趣的 属性 是，您只需更改几个指针即可将元素从一个列表的中间快速转移到另一个列表。
它们还有一个 属性，这使得它们在注意分配时非常有效地连续存储，因为每个节点的大小都相同。例如，如果它们都使用自己的类似数组的容器，那么有效地表示一堆可变大小的桶可能会很棘手，因为每个桶都想分配不同数量的内存。但是，如果他们只是将 index/pointer 存储到列表节点，他们可以轻松地将所有节点存储在一个巨大的数组中，用于所有存储桶。
也就是说，在 C++ 中，linked 列表经常被误用。尽管它们具有算法优势，但如果节点未以提供空间局部性的方式分配，那么其中很多实际上并不会转化为卓越的性能。否则，您可能会导致缓存未命中，并可能在访问每个节点时出现一些页面错误。
然而，在使用时注意节点在内存中的位置，它们会非常有用。这是一个示例用法：
在这种情况下，我们可能会有一个粒子模拟，其中每个粒子都在每个帧周围移动，并进行碰撞检测，我们将屏幕划分为网格单元。这使我们能够避免二次复杂性碰撞检测，因为粒子只需要检查与同一单元中的其他粒子的碰撞。真实版本可能存储 100x100 个网格单元（10,000 个网格单元）。
但是，如果我们对所有 10,000 个网格单元都使用像 std::vector 这样的基于数组的数据结构，那将在内存中爆炸。最重要的是，将每个粒子从一个细胞转移到另一个细胞将是一项代价高昂的线性时间操作。通过在此处使用 linked 列表（以及仅将整数用于 links 的数组的列表），我们可以在这里和那里更改一些索引（指针）以从一个粒子转移一个粒子单元格移动时移动到另一个单元格，而内存使用非常便宜（10,000 个网格单元格意味着 10,000 个 32 位整数，转换为大约 39 KB，link 每个粒子的开销为 4 字节）。
谨慎使用，linked 列表是一种非常有用的结构。然而，它们经常被误用，因为想要针对通用内存分配器单独分配每个节点的天真实现往往会导致大量缓存未命中，因为节点在内存中非常分散。 linked 列表的有用之处往往是最近被遗忘的细节，尤其是在 C++ 中，因为 std::list 实现除非与自定义分配器一起使用，否则属于那种天真的缓存未命中类别。但是，它们在操作系统中的使用方式往往非常高效，可以在不丢失参考位置的情况下获得上述这些算法优势。