Реализация LinkedList в Javascript

Опубликовано: 5 Января, 2022

В этой статье мы реализуем структуру данных LinkedList в Javascript. LinkedList - это динамическая структура данных, так как мы можем легко добавлять или удалять элементы, и она может даже увеличиваться по мере необходимости. Как и массивы, связанные списки хранят элементы последовательно, но не хранят элементы непрерывно, как массив.
Теперь давайте посмотрим на пример узла связанного списка:

Javascript

// User defined class node
class Node {
// constructor
constructor(element)
{
this .element = element;
this .next = null
}
}

Как и в приведенном выше коде, мы определяем класс Node, имеющий два свойства: element и next . Элемент содержит данные узла, а следующий содержит указатель на следующий узел, который инициализируется нулевым значением.
Теперь давайте посмотрим на реализацию класса Linked List:

Javascript

// linkedlist class
class LinkedList {
constructor()
{
this .head = null ;
this .size = 0;
}
// functions to be implemented
// add(element)
// insertAt(element, location)
// removeFrom(location)
// removeElement(element)
// Helper Methods
// isEmpty
// size_Of_List
// PrintList
}

В приведенном выше примере показан класс связанного списка с конструктором и списком реализуемых методов. Класс связанного списка имеет два свойства: то есть заголовок и размер , где заголовок хранит первый узел списка, а размер указывает количество узлов в списке.
Реализуем каждую из этих функций:

1. add (element) - добавляет элемент в конец списка.

Javascript

// adds an element at the end
// of list
add(element)
{
// creates a new node
var node = new Node(element);
// to store current node
var current;
// if list is Empty add the
// element and make it head
if ( this .head == null )
this .head = node;
else {
current = this .head;
// iterate to the end of the
// list
while (current.next) {
current = current.next;
}
// add node
current.next = node;
}
this .size++;
}

Чтобы добавить элемент в конец списка, мы учитываем следующее:

  • Если список пуст, добавьте элемент, и он будет заголовком
  • Если список не пуст, выполните итерацию до конца списка и добавьте элемент в конец списка.

2. insertAt (element, index) - вставляет элемент по указанному индексу в список.

Javascript

// insert element at the position index
// of the list
insertAt(element, index)
{
if (index < 0 || index > this .size)
return console.log( "Please enter a valid index." );
else {
// creates a new node
var node = new Node(element);
var curr, prev;
curr = this .head;
// add the element to the
// first index
if (index == 0) {
node.next = this .head;
this .head = node;
} else {
curr = this .head;
var it = 0;
// iterate over the list to find
// the position to insert
while (it < index) {
it++;
prev = curr;
curr = curr.next;
}
// adding an element
node.next = curr;
prev.next = node;
}
this .size++;
}
}

Чтобы добавить элемент в конец списка, мы учитываем три следующих условия:

  • если индекс равен нулю, мы добавляем элемент в начало списка и делаем его заголовком
  • Если индекс является последней позицией списка, мы добавляем элемент в конец списка
  • если индекс находится между 0 или размером - 1, мы переходим к индексу и добавляем элемент по этому индексу

3. removeFrom (index) - удаляет и возвращает элемент из списка по указанному индексу.

Javascript



// removes an element from the
// specified location
removeFrom(index)
{
if (index < 0 || index >= this .size)
return console.log( "Please Enter a valid index" );
else {
var curr, prev, it = 0;
curr = this .head;
prev = curr;
// deleting first element
if (index === 0) {
this .head = curr.next;
} else {
// iterate over the list to the
// position to removce an element
while (it < index) {
it++;
prev = curr;
curr = curr.next;
}
// remove the element
prev.next = curr.next;
}
this .size--;
// return the remove element
return curr.element;
}
}

Чтобы удалить элемент из списка, мы учитываем три условия:

  • Если индекс равен 0, мы удаляем заголовок и делаем следующий узел заголовком списка.
  • если индекс равен size - 1, то мы удаляем последний элемент из списка и делаем последний элемент prev
  • если он находится в диапазоне от 0 до size - 1, мы удаляем элемент, используя prev и текущий узел

4. removeElement (element) - этот метод удаляет элемент из списка. Он возвращает удаленный элемент или, если он не найден, возвращает -1.

Javascript

// removes a given element from the
// list
removeElement(element)
{
var current = this .head;
var prev = null ;
// iterate over the list
while (current != null ) {
// comparing element with current
// element if found then remove the
// and return true
if (current.element === element) {
if (prev == null ) {
this .head = current.next;
} else {
prev.next = current.next;
}
this .size--;
return current.element;
}
prev = current;
current = current.next;
}
return -1;
}

Вышеупомянутый метод - это просто модификация removeFrom (index) , поскольку он ищет элемент и удаляет его, а не удаляет его из указанного места.

Вспомогательные методы

Объявим несколько вспомогательных методов, которые пригодятся при работе с LinkedList.

1. indexOf (element) - возвращает индекс данного элемента, если элемент находится в списке.

Javascript

// finds the index of element
indexOf(element)
{
var count = 0;
var current = this .head;
// iterae over the list
while (current != null ) {
// compare each element of the list
// with given element
if (current.element === element)
count; return
count++;
current = current.next;
}
// not found
return -1;
}

В этом методе мы перебираем список, чтобы найти индекс элемента. Если его нет в списке, вместо этого возвращается -1.

