Начните использовать эту структуру данных вместо массива!
Выбор правильного способа хранения ваших данных - одна большая задача. Существует множество структур данных, и ни одна структура данных не подходит для каждой проблемы. Лучшее, что вы можете сделать, - это определить использование каждой структуры данных и определить, какая из них наиболее эффективна для конкретного случая.
Связанный список всегда был кошмаром для меня и моих коллег при изучении структур данных. Иногда меня беспокоило, почему существует даже эта структура данных, если у нас уже был простой «массив». Что ж, если вы думаете так же, как я, значит, вы этого не понимаете по сути. Итак, мы сразу же приступим к делу и ответим на вопрос на миллион долларов: что такое связанный список?
Что такое связанный список?
Связанный список относится к линейной структуре данных. В линейной структуре данных элементы данных расположены последовательно, и каждый элемент-член связан со своим предыдущим и следующим элементом. Мы можем не осознавать, но хорошо известные «массив» или «список» также относятся к категории линейных структур данных. Линейные структуры данных лучше всего использовать для хранения последовательных данных (упорядоченных данных).
Динамическое программирование
Но в чем проблема простого «массива»? Объявление массива необходимо перед компиляцией, потому что компилятор должен знать, сколько места в памяти необходимо выделить для каждой переменной. Следовательно, когда мы объявляем размер массива в начале, мы не можем изменить размер массива во время выполнения кода. Наивным решением было бы выбрать большое число для размера массива, но это было бы неэффективно и было бы пустой тратой памяти.
Вот где приходит на помощь динамическое распределение памяти! Во-первых, нам нужно понять, что существует 2 типа распределения памяти: статическое и динамическое. Элементы статической памяти распределяются в стеке таким образом, чтобы объявленные переменные сохранялись в соответствующем порядке непрерывно. С другой стороны, элементы динамической памяти размещаются в куче. В отличие от стека, в куче вы не знаете, где была выделена память, для каждого запроса, который вы делаете, будет назначен случайно выбранный блок памяти для хранения значения.
К счастью, в C они предоставляют наиболее полезную функцию для динамического выделения памяти, malloc (). Вот синтаксис этой функции.
void * malloc (размер_т размер)
Эта функция резервирует размер требуемых байтов для запрошенной переменной / структуры и возвращает выделенный адрес в куче. Если запрошенный объем памяти недоступен, функция вернет NULL. Есть некоторые другие функции, которые поддерживают динамическое выделение памяти, ie calloc () и realloc (), но мы не будем углубляться в эти функции. .
Структура связного списка
Связанный список - это структура данных, основанная на динамическом распределении памяти. По сути, связанный список состоит из узлов и ссылок. Мы можем создать простую структуру, состоящую из контейнера для хранения значения и указателя на следующий узел.
В структуре ListNode int item объявляется для хранения значения в узле, а struct _listnode * next объявляется для хранения адреса следующего узла. Если это последний узел, то следующий будет указывать на NULL.
Отлично! Теперь мы можем отслеживать второй узел по первому узлу, а также третий узел по второму узлу. Но как нам отслеживать первый узел? Без адреса первого узла второй и третий узлы будут недоступны. Поэтому мы введем указатель головы. Указатель заголовка не является узлом, вместо этого это указатель, в котором хранится адрес первого зеленого блока, который является первым узлом.
Пример связанного списка
Мы наконец определились со структурой связанного списка и с тем, как он работает. Теперь приступим к кодированию. Я расскажу вам простой код.
Вот результат связанного списка после выполнения кода.
Как видно из кода, связанный список во многом зависит от функции malloc () для динамического выделения некоторой памяти для новых узлов. Причина, по которой нам нужно использовать временную переменную, заключается в том, что мы не хотим изменять адрес, хранящийся в указателе заголовка. Впоследствии, после выполнения этого кода, указатель заголовка по-прежнему будет указывать на первый узел, тогда как временный указатель будет указывать на последний узел.
Связанный список в Python
БОНУС: Связанный список также может быть создан на других языках программирования, таких как Python, Java и т. Д. Хотя Python не имеет указателя или структур, классы могут помочь программистам Python создать связанный список.
Мы можем создать 2 класса. Первый - это класс ListNode, который используется для хранения значения и следующего указателя. Второй - это класс LinkedList, который используется так же, как указатель заголовка в C. Итак, вот простой код для применения связанного списка в Python.
Заключительные слова
Связанный список - одна из самых важных структур данных в компьютерных науках. Это базовая основа для создания других структур данных, таких как стек и очередь. Структура связного списка также не ограничивается простым связанным списком (который мы обсуждаем в этой статье). Существуют более сложные типы связанных списков, в том числе двусвязный список и круговой связанный список, которые соответствуют потребностям.
Начните изучать различные структуры данных, чтобы помочь вам выбрать правильную структуру данных (или даже их комбинацию!) Для решения конкретной проблемы.
С уважением,
Хуан Самуэль Сугианто
