Я работаю в основном с JavaScript, но место, где я работаю, использует Java в бэкэнде. Всегда будучи очарованным различными языками программирования и различными способами выполнения задач – я решил изучать java! Технический руководитель моей команды предложил – почему бы не попробовать и не сделать все, что вы можете сделать в JavaScript на Java. Так и есть! Наряду с этим, как человек без степени CS, чем больше я углубляюсь в разработку программного обеспечения, тем больше мне становятся интересны основы. Итак, эта серия постов в блоге посвящена изучению структур данных в Java и JavaScript.
Следуя старым пословицам разработки программного обеспечения: “разбивать проблемы на как можно меньшие части” и “лучше поставлено, чем идеально”, я буду выполнять итерации постепенно и добавлять один или два метода к каждой структуре каждый раз, когда я пишу. Сначала JavaScript, затем переходим к Java. Это может занять некоторое время, так что держитесь за свои задницы!
🤔 WTF?
Представьте себе следующее: вы встречаетесь с другом в поезде, чтобы уехать из города на выходные, но череда неудачных событий означает, что вы прибываете на станцию Ватерлоо всего за несколько мгновений до отправления поезда со станции. После того, как вы пробираетесь сквозь толпу и барьеры, вам удается запрыгнуть в первый вагон поезда за несколько мгновений до того, как он отходит от станции. уф 😅 . Ты проверяешь свой телефон. Ваш друг написал вам, что они сидят в вагоне D. Вы оглядываетесь, и знак указывает, что вы находитесь в вагоне А. Вы начинаете пересекать вагон поезда за вагоном, пока не дойдете до вагона D и не найдете своего друга. Привет!
Связанный список немного похож на поезд, он состоит из частей – или узлов – каждая часть знает только о следующей. Это группа узлов, которые в совокупности представляют последовательность. Эти узлы не обязательно должны всегда располагаться один за другим, то есть занимать одно и то же физическое место в памяти, они просто знают, что будет дальше.
🧐 Варианты использования
Связанный список – это структура данных шлюза, поверх которой могут быть построены другие структуры данных. Хорошим примером этого является очередь “первый вход – первый выход”, тип, с которым вы можете столкнуться везде в программировании.
Связанный список действительно эффективен, если вы хотите добавить что-то в начале или в конце. Вы можете просто сделать новый узел заголовком и то, что было следующим заголовком нового узла. По сравнению с массивом, для вставки в начале вам потребуется переиндексировать каждый элемент в этом массиве.
🥺 Характеристики
Вот методы, которые я предлагаю реализовать для односвязного списка:
- добавить добавить узел в конец связанного списка.
- to string преобразовать связанный список в удобочитаемый формат.
- pop удалить последний элемент из списка.
- отменить сдвиг добавить узел в начало связанного списка.
- shift удалить первый элемент из списка.
- вставить вставить элемент с определенным индексом.
- удалить удалить значение из определенного индекса.
- reverse перевернуть список.
📜 JavaScript-кода
Создать узел
Прежде всего, нам нужен способ создания узла. Я собираюсь объявить функцию createNode , который принимает значение параметров, и далее. Он вернет объект, содержащий значение и следующее значение.
function createNode(value, next = null) {
return {
value,
next
}
}
Создать Связанный список
Теперь давайте создадим функцию, которая будет использовать createNode для создания экземпляра самого объекта списка ссылок. Функция create Linked List не будет принимать никаких параметров и изначально вернет объект со свойствами head, tail и length.
function createLinkedList() {
return {
head: null,
tail: null,
length: 0
}
}
Теперь наш список готов к приему некоторых методов!
Нажать или добавить
Push в JavaScript Array speak означает добавление в конец массива. Мы также могли бы вызвать это добавление, так как оно добавит новый узел в конец нашего списка.
Перво наперво давайте создадим наш новый узел
const node = createNode(value);
Затем давайте разберемся, что произойдет, если в списке ничего нет, другими словами, если нет заголовка. Если нет head, то наш новый узел будет head и tail, и нам нужно будет увеличить длину на 1. Наконец, мы вернем узел для выхода из кода.
if (!this.head)
this.head = node;
this.tail = node;
this.length++
return node;
}
Теперь, что произойдет, если в нашем списке уже есть что-то? Мы захотим, чтобы текущий хвост ссылался на новый узел в качестве следующего свойства, и новый узел станет хвостом. Затем мы увеличим длину, и на этом наш метод push завершен.
this.tail.next = node; this.tail = node; this.length++
Так что давайте соберем все это вместе…
function createLinkedList() {
return {
head: null,
tail: null,
length: 0,
push(value) {
const node = createNode(value);
if (!this.head) {
this.head = node;
this.tail = node;
this.length++
return this;
}
this.tail.next = node;
this.tail = node;
this.length++;
return this;
},
}
}
К Строке
Теперь у нас есть способ создать связанный список и добавить новые узлы в конец, было бы неплохо иметь метод, с помощью которого мы могли бы показать нам, что у нас есть в нашем списке, в удобочитаемом виде. Введите метод tostring.
По сути, идея состоит в том, чтобы напечатать каждый элемент с => между ними, чтобы базовый список выглядел следующим образом…
'1 => 2 => 3'
сначала мы создадим пустой массив для хранения значений каждого узла и создадим переменную current , которую мы будем использовать при перемещении по списку. мы сначала установим на голову.
const values = []; let current = this.head;
далее мы будем переходить от узла к узлу и добавлять каждое значение в массив values . Для этого мы будем использовать цикл while. Следующая дверь в конце связанного списка – null , мы будем использовать это, чтобы прервать цикл while
while(current) {
values.push(current.value);
current = current.next;
}
наконец, мы вернем массив values , объединенный в виде строки.
return values.join(' => ');
Теперь давайте соберем все это вместе и попробуем создать связанный список и распечатать его
function createLinkedList() {
return {
head: null,
tail: null,
length: 0,
push(value) {
const node = createNode(value);
if (!this.head) {
this.head = node;
this.tail = node;
this.length++
return this;
}
this.tail.next = node;
this.tail = node;
this.length++;
return this;
},
toString() {
const values = [];
let current = this.head;
while(current) {
values.push(current.value);
current = current.next;
}
return values.join(' => ');
}
}
}
const list = createLinkedList();
list.push(1)
list.push(2)
list.push(3)
console.log(list.toString());
//prints '1 => 2 => 3' to the console.
Оригинал: “https://dev.to/freddieduffield/data-structures-two-ways-linked-list-2n61”