数组或链表对于经常随机访问？ [英] Arrays or linked-list for frequently random access?

问题描述

我使用列表和数组，很多时候，我想知道什么是速度更快，数组或列表？

I'm using lists and arrays very often, I am wondering what is faster, array or list?

比方说，我们有一个整数数组，链表，既持有相同的价值观。

Let's say we have array of integers and linked-list, both hold same values.

int array_data[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

typedef struct node_data{
    int data;
    struct node_data * next;
} list_data;

                  ____    ____    ____    ____    ____    ____    ____    ____    ____    ____
list_data *d = -> | 1| -> | 2| -> | 3| -> | 4| -> | 5| -> | 6| -> | 7| -> | 8| -> | 9| -> |10| -> NULL

如果我想获得指数6，我将使用 array_data [6] array_data的价值，并获得7价值，但如果我想从相同的数据列出？我应该从开始去和计数跳，直到我达到要求指标 GET_DATA（四，六）？或者有更好的方式来做到这一点？

If I want to get value of array_data on index 6, I'll use array_data[6] and get value of 7. But what if I want same data from list? Should I go from start and count hops till I reach asked index get_data(d,6)? Or there is better way to do this?

int get_data(list_data *l, int index){
    int i = 0;
    while(l != NULL){
        if(index == i){
            return l -> data;
        }
        i++;
        l = l -> next;
    }
    return 0;
}

如何使用指针数组列表元素？将在此情况下，最好的解决办法我有更多的则10万条记录，甚至更节省，每个记录包含一个以上的数据类型。我大多需要插入到结束，非常频繁访问的元素。

How about using array of pointers to list elements? Will be this best solution in case I have more then 100,000 records or even more to save, and each record contains more then one data type. I'll mostly need insertion to the end, and very frequently access to elements.

谢谢！

推荐答案

您是否正确要考虑每一次的问题;决定何时是否实施一个数组，链表（或其它）结构

You are correct to consider the question each time; when deciding whether to implement an array, linked-list (or other) structure.

阵列

 
• +快速随机访问。

 
• +动态分配数组可以使用`realloc（）的'调整大小。

 
• +排序利用'的qsort（）`。

 
• +对于有序阵列，特定的记录，可以使用`bsearch（）位于`

 结果
 
• - 必须占用一个连续的内存块
。
 
• - 对于长寿命应用中，数组的频繁肿大最终导致一个支离破碎的内存空间，和realloc（）``的甚至最终失败
。
 
• - 插入和删除元素是昂贵的。插入元素（在排序后的数组）要求超出插入点的数组的所有元素被移动。元素的类似的运动删除元素时是必需的。
  

• + Fast random access.
• + Dynamically allocated arrays can be re-sized using `realloc()`.
• + Sorted using `qsort()`.
• + For sorted arrays, a specific record can be located using `bsearch()`


• - Must occupy a contiguous block of memory.
• - For a long-lived applications, frequent enlargement of the the array can eventually lead to a fragmented memory space, and perhaps even eventual failure of `realloc()`.
• - Inserting and deleting elements is expensive. Inserting an element (in a sorted array) requires all elements of the array beyond the insertion point to be moved. A similar movement of elements is required when deleting an element.

链表
 

   
• +不需要一个连续的内存块。

   
• +更有效的不是一个数组重新大小动态。 ，当涉及到零碎的内存使用
胜于数组
   
• +顺序存取是好的，但恐怕还没有那么快作为数组（由于CPU高速缓存未命中，等等）。

   

   
• - 随机访问是不是真的有可能
。
   
• - 额外的内存开销节点指针（priorNode，nextNode）

 

有其他结构，即使使用链表结合阵列，诸如哈希表，二进制树，正树，随机访问列表等，每带有各种特性来考虑

There are other structures that even combine arrays with linked list, such as hash tables, binary trees, n-trees, random-access-list, etc., each comes with various characteristics to consider.

这篇关于数组或链表对于经常随机访问？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！