c - 我们什么时候应该使用链表而不是数组，反之亦然？

Question

我从一位教授的代码中得到了这些结构声明，我实际上想知道为什么我们应该使用链表而不是数组。我不知道这是否是一个愚蠢的问题，我只是好奇 SO 社区对此有何看法。

typedef struct Booking
{
  char restaurant[32];
  char customer[32];
  int  seats;
  int  period; // DAY o NIGHT
} TBooking;

typedef struct NodeBooking
{
  TBooking            booking;
  struct NodeBooking* next;
} TNodeBooking;

typedef TNodeBooking* PNodeBooking;

typedef struct BookingQueue
{
  PNodeBooking first;
  PNodeBooking last;
} TBookingQueue;

typedef struct Restaurant
{
  char              restaurant[32];
  int               n_booking_lunch;
  int               n_booking_dinner;
  TBookingsQueue bookings;
} TRestaurant;

typedef struct NodeRestaurant
{
  TRestaurant            restaurant;
  struct NodeRestaurant* next;
} TNodeRestaurant;

 typedef TNodeRestaurant* PNodeRestaurant;

Answer 1

如果您不经常修改数组(即删除和插入)，并且需要索引访问，则数组通常比较好。再说一次，正如评论中提到的，由于缓存局部性(并且没有指针间接)，由于它们在内存中的顺序布局，数组在读取它们时会表现得更好，而链表在内存中是碎片化的，并且每个节点都有一个指针间接。考虑到这一点，每种数据结构在复杂性和用例方面都有其优点和缺点。

至于数组的一些缺点，我们假设您有以下数组:

struct user_s *user_list[] = { &user1, &user2, &user3, &user4 };

想象一下这个列表包含更多的元素。

1. 如果您想删除 &user2 会发生什么？您必须将删除的元素后面的所有内容移动以填充删除的空间，这意味着在内存中最多复制 N-1 个元素。

2. 如果我们用完了数组的初始保留大小会发生什么？您必须在内存中重新分配更多空间，并将所有内容移动到新分配的内存空间(这就是重新分配的工作原理)。这也相当昂贵。

尽管如此，根据元素的类型，使用数组或链表可能更优化，并且都可以针对用例进行优化。

当您有如下所示的链接列表时，您就不会遇到其中一些问题:

struct user_s {
  char *name;

  struct user_s *next;
}

现在，当容量已满时，您可以在末尾添加新元素，而无需重新分配整个数组:

struct user_s *user_add(struct user_s *tail, struct user_s *user)
{
    assert(tail != NULL);
    assert(user != NULL);

    tail->next = user;

    return tail->next;
}

这有助于解决数组的第二个问题。您可以无限期地追加到列表尾部的末尾，而不会达到数组容量，这需要为其重新分配更多缓冲区。但这种重新分配可以通过提前缓冲内存空间来优化。

从中间删除元素的1.问题甚至更容易:

void user_remove(struct user_s *head, struct user_s *user)
{
    struct user_s *it, *prev;

    assert(head != NULL);
    assert(user != NULL);

    for (prev = head, it = head->next; it != NULL; prev = it, it = it->next) {
        if (it == user) {
            prev->next = it->next;
            free(it);
            return;
        }
    }
}

这样您就可以从列表中间删除一个元素，并将上一个和下一个元素相互绑定(bind)。

而在数组中，为了删除元素，您必须创建一个新数组，复制元素直到要删除的元素，然后将其后面的元素复制到新分配的数组中，然后返回该元素。如果您必须经常删除元素，那么这是一项非常昂贵的操作。请参阅https://ideone.com/bOSvpg

在您的示例中，结构中包含 *next 的另一个原因是，在实现涉及树等大量其他数据结构时，您几乎总是需要一个指针。