FazBrowse GitHub Viewer | Trending |
URL:
| Home
Tools: [Download Repo ZIP]   [Original HTTPS Page]

Translate DoublyLinkedList. (#276) · tallmorgan/javascript-algorithms@f53eb17 · GitHub

/ javascript-algorithms Public
forked from trekhleb/javascript-algorithms

Commit f53eb17

Browse files
Stulov Alex
authored and
trekhleb
committed
Translate DoublyLinkedList. (trekhleb#276)
1 parent db6fcb2 commit f53eb17

3 files changed

Lines changed: 113 additions & 1 deletion

File tree

‎src/data-structures/doubly-linked-list/README.md‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,9 @@
11
# Doubly Linked List
22

3+
_Read this in other languages:_
4+
[_简体中文_](README.zh-CN.md),
5+
[_Русский_](README.ru-RU.md)
6+
37
In computer science, a **doubly linked list** is a linked data structure that
48
consists of a set of sequentially linked records called nodes. Each node contains
59
two fields, called links, that are references to the previous and to the next

‎src/data-structures/doubly-linked-list/README.ru-RU.md‎

Lines changed: 108 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,108 @@
1+
# Двусвязный список
2+
3+
**Двусвязный список** — связная структура данных в информатике, состоящая из набора
4+
последовательно связанных записей, называемых узлами. Каждый узел содержит два поля,
5+
называемых ссылками, которые указывают на предыдущий и последующий элементы в
6+
последовательности узлов. Ссылка на предыдущий элемент корневого узла ссылка на
7+
последующий элемент последнего узла, указывают на некого рода прерыватель, обычно
8+
сторожевой узел или null, для облегчения обхода списка. Если в списке только один
9+
сторожевой узел, тогда список циклически связана через него.
10+
Двусвязный список можно представить, как два связных списка, которые образованны из
11+
одних и тех же данных, но расположенных в противоположном порядке.
12+
13+
![Двусвязный список](https://upload.wikimedia.org/wikipedia/commons/5/5e/Doubly-linked-list.svg)
14+
15+
Две ссылки позволяют обходить список в обоих направлениях. Добавление и
16+
удаление узла в двусвязном списке требует изменения большего количества ссылок,
17+
чем аналогичные операции в связном списке. Однако данные операции проще и потенциально
18+
более эффективны (для некорневых узлов) - при обходе не нужно следить за предыдущим
19+
узлом или повторно обходить список в поиске предыдущего узла, плюс его ссылка
20+
может быть изменена.
21+
22+
## Псевдокод основных операций
23+
24+
### Вставка
25+
26+
```text
27+
Add(value)
28+
Pre: value - добавляемое значение
29+
Post: value помещено в конец списка
30+
n ← node(value)
31+
if head = ø
32+
head ← n
33+
tail ← n
34+
else
35+
n.previous ← tail
36+
tail.next ← n
37+
tail ← n
38+
end if
39+
end Add
40+
```
41+
42+
### Удаление
43+
44+
```text
45+
Remove(head, value)
46+
Pre: head - первый узел в списке
47+
value - значение, которое следует удалить
48+
Post: true - value удалено из списка, иначе false
49+
if head = ø
50+
return false
51+
end if
52+
if value = head.value
53+
if head = tail
54+
head ← ø
55+
tail ← ø
56+
else
57+
head ← head.Next
58+
head.previous ← ø
59+
end if
60+
return true
61+
end if
62+
n ← head.next
63+
while n = ø and value = n.value
64+
n ← n.next
65+
end while
66+
if n = tail
67+
tail ← tail.previous
68+
tail.next ← ø
69+
return true
70+
else if n = ø
71+
n.previous.next ← n.next
72+
n.next.previous ← n.previous
73+
return true
74+
end if
75+
return false
76+
end Remove
77+
```
78+
79+
### Обратный обход
80+
81+
```text
82+
ReverseTraversal(tail)
83+
Pre: tail - конечный элемент обходимого списка
84+
Post: элементы списка пройдены в обратном порядке
85+
n ← tail
86+
while n = ø
87+
yield n.value
88+
n ← n.previous
89+
end while
90+
end Reverse Traversal
91+
```
92+
93+
## Сложность
94+
95+
## Временная сложность
96+
97+
| Чтение | Поиск | Вставка | Удаление |
98+
| :-------: | :-------: | :-------: | :-------: |
99+
| O(n) | O(n) | O(1) | O(1) |
100+
101+
### Пространственная сложность
102+
103+
O(n)
104+
105+
## Ссылки
106+
107+
- [Wikipedia](https://ru.wikipedia.org/wiki/%D0%A1%D0%B2%D1%8F%D0%B7%D0%BD%D1%8B%D0%B9_%D1%81%D0%BF%D0%B8%D1%81%D0%BE%D0%BA#%D0%94%D0%B2%D1%83%D1%81%D0%B2%D1%8F%D0%B7%D0%BD%D1%8B%D0%B9_%D1%81%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_(%D0%B4%D0%B2%D1%83%D0%BD%D0%B0%D0%BF%D1%80%D0%B0%D0%B2%D0%BB%D0%B5%D0%BD%D0%BD%D1%8B%D0%B9_%D1%81%D0%B2%D1%8F%D0%B7%D0%BD%D1%8B%D0%B9_%D1%81%D0%BF%D0%B8%D1%81%D0%BE%D0%BA))
108+
- [YouTube](https://www.youtube.com/watch?v=lQ-lPjbb9Ew)

‎src/data-structures/linked-list/README.ru-RU.md‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -142,4 +142,4 @@ O(n)
142142
## Ссылки
143143

144144
- [Wikipedia](https://ru.wikipedia.org/wiki/%D0%A1%D0%B2%D1%8F%D0%B7%D0%BD%D1%8B%D0%B9_%D1%81%D0%BF%D0%B8%D1%81%D0%BE%D0%BA)
145-
- [YouTube](https://www.youtube.com/watch?v=njTh_OwMljA&index=2&t=1s&list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8)
145+
- [YouTube](https://www.youtube.com/watch?v=KTpOalDwBjg)

0 commit comments

Comments
 (0)
Back | FazBrowse Home | New Git URL