2. isEmpty () - возвращает истину, если список пуст.

Javascript

// checks the list for empty
isEmpty()
{
return this .size == 0;
}

В этом методе мы проверяем свойство размера класса LinkedList , и если оно равно нулю, то список пуст.

3. size_of_list () - возвращает размер списка

Javascript

// gives the size of the list
size_of_list()
{
console.log( this .size);
}

3. printList () - печатает содержимое списка.

Javascript

// prints the list items
printList()
{
var curr = this .head;
var str = "" ;
while (curr) {
str += curr.element + " " ;
curr = curr.next;
}
console.log(str);
}

В этом методе мы перебираем весь список, объединяем элементы каждого узла и печатаем его.

Примечание. При необходимости в классе LinkedList могут быть объявлены различные вспомогательные методы.

Реализация

Теперь давайте воспользуемся классом LinkedList и его различными методами, описанными выше.

Javascript

// creating an object for the
// Linkedlist class
var ll = new LinkedList();
// testing isEmpty on an empty list
// returns true
console.log(ll.isEmpty());
// adding element to the list
ll.add(10);
// prints 10
ll.printList();
// returns 1
console.log(ll.size_of_list());
// adding more elements to the list
ll.add(20);
ll.add(30);
ll.add(40);
ll.add(50);
// returns 10 20 30 40 50
ll.printList();
// prints 50 from the list
console.log( "is element removed ?" + ll.removeElement(50));
// prints 10 20 30 40
ll.printList();
// returns 3
console.log( "Index of 40 " + ll.indexOf(40));
// insert 60 at second position
// ll contains 10 20 60 30 40
ll.insertAt(60, 2);
ll.printList();
// returns false
console.log( "is List Empty ? " + ll.isEmpty());
// remove 3rd element from the list
console.log(ll.removeFrom(3));
// prints 10 20 60 40
ll.printList();

Полный код:

Javascript

class Node {
// constructor
constructor(element) {
this .element = element;
this .next = null
}
}
// linkedlist class
class LinkedList {
constructor() {
this .head = null ;
this .size = 0;
}
// adds an element at the end
// of list
add(element) {
// creates a new node
var node = new Node(element);
// to store current node
var current;
// if list is Empty add the
// element and make it head
if ( this .head == null )
this .head = node;
else {
current = this .head;
// iterate to the end of the
// list
while (current.next) {
current = current.next;
}
// add node
current.next = node;
}
this .size++;
}
// insert element at the position index
// of the list
insertAt(element, index) {
if (index < 0 || index > this .size)
return console.log( "Please enter a valid index." );
else {
// creates a new node
var node = new Node(element);
var curr, prev;
curr = this .head;
// add the element to the
// first index
if (index == 0) {
node.next = this .head;
this .head = node;
} else {
curr = this .head;
var it = 0;
// iterate over the list to find
// the position to insert
while (it < index) {
it++;
prev = curr;
curr = curr.next;
}
// adding an element
node.next = curr;
prev.next = node;
}
this .size++;
}
}
// removes an element from the
// specified location
removeFrom(index) {
if (index < 0 || index >= this .size)
return console.log( "Please Enter a valid index" );
else {
var curr, prev, it = 0;
curr = this .head;
prev = curr;
// deleting first element
if (index === 0) {
this .head = curr.next;
} else {
// iterate over the list to the
// position to removce an element
while (it < index) {
it++;
prev = curr;
curr = curr.next;
}
// remove the element
prev.next = curr.next;
}
this .size--;
// return the remove element
return curr.element;
}
}
// removes a given element from the
// list
removeElement(element) {
var current = this .head;
var prev = null ;
// iterate over the list
while (current != null ) {
// comparing element with current
// element if found then remove the
// and return true
if (current.element === element) {
if (prev == null ) {
this .head = current.next;
} else {
prev.next = current.next;
}
this .size--;
return current.element;
}
prev = current;
current = current.next;
}
return -1;
}
// finds the index of element
indexOf(element) {
var count = 0;
var current = this .head;
// iterae over the list
while (current != null ) {
// compare each element of the list
// with given element
if (current.element === element)
count; return
count++;
current = current.next;
}
// not found
return -1;
}
// checks the list for empty
isEmpty() {
return this .size == 0;
}
// gives the size of the list
size_of_list() {
console.log( this .size);
}
// prints the list items
printList() {
var curr = this .head;
var str = "" ;
while (curr) {
str += curr.element + " " ;
curr = curr.next;
}
console.log(str);
}
}
// creating an object for the
// Linkedlist class
var ll = new LinkedLis
JavaScript Статьи

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Онлайн-обменники: быстрый и удобный способ конвертации активов в современном мире
17 Апреля, 2024
Лучшие онлайн-курсы по WordPress: рейтинг 2024
29 Марта, 2024
Для кого буду полезны услуги SMS-центра
24 Марта, 2024
Что такое экспертиза исходного кода и как ее проводят?
3 Марта, 2024
Как добавить деньги на счет аккаунта Steam через криптовалюту
20 Февраля, 2024
Заказать докторскую диссертацию на заказ
30 Января, 2024
Что такое тернарный оператор?
23 Января, 2024
Купить лайки в ВК: зачем, сколько и где
19 Января, 2024