Обзор

Позвольте мне поделиться с вами своим опытом работы со связанным списком. Недавно в одном из моих проектов у меня была возможность применить реальный контекст к структуре данных. Мне удалось реализовать модифицированный двусвязный список в качестве структуры данных для моего проекта.

Здесь я собираюсь поделиться некоторыми интересными вещами о связанном списке с некоторыми примерами из реального мира. Итак, давайте сначала изучим некоторые основы связанного списка.

Что такое связанный список?

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

Один связанный список

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

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

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

Круговой связанный список

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

Круговой двусвязный список

Циклический двусвязный список — это более сложный тип структуры данных, в котором узел содержит указатели на предыдущий узел, а также на следующий узел. Циклический двусвязный список не содержит NULL ни в одном из узлов. Первый узел списка также содержит адрес последнего узла в его предыдущем указателе.

Техника БЕГУН

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

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

LOOP в связанном списке

Цикл в связанном списке — это состояние, возникающее, когда связанный список не имеет конца. Когда цикл существует в связанном списке, последний указатель не указывает на нулевой как в односвязном или двусвязном списке, так и в заголовке связанного списка, как в циклическом связанном списке.

Теперь вопрос в том, как узнать, есть ли цикл в связном списке, для этого у нас есть много подходов. Но пока мы будем использовать,

"Алгоритм поиска циклов Флойда" –

Это самый быстрый метод, описанный ниже:

  • Обход связанного списка с использованием двух указателей.
  • Переместите один указатель (медленно) на один, а другой указатель (быстро) на два.
  • Если эти указатели встречаются в одном и том же узле, возникает петля. Если указатели не встречаются, то связанный список не имеет цикла.

Лучший связанный список среди них

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

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

Если у вас нет проблем с пространством, я могу сказать, что двунаправленный связанный список — лучший, потому что —

Список можно пройти в обоих направлениях, т. е. от головы к хвосту, от хвоста к голове.

Прыжки в обоих направлениях выполняются за постоянное время O(1).

Используется для реализации расширенных структур данных, таких как куча Фибоначчи.

Используется при разработке реальных приложений, таких как управление списком воспроизведения песен в приложении медиаплеера.

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

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

  • Индексирование. В связанном списке индексирование занимает время O (n), тогда как массив занимает O (1).
  • Вставка/удаление в начале. В связанном списке Вставка/удаление в начале занимает время O (1), тогда как массив занимает время O (n), если массив не заполнен (для смещения элементов).
  • Вставка/удаление в конце. В связанном списке Вставка/удаление в конце занимает время O (n), тогда как для вставки массива требуется время O (1) (если массив не заполнен).
  • Вставка/удаление в середине. В связанном списке требуется время O (n), тогда как в массиве требуется время O (n), если массив не заполнен (для смещения элементов).

Реальный пример — связанный список

Давайте рассмотрим пример, чтобы понять работу связанных списков, используя список воспроизведения песен медиаплеера. И для этой цели я использую двусвязный список. Причина, по которой я выбрал двусвязный список, заключалась в том, что его структура соответствовала поведению музыкального плейлиста.

Перейти назад/вперед

Поскольку каждый узел в двусвязном списке имеет указатель на предыдущий и следующий узлы, легко реализовать функцию пропуска вперед/назад.

Добавить

Когда вы добавляете новый трек в плейлист, вы добавляете его в конец. В связанном списке добавление нового элемента выполняется за постоянное время — операция O(1).

Начало/Конец

Наконец, поскольку связанный список имеет свойства начала и конца, это обеспечивает простой способ разграничить начало и конец списка воспроизведения.

Воспроизвести следующий трек

Указатель на следующий узел также упрощает запуск следующей дорожки, когда дорожка закончилась.

Преимущества и недостатки

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

Подведение итогов

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