Skip to content

Commit 3548cba

Browse files
iliakaniliakan
committed
works
1 parent 4bdc4cd commit 3548cba

13 files changed

Lines changed: 453 additions & 13 deletions

File tree

‎1-js/4-data-structures/8-array-methods/article.md‎

Lines changed: 12 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -463,10 +463,21 @@ We covered the most useful methods. But there are other too, for instance:
463463

464464
It creates a new array with elements from `arr` in the reverse order.
465465

466-
- [arr.some(fn)](mdn:js/Array/some)/[arr.every(fn)](mdn:js/Array/every) check the array.
466+
- [arr.some(fn)](mdn:js/Array/some)/[arr.every(fn)](mdn:js/Array/every) checks the array.
467467

468468
The function `fn` is called on each element of the array similar to `map`. If any/all results are `true`, returns `true`, otherwise `false`.
469469

470+
- [Array.isArray(value)](mdn:js/Array/isArray) checks if the `value` is an array.
471+
472+
As we've seen in the chapter <info:types>, the `typeof` operator cannot differ an array from a plain object:
473+
474+
```js run
475+
alert( typeof {} ); // object
476+
alert( typeof [] ); // object
477+
```
478+
479+
The call `Array.isArray(value)` helps. It returns `true` if `value` is an array, otherwise `false`.
480+
470481
These and other methods are also listed in the [manual](mdn:js/Array).
471482

472483
## Summary

‎1-js/5-deeper/1-recursion/9-output-single-linked-list/solution.md‎

Lines changed: 153 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,153 @@
1+
# Вывод списка в цикле
2+
3+
```js run
4+
var list = {
5+
value: 1,
6+
next: {
7+
value: 2,
8+
next: {
9+
value: 3,
10+
next: {
11+
value: 4,
12+
next: null
13+
}
14+
}
15+
}
16+
};
17+
18+
function printList(list) {
19+
var tmp = list;
20+
21+
while (tmp) {
22+
alert( tmp.value );
23+
tmp = tmp.next;
24+
}
25+
26+
}
27+
28+
printList(list);
29+
```
30+
31+
Обратите внимание, что для прохода по списку используется временная переменная `tmp`, а не `list`. Можно было бы и бегать по списку, используя входной параметр функции:
32+
33+
```js
34+
function printList(list) {
35+
36+
while(*!*list*/!*) {
37+
alert( list.value );
38+
list = list.next;
39+
}
40+
41+
}
42+
```
43+
44+
...Но при этом мы в будущем не сможем расширить функцию и сделать со списком что-то ещё, ведь после окончания цикла начало списка уже нигде не хранится.
45+
46+
Поэтому и используется временная переменная -- чтобы сделать код расширяемым, и, кстати, более понятным, ведь роль `tmp` -- исключительно обход списка, как `i` в цикле `for`.
47+
48+
# Вывод списка с рекурсией
49+
50+
Рекурсивный вариант `printList(list)` следует простой логике: вывести текущее значение `(1)`, а затем пропустить через себя следующее `(2)`:
51+
52+
```js run
53+
var list = {
54+
value: 1,
55+
next: {
56+
value: 2,
57+
next: {
58+
value: 3,
59+
next: {
60+
value: 4,
61+
next: null
62+
}
63+
}
64+
}
65+
};
66+
67+
function printList(list) {
68+
69+
alert( list.value ); // (1)
70+
71+
if (list.next) {
72+
printList(list.next); // (2)
73+
}
74+
75+
}
76+
77+
printList(list);
78+
```
79+
80+
# Обратный вывод с рекурсией
81+
82+
Обратный вывод -- почти то же самое, что прямой, просто сначала мы обрабатываем следующее значение, а потом -- текущее:
83+
84+
```js run
85+
var list = {
86+
value: 1,
87+
next: {
88+
value: 2,
89+
next: {
90+
value: 3,
91+
next: {
92+
value: 4,
93+
next: null
94+
}
95+
}
96+
}
97+
};
98+
99+
function printReverseList(list) {
100+
101+
if (list.next) {
102+
printReverseList(list.next);
103+
}
104+
105+
alert( list.value );
106+
}
107+
108+
printReverseList(list);
109+
```
110+
111+
# Обратный вывод без рекурсии
112+
113+
```js run
114+
var list = {
115+
value: 1,
116+
next: {
117+
value: 2,
118+
next: {
119+
value: 3,
120+
next: {
121+
value: 4,
122+
next: null
123+
}
124+
}
125+
}
126+
};
127+
128+
function printReverseList(list) {
129+
var arr = [];
130+
var tmp = list;
131+
132+
while (tmp) {
133+
arr.push(tmp.value);
134+
tmp = tmp.next;
135+
}
136+
137+
for (var i = arr.length - 1; i >= 0; i--) {
138+
alert( arr[i] );
139+
}
140+
}
141+
142+
printReverseList(list);
143+
```
144+
145+
**Обратный вывод без рекурсии быстрее.**
146+
147+
По сути, рекурсивный вариант и нерекурсивный работают одинаково: они проходят список и запоминают его элементы, а потом выводят в обратном порядке.
148+
149+
В случае с массивом это очевидно, а для рекурсии запоминание происходит в стеке (внутренней специальной структуре данных): когда вызывается вложенная функция, то интерпретатор сохраняет в стек текущие параметры. Вложенные вызовы заполняют стек, а потом он выводится в обратном порядке.
150+
151+
При этом, при рекурсии в стеке сохраняется не только элемент списка, а другая вспомогательная информация, необходимая для возвращения из вложенного вызова. Поэтому тратится больше памяти. Все эти расходы отсутствуют в варианте без рекурсии, так как в массиве хранится именно то, что нужно.
152+
153+
Преимущество рекурсии, с другой стороны -- более короткий и, зачастую, более простой код.

