Связанные списки и массивы (реализовано?)

Question

Массив - это структура данных, отличная от связанного списка, верно? Или я могу реализовать связанный список, используя массив? Я немного запутался в этой теме, был бы признателен, если бы вы могли мне помочь. Спасибо!

Answer 1

Массив - это структура данных, отличная от связанного списка, верно?

Да, массив и связанный список - это разные структуры данных.

Связанный список :
Связанный список - это линейный набор элементов данных, порядок которых не определяется их физическим размещением в памяти. Вместо этого каждый элемент указывает на следующий. Это структура данных, состоящая из набора узлов, которые вместе представляют последовательность.

Предположим, что у вас есть структура узла, определенная следующим образом (с использованием конструкции языка C в примере):

struct Node 
{ 
    int data; 
    struct Node *next; 
}; 

Каждый узел связанного списка имеет целое число и указатель на свой следующий узел, который используется для доступа к следующему члену списка (последний указатель на следующий узел установлен на NULL). Просмотр в памяти будет выглядеть примерно так:

---------    ---------    ---------    ---------
| 1 |  -|--->| 2 |  -|--->| 3 |  -|--->| 4 |  -|--->NULL
---------    ---------    ---------    ---------

Он обеспечивает гибкость с точки зрения вставки / удаления элементов в списке в любом месте, вам просто нужно установить / сбросить следующие указатели узлов. Недостатком является то, что для доступа к его узлам требуется последовательный обход .

Массив
Структура данных массива или просто массив - это структура данных, состоящая из набора элементов (значений или переменных), каждый из которых идентифицируется по меньшей мере одним индексом или ключом массива.

Предположим, что у вас есть массив из 5 целых чисел (с использованием конструкции языка C в примере):

int arr[5] = {0}; // array of 5 integer initialized with 0

Просмотр в памяти будет выглядеть примерно так:

  index   0   1   2   3   4
    arr ---------------------
        | 0 | 0 | 0 | 0 | 0 |
        ---------------------

Преимущество в том, что вы можете обращаться к любому элементу массива напрямую через его индекс . Например, если вы хотите получить доступ к элементу 3 ^rd , вы можете просто сделать a[2]. Недостатком является то, что вставка / удаление элементов в массиве в любом месте, кроме конца массива, не является прямой. Для этого вам, возможно, придется перемешать несколько элементов массива.

Или я могу реализовать связанный список, используя массив?

Да, вы можете. Но вы не получите никаких преимуществ от этого. Скорее это внесет ненужную сложность в ваш код. Отметьте это .

Answer 2

Правильно. Вы можете реализовать массив, используя связанный список, но он не будет работать так же эффективно, как массив, как обычный массив в стиле C. Вы можете технически реализовать связанный список, используя массив, но он по крайней мере унаследует относительно негибкий размер массива. Скорее всего, это не лучшая реализация для всего, что вы пытаетесь достичь.

Как правило, связанный список состоит из узлов, которые имеют указатели на другие узлы в списке, большинство или все из которых будут находиться в анонимно распределенных блоках памяти. Это дает вам гораздо больше гибкости, если вы хотите переставить элементы в списке, включая вставку элементов в середину существующего списка.

Массив, с другой стороны, имеет заданное пространство. Если язык не сделал что-то, чтобы обойти его ограничения, его нелегко вырастить, хотя, если он динамически выделяется, вы можете перераспределить его, чтобы он стал больше - но это может стоить того, чтобы скопировать все вещь в другую область памяти, в которой есть место для всего этого в непрерывном сегменте памяти.

Я бы поспорил, что этот вопрос уже задавался ранее при переполнении стека, и кто-то дал на него лучший ответ, чем я, но нашел его во всех результатах поиска "Связанные списки против массивов". "может быть сложно. Тем не менее, я предполагаю, что вы находитесь в той точке, где многие из этих постов также были бы образовательными.