c - 向量和链表 ADT 的区别

Question

有人可以向我解释交流编程语言上下文中向量和链表 ADT 之间的区别吗？

谢谢。

Answer 1

好吧，在 C 中，没有像 C++ 标准库中那样直接可供您使用的“向量”和“列表”数据类型。但就“抽象数据类型”而言，通常认为向量表示连续存储，而链表则认为由链接在一起的单个单元格表示。向量提供快速的恒定时间随机访问读写操作，但插入和删除向量元素需要线性时间。列表具有线性查找性能以查找要读取和写入的元素，但给定元素位置，具有恒定的时间插入和删除。您还可以在恒定时间内将项目添加到列表的开头和结尾（如果 ADT 实现缓存了列表中最后一个元素的位置）。

Answer 2

向量通常被实现为作为数组的连续内存块。而列表可以分布在内存中，因为每个元素都包含指向一个或多个其他元素的指针（可以是双重链接的）。这为向量提供了访问速度优势，但列出了插入/删除优势。

Answer 3

基本上，向量驻留在连续的内存中。链表包含指向前一个和下一个结构的指针。Vector对于随机访问更快，链表更适合增长。

http://www.codeguru.com/forum/archive/index.php/t-309352.html

Answer 4

vector 是一个动态数组。里面的元素在内存中是相邻的。链表内的元素不相邻。