Я собираюсь рассказать, как составить односвязный список в машинописном тексте. Сначала я покажу вам код, а затем объясню, как он работает (с картинками).

Если вы хотите просто взять этот код и использовать его, вам может потребоваться опустить «экспорт» перед каждым классом (узел, LinkedList). Я настроил его таким образом для моей среды в моем репозитории машинописных текстов, но он вам не понадобится, чтобы поэкспериментировать со списком в одном файле.

export class node {
value:number;
next:node|null;
constructor(value:number) {
this.value = value;
this.next = null;
}
}
export class LinkedList {
head:node|null = null
constructor() {
this.head = null;
}
appendNode:Function = (value:number) => {
if (this.head == null) {
this.head = new node(value)
} else if (this.head.next == null) {
this.head.next = new node(value)
} else {
//    finding the tail
let a:node|null = this.head.next
while (a.next) {
a = a.next
}
a.next = new node(value)
}
}
deletePosition:Function = (position:number) => {
if (this.head == null) {
return "The list is empty"
} else if (position == 1) {
this.head = this.head.next
} else {
let counter:number = 2
let a:null|node = this.head
while (a.next && counter != position) {
a = a.next
counter += 1
}
a.next = a.next.next
}
}
putAllValuesInArray:Function = () => {
let output: any[] = []
if (this.head == null) {
return "The list is empty"
} else if (this.head.next == null) {
return this.head.value
} else {
let c:node|null = this.head.next
while (c.next) {
output.push(c.value);
c = c.next;
}
output.push(c.value)
return output
}
}
findTail:Function = () => {
if (this.head== null) {
return "The list is empty"
} else if (this.head.next == null) {
return this.head
} else {
let a:node|null = this.head.next
while (a.next) {
a = a.next
}
return a
}
}
}

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

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

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

class node {
}
class LinkedList {
}

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

Итак, мы знаем, что у нас будет ряд объектов, содержащих какое-то значение и другой атрибут, указывающий на следующий объект в списке. Конец списка будет указывать на нуль.

Кроме того, это не обязательно, но, как правило, хорошая практика - отслеживать заголовок списка. Это упростит реализацию некоторых функций из списка.

class node {
value: number
next: node | null
constructor (value:number) {
this.value = value;
this.next = null
}
}
class linkedList {
head: node | null
constrctor () {
this.head = null
}
}

По сути, каждый следующий атрибут в узле всегда будет либо нулевым, либо другим узлом.

Каждое значение заголовка каждого списка может быть только нулевым или другим узлом.

Нет смысла (прямо сейчас) создавать узел, не имеющий значения.

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

Со списками можно делать множество вещей, но минимальная функциональность структуры данных - это добавление или удаление значений. Так что это все, что я расскажу на сегодня. В моем списке есть некоторые дополнительные функции, такие как «поместить все значения в массив», только потому, что это был простой способ увидеть все значения по порядку и дважды проверить правильность работы моих функций добавления / удаления.

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

Перейдем к добавлению узла.

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

Для этого мы просто указываем это:

if (this.head == null) {
this.head = new node(value)
}

в нашей функции добавления узла.

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

else {
// finding the tail
let a:node|null = this.head.next
while (a.next) {
a = a.next
}
// assigning the new node to tail.next
a.next = new node(value)
}

Простой способ отслеживать вещи (и вы должны признать это обычным инструментом) - это установить трекерную переменную как нечто, а затем изменить эту трекерную переменную во время цикла.

В этом случае я говорю, что переменная «a» будет либо узлом, либо нулем. Пока a.next все еще является узлом, пусть «a» будет назначен следующему узлу в списке. Как только a.next станет нулевым, мы узнаем, что «a» был назначен последнему узлу в списке. (обратитесь к нашему рисунку. Последний узел node.next всегда указывает на «null» в простом односвязном списке.) Поскольку «a» является концом списка, а a.next имеет значение null, цикл прервется, и программа продолжить оценку последнего оператора в блоке.

