Почему стоит прочитать весь пост
- Чтобы узнать или обновить в связанных списках.
- Чтобы не просто читать код, а выполнять и понимать концепции.
- Изучить и практиковать лучшие практики машинописи.
- Чтобы испачкать руки в функциональном программировании.
Краткое введение:
Что такое связанный список?
Связанный список — это последовательный список узлов, содержащих данные и указатели.
Данные → Данные → Данные → ноль
Где используются связанные списки?
- Используется во многих реализациях списка, очереди и стека.
- Отлично подходит для создания круговых списков.
- Может легко моделировать объекты реального мира, такие как поезда.
- Используется в отдельной цепочке, которая присутствует в некоторых реализациях хеш-таблиц для обработки коллизий хеширования.
- Часто используется при создании списков смежности для графов.
Терминология
Начало: первый узел в связанном списке.
Хвост: последний узел в связанном списке. list.
Указатель: Ссылка на другой узел.
Узел: Объект, содержащий данные и указатель(и).
Односвязные и двусвязные списки
Односвязные списки содержат ссылку только на следующийузел. Во время реализации вы всегда должны поддерживать ссылку на голову связанного списка и ссылку на хвост. узел для быстрого добавления/удаления.
В двусвязном списке каждый узел содержит ссылку на следующийи предыдущийузел. В реализации вы всегда должны поддерживать ссылку на голову и хвост двусвязного списка для выполнять быстрые добавления/удаления с обоих концов списка.
За и против
Односвязные списки имеют простую реализацию и потребляют меньше памяти. Однако одиночные списки не могут легко получить доступ к предыдущим элементам.
Двусвязные списки можно перемещать назад, но они занимают в два раза больше памяти.
Пожалуйста, прежде чем двигаться дальше, настройте среду узла, используя nodemon и компилятор машинописного текста.
Выполнение
Итак, приступим к грязной работе
Создайте класс для узла односвязного списка. Обратите внимание, что односвязный список имеет только следующую ссылку. В отличие от двусвязных, у которых есть следующий и предыдущий.
Создайте интерфейс с методами, которые мы будем использовать в классе.
Сделав это, давайте напишем два метода, которые вставляют головной узел.
- вставить в голову ()
- РазмерСписка(). Мы будем использовать его для установки хвостового значения.
Теперь давайте добавим метод для вставки хвостового узла.
ДАЛЕЕ давайте удалим головной узел.
ДАЛЕЕ давайте удалим хвостовой узел.
ДАЛЕЕ давайте найдем конкретный узел:
ДАЛЕЕ давайте пройдемся по списку, чтобы получить массив.
ДАЛЕЕ Последний метод — вставка узла в любую позицию. Потратьте некоторое время на написание кода перед сравнением.
Это все для этой сессии. Я призываю вас поиграть с кодом, чтобы понять, что вы узнали. Например, изменить индекс InsertNode() с 1 на 0. Более того, что, если пользователь решит указать позицию меньше 0, например -1.
Спасибо за прочтение. Не стесняйтесь лайкать, подписываться или комментировать.
Исходный код здесь.