Часть 1
Представьте, что на вас напала толпа. Представьте себе дрожащего человечка, который подходит к крестному и просит его о помощи. Представьте, что крестный отдает приказ нанести удар консильеру, а тот дает указания своему помощнику. Помощник идет к своему приятелю и протягивает ему пистолет, приятель разыскивает этого человека и сводит его к нулю. Это связанный список. Каждый узел имеет два атрибута: данные и ссылку на следующий узел.
Поиск в связанном списке занимает вечность, потому что вы должны пройти весь список, чтобы найти узел, что было бы неплохо, если бы узел, который вы ищете, был первым узлом, но представьте, что вы ищете 1 000 000 000 узлов.
Вставлять и удалять списки относительно легко, потому что все, что вам нужно сделать, это изменить его контрольную точку, но чтение узла занимает столько же времени, сколько номер узла от 0. Это противоречит массивам, потому что выборка данных из массива супер просто. Вы упоминаете индекс и стрелку, вы находитесь в значении, но вставка и удаление занимают «вечность» для компьютера, потому что вы должны переместить новый более короткий / больший массив в новое место в памяти.
Связанные списки в JavaScript - это в значительной степени просто объекты, размещенные друг в друге в парах "ключ-значение", что не идеально, но пока мне нравится JavaScript, поэтому я собрал все вместе. Когда я освоюсь с Java, я тоже напишу для этого пост.
Я мог бы продолжить о теории, но вот как мне нравится учиться. Я решаю кучу простых задач в Hackerrank или другом подобном сайте. Такое обучение обычно для меня имеет тенденцию к более глубокому изучению.
Чтобы получить любую теорию о связанных списках, посетите страницу Википедии.
Я не буду переписывать этот фрагмент кода каждый раз, поэтому классы Node и LinkedList здесь.
class Node {
constructor(data, next) {
this.data = data;
this.next = null;
}
};
class SinglyLinkedList {
constructor() {
this.head = null;
this.tail = null;
}
};
Я назову связанный список заголовком в параметрах функции.
Итак, сначала давайте начнем с основ, давайте попробуем вставить узел в начало связанного списка.
Вот логика:
1. Создайте новый узел
2. Если в связанном списке нет узлов, то узел, который мы хотим, становится головным.
3. В противном случае узел, который мы инициализировали, ссылается на голову, фактически становясь главой связанного списка.
const insertNodeAtHead => (head, data) = {
let newNode = new Node(data);
if (head == null) {
return newNode;
}
newNode.next = head;
return newNode;
}
Милая! Теперь, когда мы знаем, как добавить в связанный список, давайте посмотрим, как мы можем распечатать связанный список, прежде чем мы попытаемся еще немного поработать с ним.
1. Распечатайте данные узла
2. Перейти к следующему узлу
3. Делайте это до тех пор, пока заголовок не станет нулевым (это приведет нас от начала к концу списка).
const printLinkedList = (head) => {
while (head != null) {
console.log(head.data);
head = head.next;
}
}
Хорошо, теперь давайте попробуем вставить узел в конец связанного списка.
1. создать новый узел
2. Если головного узла нет, назначьте новый узел головным и верните его.
3. Затем давайте назначим временную переменную current в качестве заголовка.
4. продолжайте назначать следующий узел текущему, пока текущий следующий не станет нулевым (это приведет нас к концу связанного списка)
5. Теперь, когда мы находимся на последнем узле, назначьте новый узел в качестве следующего узла текущего.
6. вернуть связанный список
const insertNodeAtTail = (head, data) => {
let newNode = new Node(data);
if (!head) {
head = newNode;
return head;
}
let current = head;
while (current.next) {
current = current.next;
}
current.next = newNode;
return head;
}
давайте сделаем еще одну вставку, прежде чем мы перейдем к удалению некоторых узлов. Давайте вставим в определенное место. Функция имеет параметры заголовка связанного списка, данные для ввода и позицию, в которую должен быть вставлен узел.
1. объявить новый узел
2. объявить переменную currentPosition = 1
3. назначить напор временной переменной тока
4. Если позиция равна 0, то следующий переход нового узла будет во главе, и мы вернем связанный список из нового узла.
5. в противном случае мы используем позицию в качестве фиксированной точки и curentPosition в качестве точки перемещения для перемещения по связанному списку к узлу перед положением.
6. Оказавшись там, мы добавляем следующую ссылку newNode на узел в позиции
7. мы меняем следующую ссылку узла в currentPosition на новый узел
8. вернуть связанный список
Вот дерьмовая картинка, которую я нарисовал, чтобы понять это в своей голове ...
const insertNodeAtPosition = (head, data, position) => {
let newNode = new Node(data);
let current = head;
let currentPosition = 1;
if (position == 0) {
newNode.next = head;
return newNode;
}
while (currentPosition < position) {
current = current.next;
currentPosition++;
}
newNode.next = current.next;
current.next = newNode;
return head;
}
Прохладный. И наконец, давайте попробуем удалить узел из связанного списка.
В JavaScript есть система удаления мусора, как и в большинстве городов. Вы оставляете это без внимания, и оно каким-то образом исчезает. Итак, все, что нам действительно нужно сделать, это удалить следующую ссылку на узел, и она исчезнет.
1. назначить заголовок переменной с именем node
2. если позиция равна 0, то мы хотим удалить первую и вернуть остальные.
3. давайте создадим переменную currentPosition и присвоим ей значение 1 (чтобы отразить первую позицию в списке).
4. чтобы добраться до узла, предшествующего тому, который мы хотим удалить, мы назначим следующий узел текущему узлу и увеличим currentPosition до тех пор, пока он не станет на 1 меньше, чем позиция.
5. Теперь, когда мы находимся на узле перед тем, который нам нужно удалить, мы назначаем его рядом с узлом после следующего. Как и в случае, мы перепрыгиваем через узел, который хотим удалить, и удаляем ссылку на него.
6. вернуть связанный список
const deleteNode(head, position) {
let node = head;
let currentPosition = 1;
if (position == 0) {
return node.next;
}
while (currentPosition < position) {
node = node.next;
currentPosition++;
}
node.next = node.next.next;
return head;
}
Есть еще пара проблем, которые я хотел бы решить, но я разделю их на два сообщения, чтобы было удобнее читать. Итак, возьмите стакан воды и посмотрите часть 2.
Больше контента на plainenglish.io
