Введение в связанный список — учебные пособия по структуре данных и алгоритмам
Что такое связанный список?
A Linked List is a linear data structure which looks like a chain of nodes, where each node is a different element. Unlike Arrays, Linked List elements are not stored at a contiguous location.
В основном это цепочки узлов , каждый узел содержит такую информацию, как данные и указатель на следующий узел в цепочке. В связанном списке есть указатель head , который указывает на первый элемент связанного списка, и если список пуст, то он просто указывает на null или ничего.
Зачем нужна структура данных связанного списка?
Вот несколько преимуществ связанного списка, который указан ниже, это поможет вам понять, почему это необходимо знать.
- Динамическая структура данных: размер памяти может быть выделен или освобожден во время выполнения в зависимости от операции вставки или удаления.
- Простота вставки/удаления: вставка и удаление элементов проще, чем массивы, поскольку после вставки и удаления не нужно сдвигать элементы, нужно только обновить адрес.
- Эффективное использование памяти. Как мы знаем, связанный список — это динамическая структура данных, размер которой увеличивается или уменьшается в соответствии с требованиями, что позволяет избежать потери памяти.
- Реализация: различные расширенные структуры данных могут быть реализованы с использованием связанного списка, такого как стек, очередь, граф, хэш-карты и т. д.
Типы связанных списков:
В основном существует три типа связанных списков:
- Односвязный список
- Двойной связанный список
- Круговой связанный список
1. Односвязный список
Обход элементов может выполняться в прямом направлении только благодаря привязке каждого узла к следующему узлу.
Представление одного связанного списка:
- Создание узла:
C++
// A Single linked list nodeclass Node {public: int data; Node* next;}; |
C
// A Single linked list nodestruct Node { int data; struct Node* next;}; |
Java
// Linked List Classclass LinkedList { Node head; // head of list /* Node Class */ class Node { int data; Node next; // Constructor to create a new node Node(int d) { data = d; next = null; } }} |
Python3
# Node classclass Node: # Function to initialize the node object def __init__(self, data): self.data = data # Assign data self.next = None # Initialize next as null # Linked List class class LinkedList: # Function to initialize the Linked List object def __init__(self): self.head = None |
C#
/* A Single Linked list Node*/public class Node { public int data; public Node next; public Node(int d) { data = d; next = null; } |
Javascript
<script>// Linked List Class var head; // head of list /* Node Class */ class Node { // Constructor to create a new node constructor(d) { this.data = d; this.next = null; } } </script> |
Часто используемые операции с односвязным списком:
Следующие операции выполняются над одним связанным списком.
- Вставка: Операция вставки может быть выполнена тремя способами. Они следующие…
- Вставка в начало списка
- Вставка в конец списка
- Вставка в определенное место в списке
- Удаление: операцию удаления можно выполнить тремя способами. Они следующие…
- Удаление с начала списка
- Удаление из конца списка
- Удаление определенного узла
- Поиск: это процесс определения и извлечения определенного узла либо с начала, с конца, либо из любого места в списке.
- Отображение: этот процесс отображает элементы односвязного списка.
Практические задачи на односвязный список:
| С.но | Вопрос | Статья |
|---|---|---|
| 1 | Введение в связанный список | Вид |
| 2 | Обнаружение цикла в связанном списке | Вид |
| 3 | Найти длину цикла в связанном списке | Вид |
| 4 | Функция для проверки, является ли односвязный список палиндромом | Вид |
| 5 | Удаление дубликатов из отсортированного связанного списка | Вид |
| 6 | Удалить дубликаты из несортированного связанного списка | Вид |
| 7 | Удалить цикл в связанном списке | Вид |
| 8 | Обмен узлами в связанном списке без обмена данными | Вид |
| 9 | Переместить последний элемент в начало заданного связанного списка | Вид |
| 10 | Пересечение двух отсортированных связанных списков | Вид |
2. Двусвязный список
Обход элементов может выполняться как в прямом, так и в обратном направлении, поскольку каждый узел содержит дополнительный указатель prev , указывающий на предыдущий узел.
Представление двусвязного списка:
Создание узла:
Часто используемые операции над двусвязным списком:
В двусвязном списке мы выполняем следующие операции…
- Вставка: Операция вставки может быть выполнена тремя способами:
- Вставка в начало списка
- Вставка после заданного узла.
- Вставка в конце.
- Вставка перед данным узлом
- Удаление: Операция удаления может быть выполнена тремя способами:
- Удаление с начала списка
- Удаление из конца списка
- Удаление определенного узла
- Отображение: этот процесс отображает элементы двусвязного списка.
Практические задачи на двусвязный список:
| С.но | Вопрос | Статья |
|---|---|---|
| 1 | Обратный двусвязный список | Вид |
| 2 | Скопируйте связанный список с указателем next и arbit | Вид |
| 3 | Поменять местами K-й узел с начала на K-й узел с конца в связанном списке | Вид |
| 4 | Сортировка слиянием для двусвязного списка | Вид |
| 5 | Сортировка по двусвязному списку | Вид |
| 6 | Удалить дубликаты из несортированного связанного списка | Вид |
| 7 | Повернуть двусвязный список на N узлов | Вид |
| 8 | Слияние двух сбалансированных бинарных деревьев поиска | Вид |
| 9 | Преобразование двоичного дерева в двусвязный список по спирали | Вид |
| 10 | Преобразование данного двоичного дерева в двусвязный список | Вид |
3. Круговые связанные списки
Круговой связанный список — это тип связанного списка, в котором первый и последний узлы также связаны друг с другом, образуя круг, в конце которого нет NULL.
Часто используемые операции с циклическим связанным списком:
Следующие операции выполняются над циклическим связанным списком.
- Вставка: Операция вставки может быть выполнена тремя способами:
- Вставка в пустой список
- Вставка в начало списка
- Вставка в конец списка
- Вставка между узлами
- Удаление: Операция удаления может быть выполнена тремя способами:
- Удаление с начала списка
- Удаление из конца списка
- Удаление определенного узла
- Отображение: этот процесс отображает элементы кругового связанного списка.
Практические задачи в круговом связанном списке:
| С.но | Вопрос | Статья |
|---|---|---|
| 1 | Циклический обход связанного списка | Вид |
| 2 | Разделить круговой связанный список на две половины | Вид |
| 3 | Отсортированная вставка для кругового связанного списка | Вид |
| 4 | Проверить, является ли связанный список циклическим связанным списком | Вид |
| 5 | Удаление из кругового связанного списка | Вид |
| 6 | Круг Иосифа Флавия с использованием кругового связанного списка | Вид |
| 7 | Преобразование односвязного списка в кольцевой связанный список | Вид |
| 8 | Реализация Deque с использованием кругового массива | Вид |
| 9 | Поменять местами первый и последний узлы в циклическом связанном списке | Вид |
| 10 | Подсчет узлов в круговом связанном списке | Вид |
Связанный список против массива
Связанный список против массива во временной сложности
| Операция | Связанный список | Множество |
|---|---|---|
| Произвольный доступ | НА) | О(1) |
| Вставка и удаление в начале | О(1) | (Н) |
| Вставка и удаление в конце | НА) | О(1) |
| Вставка и удаление в произвольном месте | НА) | НА) |
Преимущества связанных списков:
- Динамический характер: связанные списки используются для динамического выделения памяти.
- Эффективность памяти: потребление памяти связным списком эффективно, поскольку его размер может динамически увеличиваться или уменьшаться в соответствии с нашими требованиями, что означает эффективное использование памяти, следовательно, отсутствие потери памяти.
- Простота вставки и удаления: вставка и удаление узлов легко реализуются в связанном списке в любой позиции.
- Реализация: для реализации стеков и очередей, а также для представления деревьев и графов.
- Связанный список может быть расширен за постоянное время.
Недостатки связанных списков:
- Использование памяти: использование указателей больше в связанных списках, следовательно, сложно и требует больше памяти.
- Доступ к узлу: произвольный доступ невозможен из-за динамического выделения памяти.
- Дорогостоящая операция поиска: поиск элемента является дорогостоящим и требует O (n) временной сложности.
- Обход в обратном порядке: Обход требует больше времени, а обратный обход невозможен в односвязных списках.
Приложения связанного списка:
Вот некоторые из приложений связанного списка:
- Линейные структуры данных, такие как стек, очередь, и нелинейные структуры данных, такие как хэш-карты и графики, могут быть реализованы с использованием связанных списков.
- Динамическое выделение памяти: мы используем связанный список свободных блоков.
- Реализация графов. Представление графов в виде списка смежности является наиболее популярным, поскольку оно использует связанные списки для хранения смежных вершин.
- В веб-браузерах и редакторах двусвязные списки можно использовать для создания кнопки навигации вперед и назад.
- Циклический двусвязный список также можно использовать для реализации таких структур данных, как кучи Фибоначчи.
Применение связанных списков в реальном мире:
- Список песен в музыкальном проигрывателе связан с предыдущей и следующей песнями.
- В веб-браузере URL-адреса предыдущей и следующей веб-страницы связаны с помощью кнопок «Предыдущая» и «Далее».
- В средстве просмотра изображений предыдущее и следующее изображения связаны с помощью кнопок «предыдущее» и «следующее».
- Переключение между двумя приложениями осуществляется с помощью «alt+tab » в windows и « cmd+tab » в macbook. Для этого требуется функциональность кругового связанного списка.
- В мобильных телефонах мы сохраняем контакты людей. Новые введенные контактные данные будут размещены в правильном алфавитном порядке.
- Это может быть достигнуто с помощью связанного списка, чтобы установить контакт в правильном алфавитном положении.
- Модификации, которые мы внесли в документы, на самом деле созданы как узлы в двусвязном списке. Мы можем просто использовать опцию отмены, нажав Ctrl+Z , чтобы изменить содержимое. Это делается с помощью функциональности связанного списка.
Наиболее часто задаваемые вопросы на собеседовании в связанном списке:
| С.но | Вопрос | Статья | Упражняться |
|---|---|---|---|
| 1 | Поиск среднего элемента в связанном списке | Вид | Решать |
| 2 | Отменить связанный список | Вид | Решать |
| 3 | Поворот связанного списка | Вид | Решать |
| 4 | Обратный связанный список в группах заданного размера | Вид | Решать |
| 5 | Точка пересечения в Y-образных связанных списках | Вид | Решать |
| 6 | Обнаружение цикла в связанном списке | Вид | Решать |
| 7 | Удалить цикл в связанном списке | Вид | Решать |
| 8 | n-й узел с конца связанного списка | Вид | Решать |
| 9 | Сведение связанного списка | Вид | Решать |
| 10 | Объединить два отсортированных связанных списка | Вид | Решать |
| 11 | Попарная замена связанного списка | Вид | Решать |
| 12 | Добавьте два числа, представленные связанными списками | Вид | Решать |
| 13 | Проверить, является ли связанный список палиндромом | Вид | Решать |
| 14 | Внедрение очереди с использованием связанного списка | Вид | Решать |
| 15 | Реализовать стек с помощью связанного списка | Вид | Решать |
| 16 | Учитывая связанный список из 0, 1 и 2, отсортируйте его | Вид | Решать |
| 17 | Удалить без указателя головы | Вид | Решать |
Часто задаваемые вопросы (FAQ) о связанном списке:
1. Что такое структура данных связанного списка?
Связанные списки чаще всего используются для обработки динамических элементов данных. Связанный список состоит из узлов, а узел состоит из двух полей, одно для хранения данных, а другое для хранения ссылки на следующий узел.
2. Что такое пример связанного списка?
Связанный список можно представить как гирлянду из цветов. Точно так же связанный список состоит из узлов. Каждый цветок в этой конкретной гирлянде называется узлом. Кроме того, каждый узел указывает на следующий узел в этом списке и содержит данные (в данном случае тип цветка).
3. Зачем нам нужна структура данных связанного списка??
Есть несколько важных преимуществ использования связанных списков по сравнению с другими линейными структурами данных. Это не похоже на массивы, так как их размер можно изменять во время выполнения. Кроме того, их можно легко вставлять и удалять.
4. Для чего используются связанные списки?
Связный список — это линейная структура данных, которая хранит данные в узлах. эти узлы содержат как данные, так и ссылку на следующий узел в списке. Linked очень эффективны при добавлении и удалении узлов из-за их простой структуры.
5. В чем разница между массивом и связанным списком?
Между ними есть следующие отличия:
- Массивы — это структуры данных, содержащие похожие элементы данных, тогда как связанные списки — это не примитивные структуры данных, содержащие неупорядоченные связанные элементы.
- В массиве элементы индексируются, а в связном списке узлы не индексируются.
- Доступ к массиву элементов выполняется быстро, если мы знаем положение элемента в массиве, в то время как в связанном списке это занимает линейное время, поэтому связанный список немного медленнее.
- Такие операции, как вставка и удаление в массивах, занимают много времени. Принимая во внимание, что производительность этих операций выше в связанных списках.
- Массивы имеют фиксированный размер, и их размер является статическим, но связанные списки являются динамическими и гибкими и могут увеличивать и уменьшать свой размер.
6. Почему связный список предпочтительнее массива?
Ниже приведены причины, по которым связанные списки предпочтительнее массивов.
- Узлы в связанном массиве, вставки и удаления могут выполняться в любой точке списка в постоянное время.
- Массивы имеют фиксированный размер, и их размер является статическим, но связанные списки являются динамическими и гибкими и могут увеличивать и уменьшать свой размер.
- Связанные списки обеспечивают эффективный способ хранения связанных данных и выполнения основных операций, таких как вставка, удаление и обновление информации, за счет дополнительного пространства, необходимого для хранения адреса.
- Операции вставки и удаления в связанном списке выполняются быстрее по сравнению с массивом.
7. В чем разница между односвязным и двусвязным списком?
Ниже приведены некоторые различия между односвязным и двусвязным списком.
| Односвязный список (SLL) | Двусвязный список (DLL) |
|---|---|
| Узлы SLL содержат 2 поля данных и поле следующей ссылки. | Узлы DLL содержат 3 поля: поле данных, поле предыдущей ссылки и поле следующей ссылки. |
| В SLL обход может быть выполнен только с использованием ссылки на следующий узел. Таким образом, обход возможен только в одном направлении. | В DLL обход может выполняться по ссылке на предыдущий узел или по ссылке на следующий узел. Таким образом, перемещение возможно в обоих направлениях (вперед и назад). |
| SLL занимает меньше памяти, чем DLL, так как имеет только 2 поля. | DLL занимает больше памяти, чем SLL, так как имеет 3 поля. |
| Сложность вставки и удаления в данной позиции составляет O(n). | Сложность вставки и удаления в заданной позиции составляет O(n/2) = O(n), потому что обход можно выполнять как с начала, так и с конца. |
| Сложность удаления с данным узлом составляет O (n), потому что предыдущий узел должен быть известен, а обход занимает O (n) | Сложность удаления с данным узлом составляет O (1), потому что к предыдущему узлу можно легко получить доступ. |
| Односвязный список потребляет меньше памяти по сравнению с двусвязным списком. | Двусвязный список потребляет больше памяти по сравнению с односвязным списком. |
8. Что лучше: массив или связанный список?
Как у массивов, так и у связанных списков есть некоторые преимущества и недостатки, когда речь идет о хранении линейных данных схожих типов.
Преимущества связного списка перед массивом:
- Динамический размер: связанные списки являются динамическими и гибкими и могут расширяться и уменьшаться в размере.
- Простота вставки/удаления: операции вставки и удаления в связанном списке выполняются быстрее по сравнению с массивом.
Недостатки связанного списка перед массивами:
- Если массив отсортирован, мы можем применить бинарный поиск для поиска любого элемента, который занимает время O (log (n)) . Но даже если связанный список отсортирован, мы не можем применить бинарный поиск, а сложность поиска элементов в связанном списке составляет O(n) .
- Связанный список занимает больше памяти по сравнению с массивом, потому что для указателя с каждым элементом в связанном списке требуется дополнительное место в памяти.
9. Каковы ограничения связанного списка?
Ниже приведены некоторые ограничения связанного списка:
- Использование указателей больше в связанных списках, следовательно, сложно и требует больше памяти.
- Произвольный доступ невозможен из-за динамического выделения памяти.
- Обход требует больше времени, а обратный обход невозможен в односвязных списках.
- Поиск элемента является дорогостоящим и требует O(n) временной сложности.
10. Почему вставка/удаление быстрее в связанном списке?
Если какой-либо элемент вставляется/удаляется из массива, все остальные элементы после него будут перемещены в память, это занимает много времени, тогда как манипуляции в связанном списке выполняются быстрее, потому что нам просто нужно манипулировать адресами узлов, поэтому без смещения битов требуется в памяти, и это не займет много времени.
Вывод
Есть много преимуществ связного списка по сравнению с массивом, несмотря на то, что они решают ту же проблему, что и массивы, мы также обсудили преимущества, недостатки и его применение, и мы пришли к выводу, что мы можем использовать связанный список, если нам нужен динамический размер хранилища, и список хорош для быстрого добавления и удаления элементов или для задач, требующих последовательности, но не подходит для запроса или поиска элементов в большом наборе данных.
Таким образом, становится важным, чтобы мы всегда помнили о положительных и отрицательных аспектах структуры данных и о том, как они связаны с проблемой, которую вы пытаетесь решить.
Статьи по Теме:
- Полное руководство по подготовке к интервью Arrays
- Структура данных, которую должен знать каждый программист
- Как начать изучение данных DSA?
- Что такое хеширование | Полное руководство
- Как легко освоить структуры данных и алгоритмы?
- Почему важно изучать структуры данных и алгоритмы?
- 15 лучших веб-сайтов для соревнований и соревнований по программированию
- SDE SHEET — Полное руководство по подготовке к SDE
- Amazon SDE Sheet — руководство по подготовке к интервью Amazon SDE
- Подготовка к собеседованию в Google для инженера-программиста — полное руководство
- 100 дней кода — полное руководство для начинающих и опытных