В этой статье мы реализуем связанный список с помощью функций javascript. Итак, что такое связанный список? Это линейная структура данных, в которой данные не хранятся в непрерывных ячейках памяти, а элементы связаны с помощью поля ссылки.
Как видите, элементы связаны друг с другом с помощью стрелок, обозначающих ссылку. Элементы связанного списка называются узлами, поэтому мы также можем сказать, что все узлы связаны указателями и именно так узлы организованы в последовательность. Первый узел называется головкой. Если связанный список пуст, то значение заголовка равно NULL. Последний узел связанного списка имеет NULL в качестве ссылки, что означает отсутствие следующего узла. Односвязный список состоит из двух частей:
- Данные (значение узла)
- Далее (ссылка на следующий узел)
Преимущества
- Вы можете динамически вставлять данные в связанный список без предварительного объявления размера и выделения памяти.
- Операции вставки и удаления в связанном списке намного проще, чем с массивом, поскольку в отличие от массива нам не нужно перемещать все элементы за вставленные или удаленные элементы.
Недостатки
- Дополнительное пространство памяти необходимо для хранения ссылки на следующий узел.
- Произвольный доступ к элементам не допускается. Мы должны обращаться к элементам последовательно, начиная с первого узла. Таким образом, мы не можем эффективно выполнять двоичный поиск по связанным спискам с его реализацией по умолчанию.
Реализация связного списка с использованием функций Javascript -
В этом разделе мы реализуем следующие функции при разработке односвязного списка в javascript.
get(index): получить значение узла по данному индексу в связанном списке.addAtHead(value): добавьте узел с значением в качестве данных перед первым узлом связанного списка.addAtTail(value): добавить узел со значением значение в конец связанного списка.addAtIndex(index, value): добавить узел со значением value по данному индексу связанного списка.deleteAtIndex(index): удалить узел по данному индексу в связанном списке.
Начнем с функции MyLinkedList. Эта функция содержит другую функцию getNewNode, которая создает новый узел, используя значение из аргументов, и возвращает вновь созданный узел с ссылкой, инициализированный как NULL. Мы хотим сохранить в памяти первую запись (заголовок) и размер списка.
var MyLinkedList = function() {
this.getNewNode = value => {
return { value, next: null };
};
this.head = null;
this.length = 0;
};
get (индекс)
Этот метод возвращает -1, если index недействителен. Если index действителен, мы будем просматривать связанный список, начиная с заголовка. Для этого мы будем использовать цикл while, который продолжается до тех пор, пока не будет достигнут индекс, и вернет значение узла.
MyLinkedList.prototype.get = function(index) {
let head = this.head;
let i = 0;
if (index < 0 || index >= this.length) {
return -1;
}
while (head.next) {
if (i === index) {
break;
}
head = head.next;
i++;
}
return head.value;
};
addAtHead (значение)
Этот метод создает новый узел и с переданным значением value добавляет его в первую позицию связанного списка.
- Инициализируйте новый узел с помощью значения.
- Если голова отсутствует (когда связанный список пуст), мы назначаем узел на голову.
- Если заголовок присутствует, присвойте исходный головной узел следующему (ссылке) нового узла.
- Назначьте новый узел заголовку.
- Увеличьте длину на 1.
MyLinkedList.prototype.addAtHead = function(value) {
const newNode = this.getNewNode(value);
if (this.head) {
newNode.next = this.head;
}
this.head = newNode;
this.length++;
};
Этот метод четко объясняет, насколько простой и менее затратной является операция вставки связанного списка, поскольку, в отличие от массива, нам не нужно перемещать все элементы за вставленный элемент.
addAtTail (значение)
Этот метод создает новый узел с переданным значением и добавляет его в связанный список.
- Проверим, есть ли голова. Если нет, мы можем напрямую вызвать addAtHead (value) или инициализировать новый узел и назначить его заголовку.
- Если заголовок существует, мы будем перемещаться по списку, начиная с начала (заголовок), пока next не станет NULL (т.е. пока мы не дойдем до последнего узла связанного списка. следующая ссылка NULL). Когда мы дойдем до последнего узла, мы инициализируем новый узел с переданным значением и присвоим его следующему исходному последнему узлу.
- Увеличьте длину на 1.
MyLinkedList.prototype.addAtTail = function(value) {
if (!this.head) {
const newNode = this.getNewNode(value);
this.head = newNode;
this.length++;
return;
}
let head = this.head;
while (head.next) {
head = head.next;
}
const newNode = this.node(value);
head.next = newNode;
this.length++;
};
addAtIndex (значение, индекс)
Этот метод создает новый узел с аргументом value и добавляет его к переданному индексу связанного списка.
- Инициализируйте новый узел с помощью значения.
- Если index недействителен, мы не выполняем вставку. Если index равен 0 или заголовок не существует (т.е. связанный список пуст), мы просто вызываем функцию addAtHead. Если index равен длине связанного списка, мы просто вызываем функцию addAtTail, поскольку узел будет добавлен в конец связанного списка.
- В остальных случаях мы будем перемещаться до index. В (индекс -1) мы сохраним предыдущий узел. В index мы получаем доступ к исходному или текущему элементу next (reference) и назначаем его в качестве ссылки на новый узел. Теперь мы добавляем новый узел к следующему (справочному) предыдущему узлу.
- Увеличьте длину на 1.
MyLinkedList.prototype.addAtIndex = function(index, value) {
if (index < 0 || index > this.length) {
return;
} else if (index === 0 || !this.head) {
this.addAtHead(value);
return;
} else if (index === this.length) {
this.addAtTail(value);
return;
}
let head = this.head;
let i = 0;
let prev = null;
while (head.next || index === this.length - 1) {
if (i === index - 1) {
prev = head;
} else if (i === index) {
const newNode = this.getNewNode(value);
newNode.next = head;
prev.next = newNode;
this.length++;
break;
}
head = head.next;
i++;
}
};
deleteAtIndex (индекс)
Эта функция удаляет узел по переданному индексу.
- Если index равен 0, мы получаем доступ к узлу с 1-го index и назначаем его заголовку.
- Если index равен длине связанного списка, мы проходим до индекса (length -1) и присваиваем NULL ссылке (length -1) указатель.
- В остальных случаях мы просматриваем связанный список до index. В index мы назначаем next (reference) текущего узла (index -1) узла next (ссылка)
- Уменьшите длину на 1.
MyLinkedList.prototype.deleteAtIndex = function(index) {
let head = this.head;
let i = 0;
let prev = null;
if (index === 0) {
while (head.next) {
if (i === index + 1) {
this.head = head;
this.length--;
break;
}
head = head.next;
i++;
}
} else if (index === this.length - 1) {
while (head.next) {
if (i === this.length - 2) {
head.next = null;
this.length--;
break;
}
head = head.next;
i++;
}
} else {
while (head.next) {
if (i === index - 1) {
prev = head;
}
if (i === index) {
prev.next = head.next;
this.length--;
break;
}
head = head.next;
i++;
}
}
};
Заключение
После создания собственного связанного списка в javascript вы должны лучше понять плюсы и минусы структуры данных связанного списка. В то время как операции вставки и удаления в связанном списке проще, доступ к случайным элементам - дорогостоящая операция.
Хотя мы можем использовать массивы для большинства наших операций, использование связанного списка может быть очень полезным при реализации других структур данных, таких как графы, стеки и очереди. Одним из реальных примеров, где связанный список может использоваться в реальном мире, является программа просмотра фотографий для связи между предыдущими и следующими фотографиями.
Вот и все!
Чтобы увидеть полный код нашей реализации, ознакомьтесь с этой сутью GitHub.
Я надеюсь, что вы нашли эту реализацию полезной для разработки одного из фундаментальных типов данных информатики, и если у вас есть какие-либо вопросы или отзывы, не стесняйтесь Оставить комментарий.