Последний оператор в блоке назначит новый узел a.next.

Бум, наш новый узел был добавлен, и это было даже не так сложно.

Удаление узла

Угадай, что? По моему опыту, добавление узлов обычно является более простой половиной реализации структуры данных.

Итак, давайте поговорим об удалении узла. При удалении узла вы можете проверить множество вещей. Вы можете удалить по значению или по позиции или даже удалить диапазон узлов. Неважно. Основная концепция, используемая для удаления рассматриваемого узла (ов), всегда будет одинаковой.

Этот процесс будет включать изменение указателя с предыдущего узла на следующий узел. Снова давайте вернемся к нашему рисунку, потому что это упростит понимание.

Не имеет особого значения, что удаляемый узел все еще имеет атрибут «следующий», который указывает на следующий узел, потому что, когда мы перебираем список, атрибут «следующий» предыдущего узла просто пропустит удаляемый узел, таким образом отображая его. недоступен.

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

Во-первых, нам нужно увидеть, пуст список или нет.

if (this.head == null) {
return "The list is empty"
}

Затем, если мы удаляем первый узел в списке, мы просто следуем нашей логике изменения указателя, сделав так, чтобы заголовок списка был на самом деле 2-м узлом, тем самым делая 1-й узел недоступным.

else if (position == 1) {
this.head = this.head.next
}

Наконец, перебирайте список до тех пор, пока мы не окажемся в нужной позиции, а затем измените относительные атрибуты, чтобы они указывали на нужные нам узлы, чтобы сделать удаленный узел недоступным.

else {
let counter:number = 2
let a:null|node = this.head
while (a.next && counter != position) {
a = a.next
counter += 1
}
if (counter == position) {
a.next = a.next.next
}
}

По сути, мы перебираем список и используем ту же переменную трекера «a», что и раньше. Кроме того, я использую переменную «счетчик», чтобы отслеживать нашу позицию в списке.

По сути, этот цикл while будет повторяться до тех пор, пока не достигнет конца списка или пока не найдет искомую позицию.

Что-то, что может показаться немного запутанным в этом, заключается в том, что мы на самом деле проверяем положение следующего узла во время итерации, потому что для изменения соответствующих атрибутов next нам нужно каким-то образом найти предыдущий узел. Самый простой способ добиться этого - поиграть с начальным значением «счетчика», чтобы цикл while сломал один узел перед целевым узлом.

Мы можем протестировать наш список, чтобы убедиться, что он работает правильно, введя несколько вызовов функций и просмотрев результат в нашей командной строке.

newList.appendNode(3);
newList.appendNode(4);
newList.appendNode(8);
newList.appendNode(9);
newList.appendNode(2);
newList.appendNode(4);
newList.appendNode(7);
console.log(newList.head) //=> node { value: 3, next: node { value: 4, next: node { value: 8, next: [node] }}}
console.log(newList.putAllValuesInArray()) // => [ 3,4,8,9,2,4,7 ]
newList.deletePosition(3)
console.log(newList.putAllValuesInArray()) // => [ 3,4,9,2,4,7 ]
newList.deletePosition(5)
console.log(newList.putAllValuesInArray()) // => [ 3,4,8,9,4,7 ]

Здесь я заполняю свой список некоторыми значениями. Затем я передаю это в console.log список, чтобы я мог увидеть, правильна ли базовая структура. Затем я вызываю функцию удаления и использую свою функцию массива, чтобы убедиться, что она удалила правильные позиции. (помните, что мои позиции начинаются с 1, поэтому не предполагайте, что это то же самое, что и индексы массива)

Наша основная структура списка кажется правильной.

И, похоже, удаляет позицию, которую мы хотим удалить. Третья позиция в списке - «8», а пятая позиция после удаления восьмерки - вторая 4.

Это все на сегодня. Имейте в виду, что этот список является чисто функциональным (и притом минимальным). Его можно довольно легко сломать, если вы умны, но этого должно быть достаточно, чтобы вы начали.