Структура данных - это способ хранения и организации данных. Как вы организуете эти данные, зависит от вас.
Что такое связанный список?
Сегодня мы поговорим о структурах данных Singly Linked List и о том, как реализовать их в JavaScript. Односвязный список - это набор узлов, каждый из которых имеет прямую ссылку на следующий узел в коллекции. Первый узел в списке называется заголовком, а последний узел в списке называется хвостом.
Класс узла
Узел можно визуализировать как один из «прямоугольников» на схеме, представленной выше. Узел - это простой объект JavaScript с двумя свойствами.
данные: значение узла
следующий: прямая ссылка на следующий узел в списке.
Начнем с реализации узла в JavaScript. Я буду использовать классы для реализации односвязного списка. Вы также можете использовать функции, но я просто предпочитаю использовать класс для своего шаблона.
Приведенный выше код создает класс узла с конструктором, он получает данные, которые являются значением, которое будет храниться в узле. Следующее свойство по умолчанию - null, потому что мы еще не знаем, какой следующий узел находится в списке.
LinkedList Класс
Хорошо, теперь, когда мы можем создавать узлы с данными, нам нужно где-то разместить эти узлы. Давайте создадим класс связанного списка.
Приведенный выше код создает класс LinkedList с конструктором, конструктор не получает аргументов. По умолчанию для головы и хвоста установлено значение null. Для свойства length по умолчанию установлено значение «0», поскольку в списке нет узлов.
Хорошо, у нас есть два класса: один для создания узлов, а другой для их хранения. Но как нам точно сохранить узел в списке? Что ж, для этого нам нужны методы с функциональностью.
Методы
Мы добавим шесть методов в класс LinkedList.
push (значение) - Добавить узел в конец связанного списка
pop () - Удаляет узел из конца связанного списка
get (index) - возвращает узел по указанному индексу
delete (index) - Удалить узел по указанному индексу
isEmpty () - возвращает истину или ложь в зависимости от длины списка
print () - возвращает видимое представление связанного списка
Я напишу все методы отдельно для чистоты, обратите внимание, что все эти методы находятся в классе LinkedList.
Метод push
Давайте рассмотрим первый метод в списке выше, push (). Таким образом мы можем поместить узлы в LinkedList.
Метод push добавляет узел в конец списка. Это один из самых простых способов реализовать. Метод push получает один аргумент - значение узла.
Вот что он должен делать.
- Создать новый узел
- Проверьте, существует ли голова, если нет, то узел - это и хвост, и голова.
- Установите свойство current tails next для нового узла, так как новый узел будет добавлен в конец списка.
- Установите хвост на новый узел.
- Увеличить свойство длины
Вот как мы это делаем в JavaScript:
Метод isEmpty
Замечательно, теперь у нас есть возможность добавлять узлы в связанный список. Давайте реализуем метод isEmpty. Это очень просто :)
Вот что он должен делать:
- Вернуть истину или ложь в зависимости от длины списка
Вот как мы это делаем в JavaScript:
Поп-метод
Метод pop немного сложнее, поскольку нам нужно знать предпоследний узел, чтобы вытолкнуть последний узел в списке. На этом этапе вы можете спросить, почему я не могу просто получить доступ к последнему индексу или другим методам, которые я использовал ранее для массива?
Одним из недостатков связного списка является обход, вам нужно начинать с головного узла и перемещаться по каждому узлу в списке. Вы не можете просто использовать arr [2] для доступа к узлу в списке. Я расскажу о некоторых преимуществах и недостатках связанного списка в конце этой статьи.
Вот что должен делать метод pop:
- Вернуть null, если список пуст
- Если голова является хвостом, установите для головы и хвоста значение null. Уменьшить длину списка и вернуть хвост
- Найдите предпоследний узел и установите для его следующего свойства значение null.
- Установите хвост на предпоследний узел
- Уменьшить длину и вернуть удаленный узел
Если вы похожи на меня, то визуальный график поможет вам понять, что именно здесь должно происходить.
Нам нужно найти предпоследний узел и присвоить его следующему свойству значение null, теперь старый хвост будет удален, а предпоследний станет новым хвостом.
Вот как мы это делаем в JavaScript:
Метод get
Метод get получает один аргумент - индекс. Вот что он должен делать:
- Если index равен 0, вернуть голову
- Если индекс меньше 0 или индекс больше длины списка, вернуть null
- Найдите и верните узел по указанному индексу
Вот как мы это делаем в JavaScript:
Метод удаления
Метод удаления получает один аргумент - индекс. Вот что он должен делать:
- Если index равен 0, установите свойство next для текущего узла в начало. (следующий узел в списке станет новой головой). Уменьшите длину и верните удаленный узел.
- Если индекс меньше 0 или индекс больше длины списка, вернуть null
- Найдите узел перед узлом, который необходимо удалить, установите для его следующего свойства следующее свойство узла, который необходимо удалить.
- Уменьшите свойство длины и верните удаленный узел
Вот как мы это делаем в JavaScript:
Метод печати
Последний метод, который мы собираемся реализовать, - это метод печати. Это скорее визуальный помощник, чем предоставление каких-либо функций структуре данных.
Вот что он должен делать:
- Вернуть все узлы, соединенные стрелкой
Вот как мы это делаем в JavaScript:
Если бы у нас было три узла в связанном списке, A, B и C. Теперь мы можем визуализировать, что происходит, следующим образом: «A =› B = ›C
Полная реализация
Как мы его используем?
Все, что вам нужно сделать, это создать переменную и назначить ее новому экземпляру класса LinkedList.
Теперь просто используйте эту переменную и методы, предоставленные в классе LinkedList.
Заключительное заявление
Вставки и удаления в связанном списке выполняются очень быстро. Связанные списки динамичны и очень гибки. Но вы не должны использовать список ссылок везде, например, они очень медленные, когда дело доходит до перехода. Также нет возможности случайным образом выбрать узел из связанного списка, как в массиве.
Хорошим вариантом использования структуры данных связанного списка может быть музыкальный проигрыватель. Если пользователь нажимает следующую кнопку, вы перемещаете следующую песню в списке. Узел может быть песней, а его следующее свойство может быть ссылкой на следующую песню в списке.
Напишите мне в Twitter, если у вас есть какие-либо вопросы или вы просто хотите поговорить о коде и структурах данных!
