Что такое LinkedList
Я решил глубже изучить структуры данных и алгоритмы, что побудило меня купить курс по Udemy «Структуры данных и алгоритмы» Скотта Баррета. Концепция курса была сосредоточена на визуализации проблемы, а не на погружении в нее с головой. Этот прием очень помог, когда дело дошло до реализации методов. Курс был посвящен связному списку, который представляет собой линейную структуру данных. Каждый элемент - это отдельный объект, который содержит указатель или ссылку на следующий объект. Другими словами, связанные списки связаны и работают иначе, чем массивы.
Преимущества / недостатки
При работе с LinkedList существуют ограничения на то, что вы можете делать. Однако есть преимущества, такие как хранение ряда значений без переопределения памяти. Кроме того, они используются в качестве основы для встроенных структур данных. К недостаткам можно отнести произвольный доступ к элементам, в отличие от массивов, которые включают произвольный доступ. LinkedList позволяет указать на следующий элемент, что, на мой взгляд, является преимуществом.
Начиная с ListNode
ListNode имеет конструктор, который содержит значение в качестве аргумента. Значение используется для создания новых узлов. Кроме того, next имеет значение null. Этот метод будет полезен при указании на узлы. Посмотрите на пример ниже.
Реализация нашего собственного узла
Теперь, когда у нас есть основы понимания LinkedLists, давайте попробуем применить это на практике, реализовав метод push. Для этого метода push потребуется новый узел, который будет добавлен в конец нашего связанного списка. Мы можем начать с создания нашего списка. Подобно нашему предыдущему примеру, должен быть конструктор, принимающий значение, которое будет коррелировать с новым узлом. Кроме того, впереди, равной нашему новому узлу, хвосту, равному голове, и длине, равной единице. Вот наглядный пример ниже.
Реализация нашего метода push
Как только это будет настроено, мы готовы реализовать наш метод push. Метод push принимает значение. Это значение будет частью нашего нового узла, поэтому мы можем начать с создания константы с именем newNode. Константа примет значение, переданное из аргумента.
Поскольку мы начинаем с головы списка, нам нужно создать сценарий, если головы не было. Если нет, мы просто установим и head, и tails в константу newNode, которую мы создали. Как только это условие будет выполнено, пора взглянуть на наш оператор else, который может оказаться непростым. Наш else укажет на хвост и установит его равным newNode. Наряду с указанием на хвост мы установим хвост на новый узел. Нашим последним шагом было бы вернуть наш список и увеличить его длину. Вот пример ниже.
Ниже приведены еще несколько методов.
- pop (): удаляет узел в конце списка.
2. Unshift (): добавить новый узел в начале.
3. Shift (): удаляет узел в начале списка.
4. Get (): возвращает индекс узла.
