常用数据结构的应用场景小结

1、单向链接

单向链表适用于只从一端单向访问的场合,这种场合一般来说:

(1)、删除时,只适合删除第一个元素;

(2)、添加时,只直接添加到最后一个元素的后面或者添加到第一个元素的前面;

(3)、属于单向迭代器,只能从一个方向走到头(只支持前进或后退,取决于实现),查找效率极差。不适合大量查询的场合。

这种典型的应用场合是各类缓冲池和栈的实现。

2、双向链表

双向链表相比单向链表,拥有前向和后向两个指针地址,所以适合以下场合:

(1)、删除时,可以删除任意元素,而只需要极小的开销;

(2)、添加时,当知道它的前一个或后一个位置的元素时,只需要极小的开销。

(3)、属于双向迭代器,可以从头走到尾或从尾走到头,但同样查找时需要遍历,效率与单向链表无改善,不适合大量查询的场合。

这种典型的应用场景是各种不需要排序的数据列表管理。

3、数组(含Delphi中动态数组)、列表(Delphi/C++ Builder中的TList)向量(C++中std::vector)

这种数据结构使用一段连续的空间来存贮元素,所以可以直接通过索引来获取到某个元素,而且可以通过对元素的内容进行排序,然后使用二分法查找,从而提供查找效率。其适合的场合主要是:

(1)、不会频繁增删元素的场合,因为增删元素都牵涉到元素空间的重新分配,频繁的内存分配操作会大幅降低操作效率。但添加操作时,可以通过预分配足够的空间来优化添加时的效率。

(2)、属于随机迭代器,可以随机访问任意元素。对于已排序的元素查找起来效率较高。

4、二叉树(含红黑树、平衡二叉树等)

这个数据结构类似于双向链表,任意插入元素时都会自动排序,红黑树和平衡二叉树都使二叉树尽量平衡,从而使查询时和二分法类似。它适合的场合主要是:

(1)、需要时刻保证列表元素的有序排列;

(2)、需要频繁的增删和查询操作;

(3)、属于双向迭代器,不能随机访问任意元素;

5、哈希桶

这个数据结构使用数组和链表来管理元素,在好的桶尺寸和哈希算法支持下,理想上可以达到接近数组的随机访问效率。其适合的场合主要是:

(1)、不需要保证元素的顺序(因为它是按哈希值决定插入到那个桶里,与原始数据内容无关);

(2)、需要频繁的增删和查询操作;

(3)、属于单向或双向迭代器(取决于具体实现),不能随机访问任意元素。

分享到: