Рубрики

Подход программиста к просмотру массива и связанного списка

В общем случае массив считается структурой данных, размер которой фиксирован во время компиляции, а память массива выделяется либо из раздела данных (например, глобального массива), либо из раздела стека (например, локального массива).
Аналогично, связанный список считается структурой данных, для которой размер не является фиксированным, а память выделяется из секции Heap (например, с помощью malloc () и т. Д.) По мере необходимости. В этом смысле массив воспринимается как статическая структура данных (находящаяся в разделе Data или Stack), а связанный список — как динамическая структура данных (находящаяся в разделе Heap). Представление в памяти массива и связанного списка может быть визуализировано следующим образом:

Массив из 4 элементов (целочисленный тип), которые были инициализированы с 1, 2, 3 и 4. Предположим, эти элементы размещены по адресам памяти 0x100, 0x104, 0x108 и 0x10C соответственно.

[(1)]       [(2)]      [(3)]      [(4)]
0x100       0x104      0x108      0x10C

Связанный список с 4 узлами, где каждый узел имеет целое число в качестве данных, и эти данные инициализируются с помощью 1, 2, 3 и 4. Предположим, эти узлы выделены с помощью malloc (), и для них выделено 0x200, 0x308, 0x404 и 0x20B. соответственно.

[(1), 0x308]     [(2),0x404]      [(3),0x20B]       [(4),NULL]  
  0x200            0x308            0x404              0x20B  

Любой, кто еще мало понимает массив и связанный список, может не заинтересоваться приведенным выше объяснением. Я имею в виду, что хорошо известно, что элементам массива выделяется память по порядку, то есть непрерывная память, в то время как узлы связанного списка не являются смежными в памяти. Хотя это звучит тривиально, но это самое важное различие между массивом и связанным списком. Следует отметить, что из-за этой смежной и несмежной памяти массив и связанный список различаются. На самом деле, это различие — то, что делает массив против связанного списка! В следующих разделах мы попытаемся исследовать эту идею дальше.

Поскольку элементы массива непрерывны в памяти, мы можем получить доступ к любому элементу случайным образом, используя индекс, например, intArr [3] получит прямой доступ к четвертому элементу массива. (Для новичков индексация массива начинается с 0, и поэтому четвертый элемент индексируется с 3). Кроме того, из-за непрерывной памяти для последовательных элементов в массиве нет необходимости хранить дополнительную информацию в отдельных элементах, то есть не требуются дополнительные затраты метаданных в массивах. В противоположность этому узлы связанного списка не являются смежными в памяти. Это означает, что нам нужен какой-то механизм для обхода или доступа к узлам связанного списка. Для достижения этого каждый узел хранит местоположение следующего узла, и это формирует основу связи от одного узла к следующему узлу. Поэтому он называется связанным списком. Хотя сохранение местоположения следующего узла в связанном списке является дополнительным, но это необходимо. Как правило, мы видим объявление узла связанного списка следующим образом:

struct llNode

{

  int dataInt;

  

  / * nextNode - указатель на следующий узел в связанном списке * /

  struct llNode * nextNode;    

};

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

Что если нам нужно выделить память массива из секции Heap (т.е. во время выполнения) и память связанного списка из секции Data / Stack. Во-первых, возможно ли это? Перед этим можно спросить, зачем кому-то это нужно делать? Теперь я надеюсь, что оставшаяся статья заставит вас переосмыслить идею массива и связанного списка.

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

/ * Предположим, что во время выполнения мы знаем требуемый размер для целочисленного массива (например, размер ввода от пользователя). Скажем, размер массива хранится в переменной arrSize. Выделите этот массив из кучи следующим образом * /

int * dynArr = (int *)malloc(sizeof(int)*arrSize);

Несмотря на то, что память этого массива выделена из Heap, к элементам все еще можно получить доступ через механизм индекса, например, dynArr [i]. По сути, исходя из проблемы программирования, мы объединили одно преимущество массива (т.е. произвольный доступ к элементам) и одно преимущество связанного списка (т.е. задержка выделения памяти до времени выполнения и выделение памяти из кучи). Другое преимущество наличия такого типа динамического массива состоит в том, что этот метод выделения массива из кучи во время выполнения может уменьшить размер кода (конечно, это зависит от некоторых других факторов, например, формата программы и т. Д.)

Теперь рассмотрим случай, когда нам нужно хранить данные в связанном списке (потому что число узлов в связанном списке будет равно фактическим хранимым элементам данных, т. Е. Нет дополнительного пространства, такого как массив), но нам не разрешено получать эту память из Куча снова и снова для каждого узла. Это может показаться гипотетической ситуацией для некоторых людей, но это не очень редкое требование во встроенных системах. По сути, в некоторых встроенных программах выделение памяти с помощью malloc () и т. Д. Не допускается по нескольким причинам. Одной из очевидных причин является производительность, т. Е. Выделение памяти с помощью malloc () является дорогостоящим с точки зрения сложности времени, поскольку ваша встроенная программа в большинстве случаев должна быть детерминированной. Другой причиной может быть управление памятью для конкретного модуля, т. Е. Возможно, что каждый модуль во встроенной системе управляет своей собственной памятью. Короче говоря, если нам нужно выполнить собственное управление памятью, вместо того чтобы полагаться на предоставляемые системой API-интерфейсы malloc () и free (), мы могли бы выбрать связанный список, который моделируется с использованием массива. Я надеюсь, что вы поняли, почему нам может понадобиться смоделировать связанный список с использованием массива. Теперь давайте сначала посмотрим, как это можно сделать. Предположим, тип узла в связанном списке (то есть базовый массив) объявлен следующим образом:

struct sllNode

{

  int dataInt;

  

 / * Обратите внимание, что nextIndex хранит местоположение следующего узла в

  связанный список * /

  int nextIndex; 

};

  

struct sllNode arrayLL[5];

Если мы инициализируем этот связанный список (который на самом деле является массивом), он будет выглядеть в памяти следующим образом:

[(0),-1]    [(0),-1]    [(0),-1]   [(0),-1]   [(0),-1]
0x500        0x508       0x510      0x518      0x520

Важно отметить, что все узлы связанного списка являются смежными в памяти (каждый занимает 8 байтов), а nextIndex каждого узла имеет значение -1. Это (то есть -1) сделано, чтобы обозначить, что каждый узел связанного списка является пустым на данный момент. Этот связанный список обозначается головным индексом 0.

Теперь, если этот связанный список обновляется четырьмя элементами данных 4, 3, 2 и 1 последовательно, он будет выглядеть следующим образом в памяти. Этот связанный список можно просмотреть как 0x500 -> 0x508 -> 0x510 -> 0x518.

[(1),1]       [(2),2]      [(3),3]     [(4),-2]     [(0),-1]
 0x500         0x508        0x510       0x518        0x520

Важно отметить, что nextIndex последнего узла (то есть четвертого узла) имеет значение -2. Это (то есть -2) сделано, чтобы обозначить конец связанного списка. Кроме того, головным узлом связанного списка является индекс 0. Эта концепция имитации связного списка с использованием массива выглядела бы более интересной, если бы мы удалили, скажем, второй узел из вышеуказанного связанного списка. В этом случае связанный список будет выглядеть в памяти следующим образом:

[(1),2]       [(0),-1]      [(3),3]     [(4),-2]     [(0),-1]
 0x500         0x508         0x510       0x518        0x520

Результирующий связанный список: 0x500 -> 0x510 -> 0x518. Здесь следует отметить, что даже если мы удалили второй узел из нашего связанного списка, память для этого узла все еще там, потому что базовый массив все еще там. Но nextIndex первого узла теперь указывает на третий узел (для которого индекс равен 2).

Надеемся, что приведенные выше примеры дадут некоторую идею, что для смоделированного связанного списка нам нужно написать наш собственный API, похожий на malloc () и free (), который в основном будет использоваться для вставки и удаления узла. Теперь это то, что называется собственным управлением памятью. Давайте посмотрим, как это можно сделать алгоритмическим образом.

Есть несколько способов сделать это. Если мы используем упрощенный подход к созданию связанного списка с использованием массива, мы можем использовать следующую логику. Для вставки узла просмотрите базовый массив и найдите узел, у которого nextIndex равен -1. Это означает, что этот узел пуст. Используйте этот узел как новый узел. Обновите часть данных в этом новом узле и присвойте nextIndex этого узла текущему главному узлу (то есть главному индексу) связанного списка. Наконец, сделайте индекс этого нового узла в качестве индекса заголовка связанного списка. Чтобы визуализировать это, давайте возьмем пример. Предположим, что связанный список выглядит следующим образом, где индекс индекса равен 0, т.е. связанный список равен 0x500 -> 0x508 -> 0x518 -> 0x520.

[(1),1]       [(2),3]      [(0),-1]     [(4),4]     [(5),-2]
 0x500         0x508        0x510        0x518       0x520

После вставки нового узла с данными 8 связанный список будет выглядеть следующим образом с индексом заголовка 2.

[(1),1]       [(2),3]      [(8),0]     [(4),4]     [(5),-2]
 0x500         0x508        0x510       0x518       0x520

Таким образом, узлы связанного списка будут расположены по адресам 0x510 -> 0x500 -> 0x508 -> 0x518 -> 0x520

Для удаления узла нам нужно установить nextIndex узла как -1, чтобы узел был помечен как пустой узел. Но, прежде чем сделать это, мы должны убедиться, что nextIndex предыдущего узла корректно обновляется до индекса следующего узла этого узла, который будет удален. Мы можем видеть, что мы сделали собственное управление памятью для создания связанного списка из памяти массива. Но это один из способов вставки и удаления узлов в этом связанном списке. Легко заметить, что поиск пустого узла не так эффективен с точки зрения сложности времени. По сути, мы ищем полный массив линейно, чтобы найти пустой узел.

Давайте посмотрим, сможем ли мы оптимизировать его дальше. По сути, мы можем поддерживать связанный список пустых узлов в одном массиве. В этом случае связанный список будет обозначаться двумя индексами — один индекс будет для связанного списка, который имеет действительные значения данных, то есть узлы, которые были вставлены до сих пор, и другие индексы для связанного списка пустых узлов. Таким образом, всякий раз, когда нам нужно вставить новый узел в существующий связанный список, мы можем быстро найти пустой узел. Давайте возьмем пример:

[(4),2]    [(0),3]    [(5),5]    [(0),-1]   [(0),1]   [(9),-1]
 0x500      0x508      0x510      0x518      0x520      0x528

Приведенный выше связанный список, представленный с использованием двух индексов (0 и 5), имеет два связанных списка: один для фактических значений, а другой для пустых узлов. Связанный список с фактическими значениями имеет узлы по адресу 0x500 -> 0x510 -> 0x528, в то время как связанный список с пустыми узлами имеет узлы по адресам 0x520 -> 0x508 -> 0x518. Можно видеть, что поиск пустого узла (т.е. написание собственного API, похожего на malloc ()) теперь должен быть относительно быстрым, потому что мы можем быстро найти свободный узел. В реальных встроенных программах фиксированный кусок памяти (обычно называемый пулом памяти) выделяется с помощью malloc () только один раз модулем. И затем управление этим пулом памяти (который в основном является массивом) осуществляется самим этим модулем с использованием методов, упомянутых ранее. Иногда существует несколько пулов памяти, каждый из которых имеет разный размер узла. Конечно, есть несколько других аспектов управления собственной памятью, но мы оставим это здесь сами. Но стоит упомянуть, что есть несколько методов, с помощью которых вставка (которая требует нашего собственного выделения памяти) и удаление (которое требует нашего собственного освобождения памяти) могут быть улучшены далее.

Если мы посмотрим внимательнее, то можно заметить, что раздел кучи памяти представляет собой большой массив байтов, который управляется базовой операционной системой (ОС). И ОС предоставляет эту услугу управления памятью программистам через malloc (), free () и т. Д. Ага !!

Важные выводы из этой статьи можно суммировать следующим образом:

А) Массив означает непрерывную память. Он может существовать в любом разделе памяти, будь то Data, Stack или Heap.
Б) Связанный список означает несмежную связанную память. Он может существовать в любом разделе памяти, будь то куча, данные или стек.
C) Как программист, взгляд на структуру данных с точки зрения памяти может дать нам лучшее понимание при выборе конкретной структуры данных или даже при проектировании новой структуры данных. Например, мы можем создать массив связанных списков и т. Д.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Подход программиста к просмотру массива и связанного списка

0.00 (0%) 0 votes