Monday, March 30, 2009

Algorithms: What are the differences between array and linked list?

Итак, в чем же разница между массивом и односвязным списком?

Space:

1. В случае массивов, для хранения 10 элементов нам потребуется 10 * sizeof(element) байт памяти.
2. А в случае со односвязным списком, нам понадобится 10 * (sizeof(element) + sizeof(pointer)) места.

Следовательно, нам понадобится больше места/памяти в случае списка (по сравнению с массивом).

Time:

Т. к. массив предоставляет возможнось доступа к элементу по индексу, то в случае массива время доступа к произвольному элементу будет O(1), в то время как поиск элемента в списке потребует O(n) времени.

НО:

1. Некоторые структуры данных удобней представлять в виде именно связных списков, а не массивов.
2. Удаление и добавление новых элементов проще производить в списках, чем в массивах (массивы не расширяемы).
3. В случае массивов нет фрагментации памяти (т.к. элементы массива следуют друг за другом в памяти), как это может быть со связным списком.

No comments :

Post a Comment