‎1-js/5-deeper/1-recursion/9-output-single-linked-list/task.md‎

Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
importance: 5
2+
3+
---
4+
5+
# Вывести односвязный список
6+
7+
TODO: определение списка есть в статье, убрать отсюда.
8+
9+
[Односвязный список](http://ru.wikipedia.org/wiki/Связный_список) -- это структура данных, которая состоит из *элементов*, каждый из которых хранит ссылку на следующий. Последний элемент может не иметь ссылки, либо она равна `null`.
10+
11+
Например, объект ниже задаёт односвязный список, в `next` хранится ссылка на следующий элемент:
12+
13+
```js
14+
var list = {
15+
value: 1,
16+
next: {
17+
value: 2,
18+
next: {
19+
value: 3,
20+
next: {
21+
value: 4,
22+
next: null
23+
}
24+
}
25+
}
26+
};
27+
```
28+
29+
Графическое представление этого списка:
30+
![](linked-list.png)
31+
32+
Альтернативный способ создания:
33+
34+
```js no-beautify
35+
var list = { value: 1 };
36+
list.next = { value: 2 };
37+
list.next.next = { value: 3 };
38+
list.next.next.next = { value: 4 };
39+
```
40+
41+
Такая структура данных интересна тем, что можно очень быстро разбить список на части, объединить списки, удалить или добавить элемент в любое место, включая начало. При использовании массива такие действия требуют обширных перенумерований.
42+
43+
Задачи:
44+
45+
1. Напишите функцию `printList(list)`, которая выводит элементы списка по очереди, при помощи цикла.
46+
2. Напишите функцию `printList(list)` при помощи рекурсии.
47+
3. Напишите функцию `printReverseList(list)`, которая выводит элементы списка в обратном порядке, при помощи рекурсии.
48+
Для списка выше она должна выводить `4`,`3`,`2`,`1`
49+
4. Сделайте вариант `printReverseList(list)`, использующий не рекурсию, а цикл.
50+
51+
Как лучше -- с рекурсией или без?

0 commit comments

Comments
 (0)