DoublyLinkedList

class DoublyLinkedList {
	constructor() {
		this.size = 0
		this.head = null
		this.tail = null
	}

	prepend(value) {
		// Создаём новый узел, который будет новым head,
		// при создании передаём второй аргумент, который указывает
		// что его "next" будет текущий head,
		// так как новый узел будет стоять перед текущем head.
		const newNode = {
			value,
			next: null,
			prev: null,
		}

		// Если есть head, то он больше не будет head.
		// Поэтому, его ссылку на предыдущий узел (previous) меняем на новый узел.
		if (this.head) {
			this.head.prev = newNode
		}

		// Переназначаем head на новый узел
		this.head = newNode

		// Если ещё нет tail, делаем новый узел tail.
		if (!this.tail) {
			this.tail = newNode
		}
		this.size++
		// Возвращаем весь список.
		return this
	}

	append(value) {
		// Создаём новый узел.
		const newNode = {
			value,
			next: null,
			prev: null,
		}

		if (this.tail) {
			// Присоединяем новый узел к концу связного списка.
			this.tail.next = newNode
		}

		// В новом узле указываем ссылку на предыдущий (previous) элемент на this.tail,
		// так как новый узел будет теперь последним.
		newNode.prev = this.tail

		// Переназначаем tail на новый узел.
		this.tail = newNode

		// Если ещё нет head, делаем новый узел head.
		if (!this.head) {
			this.head = newNode
		}
		this.size++
		return this
	}

	// Добавляет элемент в список.
	// Если указан индекс - добавляет по индексу,
	// в противном случае добавляет в конец.
	// Если индекс за пределами — кидает ошибку.
	add(value, index = this.size) {
		if (!Number.isInteger(index) || index < 0 || index > this.size + 1) {
			console.log(`Invalid index. Current length is ${this.size}.`)
			return this
		}

		// If index is 0, prepend
		// If index is equal to this.length, append
		if (index === 0) {
			this.prepend(value)
			return this
		} else if (index === this.size) {
			this.append(value)
			return this
		}

		// Reach the node at that index
		let newNode = {
			value,
			next: null,
			prev: null,
		}
		let previousNode = this.head

		for (let k = 0; k < index - 1; k++) {
			previousNode = previousNode.next
		}

		let nextNode = previousNode.next

		newNode.next = nextNode
		previousNode.next = newNode
		newNode.prev = previousNode
		nextNode.prev = newNode

		this.size++
	}

	// Удаляет элемент из списка по значению.
	// Удаляет только первый найденный элемент.
	// Если элемент не найден, ничего делать не нужно.
	removeByValue(value) {
		// Если нет head значит список пуст.
		if (!this.head) {
			return
		}

		let deletedNode = null
		let currentNode = this.head

		// Перебираем все узлы и удаляем их, если их значение равно указанному.
		while (currentNode) {
			if (currentNode.value === value) {
				// Сохраняем значение текущего узла как удаленное.
				deletedNode = currentNode

				// Если head должен быть удален,
				if (deletedNode === this.head) {
					// то делаем следующий узел новым head
					this.head = deletedNode.next

					// Меняем в новом head ссылку (previous) на null.
					if (this.head) {
						this.head.prev = null
					}

					// Если все узлы в списке имеют одинаковое значение,
					// которое передается в качестве аргумента,
					// тогда все узлы будут удалены. Поэтому tail необходимо обновить.
					if (deletedNode === this.tail) {
						this.tail = null
					}
				} else if (deletedNode === this.tail) {
					// Если tail должен быть удален, -
					// меняем tail на предпоследний узел, который станет новым хвостом.
					this.tail = deletedNode.prev
					// Обновляем ссылку next в новом хвосте.
					this.tail.next = null
				} else {
					// Если средний узел будет удален, -
					// сохраняем ссылку на предыдущий элемент,
					const previousNode = deletedNode.prev
					// и сохраняем ссылку на следующий элемент.
					const nextNode = deletedNode.next
					// Меняем ссылки у предыдущего и следующего узлов от удаленного узла,
					// чтобы они больше не ссылались на удаленный узел.
					previousNode.next = nextNode
					nextNode.prev = previousNode
				}
				this.size--
				return
			}

			// Перематываем на один узел вперёд.
			currentNode = currentNode.next
		}
	}

	// Удаляет элемент из списка по индексу.
	// Если индекс за пределами — кидает ошибку.
	removeByIndex(index) {
		// Если нет head значит список пуст.
		if (!this.head) {
			return null
		}

		let deletedNode = null
		let i = 0

		// Перебираем все узлы и удаляем их, если их значение равно указанному.

		// Сохраняем значение текущего узла как удаленное.
		deletedNode = this.searchByIndex(index)

		// Если head должен быть удален,
		if (deletedNode === this.head) {
			// то делаем следующий узел новым head
			this.head = deletedNode.next

			// Меняем в новом head ссылку (previous) на null.
			if (this.head) {
				this.head.prev = null
			}

			// Если все узлы в списке имеют одинаковое значение,
			// которое передается в качестве аргумента,
			// тогда все узлы будут удалены. Поэтому tail необходимо обновить.
			if (deletedNode === this.tail) {
				this.tail = null
			}
		} else if (deletedNode === this.tail) {
			// Если tail должен быть удален, -
			// меняем tail на предпоследний узел, который станет новым хвостом.
			this.tail = deletedNode.prev
			// Обновляем ссылку next в новом хвосте.
			this.tail.next = null
		} else {
			// Если средний узел будет удален, -
			// сохраняем ссылку на предыдущий элемент,
			const previousNode = deletedNode.prev
			// и сохраняем ссылку на следующий элемент.
			const nextNode = deletedNode.next
			// Меняем ссылки у предыдущего и следующего узлов от удаленного узла,
			// чтобы они больше не ссылались на удаленный узел.
			previousNode.next = nextNode
			nextNode.prev = previousNode
		}

		return deletedNode
	}

	// Ищет элемент в списке по индексу.
	// Если индекс за пределами — кидает ошибку.
	searchByIndex(index) {
		// Если нет head - список пуст.
		if (!this.head) {
			return null
		}

		// Проверка неверной позиции
		if (index < 0 || index > this.size) {
			throw new Error('Индекс за пределами списка')
		}

		let currentNode = this.head
		let count = 0

		// Перебираем все узлы до нужного индекса.
		while (count < index) {
			currentNode = currentNode.next
			count++
		}

		return currentNode
	}

	// Ищет элемент в списке по значению.
	// Возвращает первый найденный элемент.
	// Опционально можно указать индекс начала поиска.
	// Если индекс за пределами — кидает ошибку.
	// Если элемент не найден, нужно вернуть null.
	searchByValue(value, startIndex = 0) {
		// Если нет head - список пуст.
		if (!this.head) {
			return null
		}

		let currentNode = this.head

		// Перебираем все узлы в поиске значения.
		while (currentNode) {
			// Если указано значение, пробуем сравнить его по значению.
			if (value !== undefined && currentNode.value === value) {
				return currentNode
			}

			// Перематываем на один узел вперед.
			currentNode = currentNode.next
		}

		return null
	}
}
const userObj = new DoublyLinkedList()

userObj.add('test1')
userObj.add('test2')
userObj.add('test3')
userObj.add('test4')
userObj.add('test5')
userObj.removeByValue('test111')

// console.log(userObj.searchByIndex(0))
// console.log(userObj.searchByIndex(1))
// console.log(userObj.searchByIndex(2))
console.log(userObj.size)
console.log(userObj.head)
console.log(userObj.tail)