Hey there! Let’s break down your questions step by step—this is such a common (and critical) topic when working with data structures, so I’m glad you’re digging into the details.

First up, let’s clear up when to pick one over the other:

什么时候选链表而非数组？ #

• 频繁在任意位置增删元素: Say you need to insert a new booking between two existing ones, or delete a cancellation from the middle of your list. With an array, you’d have to shift every element after that position to make space (or fill the gap)—that’s an O(n) operation, which gets slow as your list grows. Linked lists? You just tweak a couple pointers to redirect the chain, and you’re done in O(1) time (once you’ve found the right spot).
• 数据规模不确定/动态变化: If you don’t know how many bookings you’ll get (think busy weekends vs. slow weekdays), linked lists let you add nodes on demand. Arrays force you to either allocate a huge buffer upfront (wasting memory) or manually reallocate and copy all your data when you run out of space—total hassle.
• 实现特定数据结构: Linked lists are the go-to for queues, stacks (no fixed capacity limits), hash table collision resolution, or any structure where you need to rearrange elements often without shifting chunks of data around.

什么时候选数组而非链表？ #

• 需要随机访问: If you need to jump straight to the 10th booking in your list, arrays let you do that in O(1) time with an index. With linked lists? You have to start at the head and traverse 9 nodes to get there—O(n) time, which is brutal if you’re doing this a lot.
• 内存效率&缓存性能: Arrays use contiguous memory, which CPUs love (cache hits are way more common, so your code runs faster). Linked lists have extra overhead from the next pointer in every node, and their scattered memory layout leads to more cache misses.
• 数据规模固定: If you know exactly how many elements you’ll have (like a fixed number of tables in a small café), arrays are simpler to code and faster. No need to mess with pointer management or individual node memory allocations.

First, let’s recap your professor’s code (formatted for readability):

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

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

typedef TNodeBooking* PNodeBooking;

This is a textbook use case for linked lists, and here’s why it makes sense for a booking system:

1. 预订数量波动大: A restaurant’s bookings can swing wildly—busy weekends, slow weekdays, last-minute cancellations or additions. A linked list lets you add/remove bookings without stressing about preallocating enough space (something you’d struggle with if you used a fixed-size array).
2. 频繁修改是常态: Customers cancel bookings, change their party size, or you might need to insert a VIP booking ahead of others. With an array, each of these changes would require shifting elements around; with a linked list, you just adjust pointers to reorder or remove nodes in seconds.
3. 未来扩展更灵活: If the system needs to grow—like adding sorting by time, grouping by restaurant, or linking bookings to a customer’s history—the linked list structure makes these extensions way easier than modifying a rigid array setup.

Stack Overflow has tons of discussions on this exact topic, and the core takeaways are pretty consistent:

• 核心操作决定选择: There’s no "best" structure—you pick based on what you need to do most. If random access and raw speed are top priorities, go array. If dynamic size and frequent edits are key, linked list is the way to go.
• 内存与灵活性的权衡: Many devs point out that linked lists have pointer overhead (each node uses extra memory for the next pointer), but this is a worthwhile cost if you need the dynamic behavior. For small data types, this overhead is more noticeable, but for structs like TBooking, it’s negligible compared to the benefits.
• 实现复杂度对比: Arrays are simpler to code and less error-prone (no null pointer bugs or memory leaks to worry about). Linked lists require careful memory management (especially in C), but offer far more flexibility for changing datasets.
• C语言中的实际考量: In C specifically, dynamic arrays require manual reallocation (using realloc), which can be messy and error-prone. Linked lists let you allocate/deallocate nodes one at a time, which is cleaner for variable-size datasets like restaurant bookings.

内容的提问来源于stack exchange，提问作者St3ve R0nix