Связанный список
Ранее мы обсуждали, как использоватькуча,очередьДля хранения данных они фактическисписокОдной из структур данных базовых хранимых данных является массив.
Но массивы не всегда являются лучшей структурой данных, потому что во многих языках программирования массивы имеют фиксированную длину и очень сложно добавлять новые элементы, если массив уже заполнен данными. Более того, для операций удаления и добавления массива другие элементы в массиве обычно нужно сдвигать вперед или назад, а эти операции тоже весьма громоздки.
Однако массивы в JS не имеют вышеперечисленных проблем, в основном потому, что они реализованы в виде объектов, но по сравнению с другими языками (такими как C или Java) он намного менее эффективен.
В настоящее время мы можем рассмотреть возможность использования связанного списка (Linked-list) для его замены, помимо произвольного доступа к данным, связанный список можно использовать практически в любой ситуации, где можно использовать одномерный массив. Если вам случится использовать язык высокого уровня, такой как C или Java, вы обнаружите, что связанные списки работают намного лучше, чем массивы.
На самом деле существует много типов связанных списков: односвязные списки, двусвязные списки, односвязные круговые списки и двусвязные списки.Затем мы реализуем односвязный список на основе объектов, поскольку он наиболее широко используется.
Определение связанного списка
Прежде всего, чтобы реализовать связанный список, мы сначала разбираемся в некоторых основных вещах о связанных списках, потому что это очень важно!
Связный список — это набор узлов, каждый из которых использует ссылку на объект, чтобы указать на его следующий узел. Ссылка на другой узел называется цепочкой. Ниже я нарисовал простую схему структуры ссылок для вашего удобства.
Среди них data содержит данные, а next содержит ссылку на следующий связанный список. На изображении выше мы говорим, что данные2 следуют за данными1, а не что данные2 являются вторым элементом в связанном списке. На приведенном выше рисунке стоит отметить, что мы указываем хвостовой элемент связанного списка на нулевой узел, указывая позицию, где заканчивается ссылка.
Поскольку трудно определить начальную точку связанного списка, многие реализации связанных списков добавляют специальный узел вверху связанного списка, называемыйголовной узел, который представляет заголовок связанного списка. После преобразования связанный список становится следующим:
к связанному спискувставить узелЭффективность очень высока.Необходимо модифицировать узел (предшественник) перед ним, чтобы он указывал на вновь добавленный узел, а новый узел указывал на узел, на который указывает исходный узел-предшественник. Ниже я использую рисунок, чтобы продемонстрировать, как вставить узел data4 после узла data2.
Точно так же удалить узел из связанного списка очень просто. Просто укажите узел-предшественник узла, который нужно удалить, на узел, который нужно удалить, и в то же время укажите узел, который нужно удалить, на ноль, после чего узел будет успешно удален. Ниже мы используем рисунок, чтобы продемонстрировать, как удалить узел data4 из связанного списка.
Дизайн связанного списка
Мы разрабатываем связанный список так, чтобы он содержал два класса: один — это класс Node для представления узлов, а другой — класс LinkedList, обеспечивающий некоторые операции, такие как вставка и удаление узлов.
Класс узла
Класс Node содержит два атрибута: element используется для сохранения данных на узле, next используется для сохранения ссылки на следующий узел, конкретная реализация выглядит следующим образом:
//节点
function Node(element) {
this.element = element; //当前节点的元素
this.next = null; //下一个节点链接
}
Класс LinkedList
Класс LinkedList предоставляет методы для управления связанным списком, включая вставку и удаление узлов, поиск заданного значения и т. д. Стоит отметить, что у него есть только одно свойство — использовать объект Node для хранения головного узла связанного списка.
Его конструктор реализован следующим образом:
//链表类
function LList () {
this.head = new Node( 'head' ); //头节点
this.find = find; //查找节点
this.insert = insert; //插入节点
this.remove = remove; //删除节点
this.findPrev = findPrev; //查找前一个节点
this.display = display; //显示链表
}
Свойство next головного узла инициализируется значением null , когда вставляется новый элемент, next будет указывать на новый элемент.
Далее, давайте взглянем на реализацию конкретных методов.
вставка: вставить узел в связанный список
Мы сначала анализируем и анализируем метод вставки, Чтобы вставить узел, мы должны указать, какой узел вставлять до или после. Давайте сначала посмотрим, как вставить узел после известного узла.
Чтобы вставить новый узел после известного узла, нам сначала нужно найти узел, для этого нам нужен метод find для обхода связанного списка для поиска заданных данных. Если он найден, метод возвращает узел, содержащий данные. Итак, давайте сначала реализуем метод find.
найти: найти данный узел
//查找给定节点
function find ( item ) {
var currNode = this.head;
while ( currNode.element != item ){
currNode = currNode.next;
}
return currNode;
}
Метод find также показывает, как перемещаться по связанному списку. Сначала создайте новый узел, назначьте головной узел связанного списка вновь созданному узлу, а затем выполните цикл по связанному списку.Если атрибут элемента текущего узла не соответствует информации, которую мы ищем, переместите текущий к следующему узлу. Если поиск выполнен успешно, метод возвращает узел, содержащий данные, в противном случае он возвращает значение null.
Как только узел найден, мы можем вставить новый узел в связанный список, установить следующий атрибут нового узла в значение, соответствующее следующему атрибуту следующего узла, а затем установить следующий атрибут следующего узла в точку к новому узлу Конкретная реализация выглядит следующим образом:
//插入节点
function insert ( newElement , item ) {
var newNode = new Node( newElement );
var currNode = this.find( item );
newNode.next = currNode.next;
currNode.next = newNode;
}
Теперь мы можем протестировать наш связанный список. Подождите, давайте сначала определим метод отображения для отображения элементов связанного списка, иначе как мы узнаем, что это правильно?
display: отображать связанный список
//显示链表元素
function display () {
var currNode = this.head;
while ( !(currNode.next == null) ){
console.log( currNode.next.element );
currNode = currNode.next;
}
}
Принцип реализации такой же, как и выше, назначьте головной узел новой переменной, затем зациклите связанный список и остановите цикл, пока следующий атрибут текущего узла не станет нулевым, мы просто распечатываем данные каждого узла во время петля.
var fruits = new LList();
fruits.insert('Apple' , 'head');
fruits.insert('Banana' , 'Apple');
fruits.insert('Pear' , 'Banana');
console.log(fruits.display()); // Apple
// Banana
// Pear
удалить: удалить узел из связанного списка
从链表中删除节点时，我们先要找个待删除节点的前一个节点，找到后，我们修改它的 next 属性，使其不在指向待删除的节点，而是待删除节点的下一个节点。那么，我们就得需要定义一个 findPrevious 方法遍历链表，检查每一个节点的下一个节点是否存储待删除的数据。如果找到，返回该节点，这样就可以修改它的 next 属性了。 findPrevious 的实现如下：
//查找带删除节点的前一个节点
function findPrev( item ) {
var currNode = this.head;
while ( !( currNode.next == null) && ( currNode.next.element != item )){
currNode = currNode.next;
}
return currNode;
}
Таким образом, реализация метода удаления легко решается.
//删除节点
function remove ( item ) {
var prevNode = this.findPrev( item );
if( !( prevNode.next == null ) ){
prevNode.next = prevNode.next.next;
}
}
Давайте напишем тестовую программу для проверки метода удаления:
// 接着上面的代码，我们再添加一个水果
fruits.insert('Grape' , 'Pear');
console.log(fruits.display()); // Apple
// Banana
// Pear
// Grape
// 我们把香蕉吃掉
fruits.remove('Banana');
console.log(fruits.display()); // Apple
// Pear
// Grape
Здорово! Успех, теперь вы можете реализовать базовый односвязный список.
Двусвязный список
Хотя переход по связанному списку от головного узла связанного списка прост, не так просто перейти от конца к началу. Мы можем добавить предыдущий атрибут к классу Node, чтобы указать его на ссылку предшествующего узла, таким образом сформировав двусвязный список, как показано ниже:
В настоящее время вставка узла в связанный список требует изменения предшественника и преемника узла, но эффективность удаления узла повышается, и больше нет необходимости искать узел-предшественник удаляемого узла.
Реализация двусвязного списка
Чтобы реализовать двусвязный список, вам сначала нужно добавить предыдущее свойство в класс Node:
//节点类
function Node(element) {
this.element = element; //当前节点的元素
this.next = null; //下一个节点链接
this.previous = null; //上一个节点链接
}
Метод вставки двусвязного списка похож на метод вставки односвязного списка, но для предыдущего свойства нового узла необходимо установить значение, указывающее на предшественника узла, который определяется следующим образом:
//插入节点
function insert ( newElement , item ) {
var newNode = new Node( newElement );
var currNode = this.find( item );
newNode.next = currNode.next;
newNode.previous = currNode;
currNode.next = newNode;
}
Метод удаления двусвязного списка более эффективен, чем односвязный: ему не нужно искать узел-предшественник, достаточно найти удаляемый узел, а затем следующий атрибут узла-предшественника указывает на преемника узла. удаляемый узел и устанавливает атрибут преемника предыдущего узла так, чтобы он указывал на удаляемый узел.Предшественник узла может быть. Определяется следующим образом:
//删除节点
function remove ( item ) {
var currNode = this.find ( item );
if( !( currNode.next == null ) ){
currNode.previous.next = currNode.next;
currNode.next.previous = currNode.previous;
currNode.next = null;
currNode.previous = null;
}
}
Есть также несколько методов для отображения связанного списка в обратном порядке, dispReverse, поиска последнего элемента связанного списка, findLast и т. д. Думаю, у вас уже есть идея.Здесь я даю код завершения базового двусвязного списка для вашего ссылка.
//节点
function Node(element) {
this.element = element; //当前节点的元素
this.next = null; //下一个节点链接
this.previous = null; //上一个节点链接
}
//链表类
function LList () {
this.head = new Node( 'head' );
this.find = find;
this.findLast = findLast;
this.insert = insert;
this.remove = remove;
this.display = display;
this.dispReverse = dispReverse;
}
//查找元素
function find ( item ) {
var currNode = this.head;
while ( currNode.element != item ){
currNode = currNode.next;
}
return currNode;
}
//查找链表中的最后一个元素
function findLast () {
var currNode = this.head;
while ( !( currNode.next == null )){
currNode = currNode.next;
}
return currNode;
}
//插入节点
function insert ( newElement , item ) {
var newNode = new Node( newElement );
var currNode = this.find( item );
newNode.next = currNode.next;
newNode.previous = currNode;
currNode.next = newNode;
}
//显示链表元素
function display () {
var currNode = this.head;
while ( !(currNode.next == null) ){
console.debug( currNode.next.element );
currNode = currNode.next;
}
}
//反向显示链表元素
function dispReverse () {
var currNode = this.findLast();
while ( !( currNode.previous == null )){
console.log( currNode.element );
currNode = currNode.previous;
}
}
//删除节点
function remove ( item ) {
var currNode = this.find ( item );
if( !( currNode.next == null ) ){
currNode.previous.next = currNode.next;
currNode.next.previous = currNode.previous;
currNode.next = null;
currNode.previous = null;
}
}
var fruits = new LList();
fruits.insert('Apple' , 'head');
fruits.insert('Banana' , 'Apple');
fruits.insert('Pear' , 'Banana');
fruits.insert('Grape' , 'Pear');
console.log( fruits.display() ); // Apple
// Banana
// Pear
// Grape
console.log( fruits.dispReverse() ); // Grape
// Pear
// Banana
// Apple
Круговой связанный список
Циклический связанный список похож на односвязный список, и типы узлов те же, единственное отличие состоит в том, что при создании циклического связанного списка пусть следующий атрибут его головного узла выполняет сам себя, то есть
head.next = head;
Это приведет к тому, что следующий атрибут каждого узла в связанном списке будет указывать на головной узел связанного списка.Другими словами, хвостовой узел связанного списка указывает на головной узел, образуя круговой связанный список, как показано на следующем рисунке:
Я думаю, вы уже поняли принцип. Циклический связанный список здесь, чтобы субсидировать код. Я верю, что вы можете сделать это самостоятельно!
На данный момент у нас есть относительно глубокое понимание связанного списка.Если мы хотим сделать наш связанный список более надежным, мы также можем использовать наше собственное мышление, чтобы добавить к связанному списку, например, переместить несколько узлов вперед, переместить несколько узлы назад, и отображение текущего узла. Ждите метод, давайте работать вместе!