Структуры данных. Связный список

Это краткий дополненный конспект части о связных списках в книге Гид по Computer Science, Вильям Спрингер.

Основная информация

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

Указатель на связный список — это просто указатель на первый элемент, или head, списка;

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

Во многом дополнение массива.

Пример:

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

Сравнение с массивом

Массив	Связный список
Быстрый доступ к любому элементу по ключу	Необходимо пройтись по всем ссылкам, пока не будет найден нужный элемент. В худшем случае займет О(n) времени.
Фиксированный размер (во многих языках программирования, но не в JavaScript)	Элементы могут размещаться в любом месте памяти и он может произвольно увеличиваться, пока не закончится доступная память
Вставка и удаление элементов затратны	Вставка и удаление элементов удаляются за постоянное время если есть указатель на предыдущий узел

Реализация на JavaScript

Пример реализации взят с этого сайта. Также немного другой пример можно посмотреть здесь (реализация с tail).

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

JavaScript

1class LinkedListNode {
2	constructor(value, next = null) {
3		this.value = value;
4		this.next = next;
5	}
6}

Список создаем через отдельный класс, работая только с head списка (Есть примеры реализации связного списка с сохранением и хвоста (tail) списка).

JavaScript

1class LinkedList {
2	constructor() {
3		// сохраняем ссылку на голову
4		this.head = null;
5	}
6}

Добавление нового элемента

В начало списка

В этом случае добавленный элемент становится head, а в его указатель на следующий элемент (next) записываем текущее значение head.

JavaScript

1add(value) {
2		this.head = new LinkedListNode(value, this.head);
3}

Через индекс (в середину или конец списка)

JavaScript

1insert(index, value) {
2		if (this.head === null) {
3			// если список пустой, вставляем элемент в начало
4			this.head = new LinkedListNode(value, null);
5		} else if (index === 0) {
6			this.add(value);
7		} else {
8			// Нельзя сразу вставить элемент в поределнное место связного списка, нужно сначала перебрать все его узлы.
9			let current = this.head;
10			while (current.next !== null && index > 1) {
11				current = current.next;
12				index = index - 1;
13			}
14
15			// Педыдущему элементу указанного индекса устанавливаем ссылку на новый узел
16			current.next = new LinkedListNode(value, current.next);
17		}
18	}

Например, создали список и добавили три узла: 4, 24 и 88 (для упрощения буду использовать только значения здесь и ниже).

JavaScript

1const list = new LinkedList();
2
3list.add(4);
4list.add(24);
5list.add(88);

Head - элемент со значением 88.

Теперь хотим добавить элемент со значением 21 по индексу 2 - list.insert(2, 21);

let current= 88;

Первая итерация:

пройдя первый цикл while получим current 24, index 1;

Условие цикла не выполняется, так как index === 1, поэтому выходим из цикла и записываем узлу со значением 24 в next ссылку на новый элемент.

Если хотим добавить элемент под индексом 3, а не 2 - list.insert(3, 21);

Также первоначальное в значение current попадает head

let current= 88;

Первая итерация: пройдя первый цикл while получим current - 24, index 2;

Вторая итерация: получим current - 4, index 1;

Условие цикла не выполняется, так как index === 1, поэтому выходи м из цикла и записываем узлу со значением 4 в next ссылку на новый элемент.

Удаление элемента

Из начала списка

Заменяем значение в head следующим за ним узлом.

JavaScript

1remove() {
2		if (this.head === null) return;
3
4		this.head = this.head.next;
5}

По индексу (Из середины или конца)

JavaScript

1removeAt(index) {
2		if (this.head === null) {
3			return;
4		} else if (index === 0 || this.head.next === null) {
5			this.head = this.head.next;
6		} else {
7			let current = this.head;
8			while (current.next.next !== null && index > 1) {
9				current = current.next;
10				index = index - 1;
11			}
12
13			current.next = current.next.next;
14		}
15	}

Как видите, цикл прохождения по списку такой же как и при добавлении элемента, но для большего понимания также разберу его на примере того списка, который создали выше из узлов 4, 24, 88.

JavaScript

1const list = new LinkedList();
2
3list.add(4);
4list.add(24);
5list.add(88);
6
7// LinkedList {
8//   head: LinkedListNode {
9//     value: 88,
10//     next: LinkedListNode { value: 24, next: [LinkedListNode] }
11//   }
12// }

Хотим удалить узел со значением 4. Его индекс 2 - list.removeAt(2)

Записываем в current значение head.

let current= 88;

Первая итерация: Пройдя первую итерацию цикла while получим current 24, index 1;

Условие цикла не выполняется, так как index === 1, поэтому выходим из цикла и записываем узлу со значением 24 в next ссылку next узла со значением 4, перезаписывая ссылку на сам этот узел.

Если вывести после этого список в консоль получим:

JavaScript

1// LinkedList {
2//   head: LinkedListNode {
3//     value: 88,
4//     next: LinkedListNode { value: 24, next: null }
5//   }
6// }

Полный пример реализации на JS

JavaScript

1class LinkedListNode {
2	constructor(value, next = null) {
3		this.value = value;
4		this.next = next;
5	}
6}
7
8class LinkedList {
9	constructor() {
10		this.head = null;
11	}
12
13	add(value) {
14		this.head = new LinkedListNode(value, this.head);
15	}
16
17	// Вставка элемента в середину или конец списка (По индексу)
18	insert(index, value) {
19		if (this.head === null) {
20			this.head = new LinkedListNode(value, null);
21		} else if (index === 0) {
22			this.add(value);
23		} else {
24			let current = this.head;
25			while (current.next !== null && index > 1) {
26				current = current.next;
27				index = index - 1;
28			}
29
30			current.next = new LinkedListNode(value, current.next);
31		}
32	}
33
34	// Удаление элемента из начала списка
35	remove() {
36		if (this.head === null) return;
37
38		this.head = this.head.next;
39	}
40
41	// Удаление элемента по индексу элемента
42	removeAt(index) {
43		if (this.head === null) {
44			// Возвращаемся из функции если список пустой
45			return;
46		} else if (index === 0 || this.head.next === null) {
47			this.head = this.head.next;
48		} else {
49			let current = this.head;
50			while (current.next.next !== null && index > 1) {
51				current = current.next;
52				index = index - 1;
53			}
54
55			current.next = current.next.next;
56		}
57	}
58}

Структуры данных. Связный список

Основная информация

Реализация на JavaScript

Добавление нового элемента

В начало списка

Через индекс (в середину или конец списка)

Удаление элемента

Из начала списка

По индексу (Из середины или конца)

Полный пример реализации на JS

Другие посты