向量和链接列表之间的区别ADT

Question

有人可以向我解释在c编程语言上下文中向量和链接列表ADT之间的区别。

谢谢。

Answer 1

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

Answer 2

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

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

Answer 3

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

Answer 4

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