Привет, Мой Великолепный Друг В Интернете
Это вторая часть моей серии “Структуры данных и алгоритмы”. Проверять Первая статья Для Введение в структуры данных и Массивы .
В этом посте сначала мы поговорим о структуре данных Связанного списка, о том, почему мы должны ее использовать, и о простых программах Java, реализующих Связанный список.
Кроме того, проверьте мой репозиторий GitHub для всех программ:
джеймс шах/Структуры Данных И Алгоритмы
Структуры Данных И Алгоритмы Для Целей Обучения.
Связанный список
Итак, самый первый вопрос, который приходит мне в голову, – это:
Что Такое Связанный Список?
- Связанный список – это определенный список некоторых элементов данных, связанных друг с другом. При этом каждый элемент указывает на следующий элемент, который представляет логический порядок.
- Каждый элемент называется “узлом”, который состоит из двух частей. Часть ДАННЫХ, в которой хранится информация, и УКАЗАТЕЛЬ, указывающий на следующий элемент.
- Первый “узел” связанного списка называется “head”.
Поле УКАЗАТЕЛЯ последнего узла равно “null”, что означает, что оно не указывает ни на один элемент.
Мы можем получить доступ к связанному списку, используя адрес головного узла а затем он дает нам адрес следующего узла и так далее. Это как охота за сокровищами: ты идешь к первому парню и узнаешь местонахождение следующего парня.
Почему Связанный список?
- И ответ заключается в том, что Связанный список лучше Массивов с точки зрения пространственной сложности и с точки зрения временной сложности.
- В массивах мы должны заранее знать максимальный размер массива, потому что массивы представляют собой непрерывный набор элементов. Под непрерывным мы подразумеваем, что элементы массива находятся рядом друг с другом в памяти без пробелов между ними.
- И, таким образом, если мы хотим ввести больше элементов, чем размер массива, нам нужно создать новый массив большего размера, а затем скопировать все элементы в этот новый массив. Этот процесс занимает очень много времени и, следовательно, непрактичен.
- Использование памяти в массиве неэффективно. И наоборот, в Связанном списке эффективно используется память.
Типы Связанного Списка
- Односвязный список
- Двусвязный список
- Круговой Связанный список
Односвязный список
- Односвязный список – это базовый тип связанного списка. Односвязный список – это набор узлов, связанных последовательно, где каждый узел односвязного списка содержит поле данных и поле адреса, содержащее ссылку на следующий узел.
Вот простая программа, реализующая связанный список на Java.
Вставка Узлов В Связанный Список
Существует в общей сложности три возможности вставки узла в связанный список, как показано ниже.
- Вставка узла в начало связанного списка
- Вставка узла в конец связанного списка
- Вставка узла в определенное место в связанном списке (т.е. после заданного узла.)
Вот программа, которая показывает все три вставки в связанном списке.
А теперь мы увидим полную программу с реализацией Связанного списка, а также со всеми возможностями вставки узла.
В следующей статье мы увидим больше операций со Связанным списком.
Спасибо За Прокрутку, Оставайтесь Здесь ✌ 🏻 . Счастливого кодирования! 💻 🖤
Оригинал: “https://dev.to/jamesshah/data-structures-and-algorithms-day-2-430k”