c - 在 C 中插入有序列表：使用数组还是链表？

Question

尝试插入有序列表时，请考虑两种情况。

1. 使用指针数组。二进制搜索以查找插入点的位置：

   • 使用 memmove() 移动字节为新地址腾出空间

   • 使用迭代移动地址以为新地址腾出空间

2. 使用链表和线性搜索

哪个表现更好？我的猜测是，在优化代码中，1. 的两个选项的性能大致相同，但 1. 和 2. 将如何比较。似乎它们都是 O(n)。有没有更简单的方法来做到这一点？是否可以在任何类型的链表上设置二进制搜索？

非常欢迎任何其他建议。