Серия в связанных списках

Почему связанный список

Краткое руководство по преимуществам использования связанных списков

Привет, я недавно просматривал структуры данных и наткнулся на одну из наиболее известных - связанный список. Поскольку для доступа к любому заданному элементу в списке вам нужно будет перебрать весь список до точки, где находится ваш элемент, и для создания связанного списка вам нужно создать его с нуля, а также создать все методы, которые соглашаться с этим, поначалу казалось бы бессмысленным. В большинстве случаев да, простой массив, вероятно, мог бы выполнить эту работу так же хорошо, если не быстрее, однако бывают случаи, когда связанный список может сэкономить вам много времени и пространства.

Во-первых, одна из замечательных особенностей массивов заключается в том, что каждый элемент индексируется. В большинстве случаев это нам очень помогает, когда при доступе к элементу и последующем его редактировании мы можем просто вызвать его по его индексу. Однако в случае изменения порядка в массиве потребуется изменить индекс каждого затронутого элемента.

Например, давайте посмотрим на массив.

let arr = [ "arrays" , "are" , "always" , "indexed" ]

Javascript индексирует каждый элемент в массиве, поэтому мы можем вызывать по индексу.

arr[0] // "arrays"
arr[1] // "are"
arr[2] // "always"
arr[3] // "indexed"

Теперь, если мы протолкнем новый элемент до конца, это не имеет большого значения, но что, если мы хотим добавить элемент в начало массива?

arr.unshift("Javascript")

arr[0] // "Javascript"
arr[1] // "arrays"
arr[2] // "are"
arr[3] // "always"
arr[4] // "indexed"

Каждому элементу должен был быть присвоен новый индекс, например, слово «всегда» достигается в arr[3] вместо arr[2], короче говоря, вместо использования одного вычисления (O¹), просто добавляя один элемент, наш код должен был пройти через и изменить каждый элемент (O ^ n) ?? !!

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

- - - - - - - - - - - - Вход в связанные списки - - - - - - - - - -

Связанный список - это то, на что он похож - связанный список - каждый элемент или узел в этом случае связан с тем, что находится после него (или, в случае двусвязного списка, с тем, который находится до и после него). Итак, чтобы получить доступ к заданному элементу внутри списка, вам нужно будет пройти по всему списку, но если вы хотите добавить в начало или конец, если на то пошло, потребуется одно вычисление (O¹).

Каждый узел подключается только через следующий за ним

Итак, просто повторим два основных преимущества.

  1. Сложность времени - при вставке или удалении элементов
  2. Сложность пространства - отсутствие прикрепленного индекса требует меньше памяти. (Обратите внимание, что, поскольку каждый узел содержит указатель на второй узел, сами узлы занимают больше памяти, чем элемент в массиве.)

Дело в том, что связанные списки заключаются в том, что Javascript не просто передает их вам как массив, вы должны создать его для себя, не только для этого, но и сами должны создать методы. В моем следующем блоге я расскажу, как создать простой односвязный список и наиболее часто используемые методы.

А пока наслаждайтесь кодированием!



Односвязный список - Pop and Shift
Обзор методов удаления узла из начала или конца связанного списка. medium. com



Первоначально опубликовано на https://www.bpThreadts.com.