作者：sdx3418153 | 来源：互联网 | 2023-09-18 10:30
今晚在研究线性表的两种实现方法插入删除操作的效率问题，一种是利用数组实现，这种方法如果在头部插入，需要把整个链表后移一位，然后再写入数据，同样的，如果采用链式存储结构实现，那么在尾部插入删除时，需要从
今晚在研究线性表的两种实现方法插入删除操作的效率问题，一种是利用数组实现，这种方法如果在头部插入，需要把整个链表后移一位，然后再写入数据，同样的，如果采用链式存储结构实现，那么在尾部插入删除时，需要从head头指针遍历到最后一个然后在进行操作。理论上来说，如果对数组实现进行头部插入删除和链表实现尾部插入删除执行相同规模，链表应当比数组快才对。
可我晚上测试的时候却发现结果相反，数组执行10w次只要13s，链表执行5w次就要100+s，不清楚是我的实现问题还是本就如此，希望你能告诉我具体原因。
下附部分代码和运行截图（如果有需要，我可以继续传其他的代码）。
//Linked_List
template
Error_code List::remove(int position, List_entry & x)
{
if (position<0 || position >= count)return range_out;
if (position == 0) {
x = head->entry;
Node *p=head;
head = head->next;
delete p;
count--;
return success;
}
Node *pre, *cur;
pre = set_position(position-1);
cur = pre->next;
pre->next = cur->next;
x = cur->entry;
delete cur;
count--;
return success;
}
template
Error_code List::insert(int position, const List_entry & x)
{
if (position<0 || position > count)return range_out;
if (full())return overflow;
if (position == 0) {
head = new Node(x, head);
count++;
return success;
}
Node *pre = set_position(position - 1);
Node *cur = pre->next;
pre->next = new Node(x,cur);
count++;
return success;
}
#include"Linked_List.cpp"
#include
#include
using namespace std;
void main() {
List test;
clock_t start_time = clock();
{
for (int i = 0; i <100000; i++) { //初始化
test.insert(i, i);
}
}
clock_t end_time = clock();
cout << "Linked_List Tail Insert Running time is: " << static_cast(end_time - start_time) / CLOCKS_PER_SEC * 1000 << "ms" << endl;//输出运行时间
start_time = clock();
{
//被测试代码
for (int i = 99999; i >=0; i--) {
int x;
test.remove(i, x);
}
}
end_time = clock();
cout << "Linked_List Tail Delete Running time is: " << static_cast(end_time - start_time) / CLOCKS_PER_SEC * 1000 << "ms" << endl;//输出运行时间
}
//Squence_List
template
Error_code List::remove(int position, List_entry & x)
{
if (empty())return underflow;
if (position<0 || position>=count)return range_out;
for (int i =position; i < count-1; i++) {
entries[i] = entries[i + 1];
}
count--;
return success;
}
template
Error_code List::insert(int position, const List_entry & x)
{
if (full())return overflow;
if (position<0 || position>count) return range_out;
for (int i = count; i > position; i--) {
entries[i] = entries[i - 1];
}
entries[position] = x;
count++;
return success;
}
#include"Sequence_Link.cpp"
#include
#include
#include
using namespace std;
void main() {
List test;
clock_t start_time = clock();
{
//被测试代码
for (int i = 0; i < 100000; i++) {
test.insert(0, 99999);
}
}
clock_t end_time = clock();
cout << "Sequence_List Tail Insert Running time is: " << static_cast(end_time - start_time) / CLOCKS_PER_SEC * 1000 << "ms" << endl;//输出运行时间
start_time = clock();
{
//被测试代码
for (int i = 99999; i >=0; i--) {
int x;
test.remove(0, x);
}
}
end_time = clock();
cout << "Sequence_List Tail Delete Running time is: " << static_cast(end_time - start_time) / CLOCKS_PER_SEC * 1000 << "ms" << endl;//输出运行时间
}
9 个解决方案
“如果采用链式存储结构实现，那么在尾部插入删除时， 需要从head头指针遍历到最后一个然后在进行操作”.....
不会储存一个尾指针么, std::list::back的效率不是低的吓死人.
链表不是随机储存的容器，支持随机位置插入/删除反而画蛇添足.
而lz问题的答案....没仔细看代码，目测是CPU的缓存引起的
数组查询快，链表增删快
在不知道索引的情况下，你要查找数据，遍历是必须的。
链表同样需要遍历，而且代价更高。
你要取到中间的某个值，必须从某一个节点开始往一个方向搜索，因为链表不是连续存储，所以这个消耗是比较大的。
提高C++程序运行效率的10个简单方法:http://www.jb51.net/article/54792.htm
楼主说的是数据结构的理论效率，现在 cpu 缓存的情况下，绝大多数的时候都是 vector 快，除非元素数目特别巨大，否则 list 没有优势。
"增删操作应该是链表快不是吗？"
的确，但是lz的代码比较的是“增删操作”吗，我怎么觉得是进行的遍历效率的检查，请看看std::list的删除操作的参数.
我的“画蛇添足”说法已经非常清楚了.
![扫描线三巨头 hdu1928hdu 1255 hdu 1542 [POJ 1151]](https://img.php1.cn/3c972/245b5/42f/19446f78530d3747.jpeg)
京公网安备 11010802041100号