c - 文本编辑器中的双链表与数组

Question

我使用 ncurses 启动了一个实验性代码编辑器。我使用双链表来存储/解析/打印文本。尽管我已经深入实现了，但我还没有完全确定使用双链表是否是最好的主意(而不是使用数组)。

请注意，当我指的是数组时，我指的是每行的字符数组 - 而不是单个线性数组。

以下是我权衡利弊的方法:

双向链表:

• 更快的字符和行插入
• 更快的代码折叠

数组:

• 使用更少的内存
• 解析速度更快
• 打印速度更快我使用链表正确吗？或者，它们是更好的方法吗？

注意:

数组的打印速度更快，因为只需调用一次 printw 即可打印整行。与针对每个字符调用 printw 不同。

Answer 1

将评论转移到答案中，因为没有其他人参与。

为什么不使用(双向链接)字符串列表，其中列表中的每个项目都是一行，这样您就可以像数组一样每行调用一次 printw() ？您还可以显着降低存储需求；在 64 位机器上，单个字符的双向链表可能每个字符使用 24 个字节，这是相当高的开销。

I actually just started doing that. It does seem like a pretty decent compromise (I have a hunch that it's what nano uses). I'm probably going to delete this question, because I think that's my solution I'll be working with. Also, is it a bad idea to use realloc() at every insertion/removal?

我可能会按照以下方式设计列表节点:

struct Line
{
    struct Line *next;
    struct Line *prev;
    char        *line;
    size_t       line_len;
    size_t       line_max;
};

其中 line_len 记录当前行长度，line_max 记录分配的空间。

当角色被删除时，我不会调用realloc()；除非实际大小和最大大小之间存在相当大的(256 字节？)差异，否则我可能不会这样做。

对于插入，我只会在不再有空间时重新分配(当 line_len == line_max 时，但要注意相差一)，并且我会以至少 16 的增量进行分配字符(因为这可能是 malloc() 等实际分配的最小数量，而且当用户插入一个字符时，他们通常会插入几个字符)。因此，您希望避免对内存分配进行每个字符的更改(调用 realloc())，而不必担心在必要时重新分配。