Связный список — это структура данных, состоящая из последовательности узлов, где каждый узел содержит значение и ссылку (или «ссылку») на следующий узел в последовательности. Связанные списки часто используются для реализации других структур данных, таких как стеки, очереди и деревья.
В JavaScript связанный список может быть реализован с использованием объектов и массивов. Каждый узел в связанном списке может быть представлен как объект со свойством value и свойством next, который является ссылкой на следующий узел в последовательности. Сам связанный список может быть представлен в виде массива узлов, где первый узел является началом списка, а последний узел — хвостом списка.
Вот пример создания связанного списка в JavaScript:
// Create the nodes for the linked list
const node1 = { value: 1, next: null };
const node2 = { value: 2, next: null };
const node3 = { value: 3, next: null };
// Link the nodes together to form a linked list
node1.next = node2;
node2.next = node3;
// Create an array to represent the linked list
const linkedList = [node1, node2, node3];
В приведенном выше примере мы создаем три узла, каждый из которых содержит свойства value и next. Затем мы связываем узлы вместе, чтобы сформировать связанный список, устанавливая свойство next каждого узла для ссылки на следующий узел в последовательности. Наконец, мы создаем массив для представления связанного списка, где первый элемент является началом списка, а последний элемент — хвостом списка.
Чтобы вставить новый узел в связанный список, нам сначала нужно найти правильную позицию для вставки узла. Обычно это делается путем обхода связанного списка, начиная с головы и переходя от одного узла к другому, пока мы не достигнем правильной позиции. Как только мы нашли правильную позицию, мы можем вставить новый узел, изменив свойство next предыдущего узла, чтобы оно ссылалось на новый узел, и свойство next нового узла, чтобы оно ссылалось на следующий узел в последовательности.
Вот пример вставки нового узла в связанный список в JavaScript:
// Create the new node to insert
const newNode = { value: 4, next: null };
// Find the correct position to insert the new node
let currentNode = linkedList[0];
let previousNode = null;
while (currentNode.value < newNode.value) {
previousNode = currentNode;
currentNode = currentNode.next;
}
// Insert the new node into the linked list
newNode.next = currentNode;
previousNode.next = newNode;
// Add the new node to the array representing the linked list
linkedList.push(newNode);
В приведенном выше примере мы создаем новый узел для вставки в связанный список. Затем мы просматриваем связанный список, начиная с головы, пока не найдем правильную позицию для вставки нового узла. Как только мы нашли правильную позицию, мы вставляем новый узел, изменяя свойство next предыдущего узла для ссылки на новый узел и свойство next нового узла для ссылки на следующий узел в последовательности. Наконец, мы добавляем новый узел в массив, представляющий связанный список.
Чтобы удалить узел из связанного списка, нам сначала нужно найти правильную позицию удаляемого узла. Обычно это делается путем обхода связанного списка, начиная с головы и переходя от одного узла к другому, пока мы не достигнем правильной позиции. Как только мы нашли правильную позицию, мы можем удалить узел, изменив свойство next предыдущего узла, чтобы он ссылался на следующий узел в последовательности, пропуская удаляемый узел.
Вот пример удаления узла из связанного списка в JavaScript:
// Find the correct position of the node to delete
let currentNode = linkedList[0];
let previousNode = null;
while (currentNode.value !== 2) {
previousNode = currentNode;
currentNode = currentNode.next;
}
// Delete the node from the linked list
previousNode.next = currentNode.next;
// Remove the node from the array representing the linked list
const index = linkedList.indexOf(currentNode);
linkedList.splice(index, 1);
В приведенном выше примере мы просматриваем связанный список, начиная с головы, пока не найдем правильную позицию удаляемого узла. Как только мы нашли правильную позицию, мы удаляем узел, изменяя свойство next предыдущего узла, чтобы он ссылался на следующий узел в последовательности, пропуская удаляемый узел. Наконец, мы удаляем узел из массива, представляющего связанный список.
