Инструменты пользователя
basics_of_algorithms:doubly_linked_list
Различия
Здесь показаны различия между двумя версиями данной страницы.
| Предыдущая версия справа и слева Предыдущая версия Следующая версия | Предыдущая версия | ||
|
basics_of_algorithms:doubly_linked_list [2023/10/20 17:01] werwolf [Вставка узла в начало списка] |
basics_of_algorithms:doubly_linked_list [2023/10/20 22:16] (текущий) werwolf [Примеры] |
||
|---|---|---|---|
| Строка 194: | Строка 194: | ||
| * Ссылка на последний узел — <color red>tail</color> | * Ссылка на последний узел — <color red>tail</color> | ||
| * Различные методы, например: | * Различные методы, например: | ||
| - | * ''insertBegin(value)'' — вставка в начало | + | * <color red>insertBegin(value)</color> — вставка в начало |
| - | * ''insertEnd(value)'' — вставка в конец | + | * <color red>insertEnd(value)</color> — вставка в конец |
| - | * ''removeBegin()'' — удаление из начала | + | * <color red>removeBegin()</color> — удаление из начала |
| - | Новый список пуст, поэтому поля ''head'' и ''tail'' содержат значение ''null'': | + | Новый список пуст, поэтому поля <color red>head</color> и <color red>tail</color> содержат значение <color red>null</color>: |
| - | {{https://cdn2.hexlet.io/derivations/image/original/eyJpZCI6ImNlNzU0OTdlZmFhZWU0M2JjOWYwNGU5ZTMzYWExZDM3LnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=fcbd19effa085666c31749cbbb11e8a4ce795cbd48cc6d1ef40fce24916b897c?400|400}}После вставки первого узла ''head'' и ''tail'' содержат его адрес. При этом поля ''previous'' и ''next'' у этого узла никуда не указывают, потому что он одновременно является первым и последним в списке — другими словами, у него нет ни предыдущего, ни следующего узла: | + | {{ :basics_of_algorithms:image_processing20231016-24-v3t3k9.png?300 |}} |
| - | {{https://cdn2.hexlet.io/derivations/image/original/eyJpZCI6ImViYTQ5OTFkODU0MTExYTkyY2RiNWQ5MTJiNzMyOGU3LnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=c68788227472999711963efe383e92c572ef81bca7f9c6a8c5b73edfdd29ebc9|eyJpZCI6ImViYTQ5OTFkODU0MTExYTkyY2RiNWQ5MTJiNzMyOGU3LnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=c68788227472999711963efe383e92c572ef81bca7f9c6a8c5b73edfdd29ebc9}}Теперь посмотрим на фрагмент кода: | + | После вставки первого узла <color red>head</color> и <color red>tail</color> содержат его адрес. При этом поля <color red>previous</color> и <color red>next</color> у этого узла никуда не указывают, потому что он одновременно является первым и последним в списке — другими словами, у него нет ни предыдущего, ни следующего узла: |
| - | <code> | + | {{ :basics_of_algorithms:image_processing20231016-39-n7fcvw.png?600 |}} |
| + | |||
| + | Теперь посмотрим на фрагмент кода: | ||
| + | |||
| + | <code javascript> | ||
| if (this.head == null) { | if (this.head == null) { | ||
| const node = new DoublyLinkedListNode(value, null, null); | const node = new DoublyLinkedListNode(value, null, null); | ||
| Строка 212: | Строка 216: | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| + | <summary>Python</summary> | ||
| - | <code> | + | <code python> |
| if self.head is None: | if self.head is None: | ||
| node = DoublyLinkedListNode( | node = DoublyLinkedListNode( | ||
| Строка 222: | Строка 227: | ||
| self.tail = node | self.tail = node | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| Строка 234: | Строка 241: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| if (head == null) { | if (head == null) { | ||
| var node = new DoublyLinkedListNode(value, null, null); | var node = new DoublyLinkedListNode(value, null, null); | ||
| Строка 244: | Строка 253: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Условие ''this.head == null'' выполняется для пустого списка. Нам достаточно создать узел с пустыми ссылками на предыдущий и следующий узлы, а затем присвоить его адрес полям ''this.head'' и ''this.tail''. | + | Условие <color red>this.head == null</color> выполняется для пустого списка. Нам достаточно создать узел с пустыми ссылками на предыдущий и следующий узлы, а затем присвоить его адрес полям <color red>this.head</color> и <color red>this.tail</color>. |
| - | При вставке каждого следующего узла в начало, ''head'' всегда будет указывать на новый узел. Значение ''tail'' при этом не изменится, потому что хвост списка остается прежним. Поле ''next'' новой головы списка будет указывать на прежнюю голову, а в поле ''previous'' старой головы вместо null должен появиться адрес новой головы: | + | При вставке каждого следующего узла в начало, <color red>head</color> всегда будет указывать на новый узел. Значение <color>tail</color> при этом не изменится, потому что хвост списка остается прежним. Поле <color red>next</color> новой головы списка будет указывать на прежнюю голову, а в поле <color red>previous</color> старой головы вместо null должен появиться адрес новой головы: |
| - | {{https://cdn2.hexlet.io/derivations/image/original/eyJpZCI6IjhiOWU4MzI5ZGZiMTJlM2Q3OGZmMzBhY2QxNmFjNmYwLnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=7c1986d7e3fcbbb6d44608936b8de2e8882ce3664b5f11cf148a8549f89bf2e0|eyJpZCI6IjhiOWU4MzI5ZGZiMTJlM2Q3OGZmMzBhY2QxNmFjNmYwLnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=7c1986d7e3fcbbb6d44608936b8de2e8882ce3664b5f11cf148a8549f89bf2e0}}Это довольно сложная логика, которая требует аккуратной реализации и проверки граничных условий. Поэтому код методов двусвязного списка сложнее, чем код методов односвязного. Посмотрите на этот пример: | + | {{ :basics_of_algorithms:image_processing20231016-39-mkvx9s.png?600 |}} |
| - | <code> | + | Это довольно сложная логика, которая требует аккуратной реализации и проверки граничных условий. Поэтому код методов двусвязного списка сложнее, чем код методов односвязного. Посмотрите на этот пример: |
| + | |||
| + | <code javascript> | ||
| const node = new DoublyLinkedListNode(value, null, this.head); | const node = new DoublyLinkedListNode(value, null, this.head); | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| + | <summary>Python</summary> | ||
| - | <code> | + | <code python> |
| node = DoublyLinkedListNode(value, None, self.head) | node = DoublyLinkedListNode(value, None, self.head) | ||
| </code> | </code> | ||
| + | </details> | ||
| + | <details> | ||
| + | <summary>PHP</summary> | ||
| - | PHP | + | <code php> |
| - | + | ||
| - | <code> | + | |
| <?php | <?php | ||
| $node = new DoublyLinkedListNode($value, null, $this->head); | $node = new DoublyLinkedListNode($value, null, $this->head); | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| var node = new DoublyLinkedListNode(value, null, head); | var node = new DoublyLinkedListNode(value, null, head); | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Создавая узел, мы сразу записываем в поле ''next'' текущее значение ''this.head''— текущую голову. Поле ''previous'' текущей головы должно ссылать на новый узел, за это отвечает такая строка: | + | Создавая узел, мы сразу записываем в поле <color red>next</color> текущее значение <color red>this.head</color>— текущую голову. Поле <color red>previous</color> текущей головы должно ссылать на новый узел, за это отвечает такая строка: |
| - | <code> | + | <code javascript> |
| this.head.previous = node; | this.head.previous = node; | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| + | <summary>Python</summary> | ||
| - | <code> | + | <code python> |
| self.head.previous = node | self.head.previous = node | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| $this->head->previous = $node; | $this->head->previous = $node; | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| head.previous = node; | head.previous = node; | ||
| </code> | </code> | ||
| + | </details> | ||
| Наконец, новый узел становится новой головой списка: | Наконец, новый узел становится новой головой списка: | ||
| - | <code> | + | <code javascript> |
| this.head = node; | this.head = node; | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| + | <summary>Python</summary> | ||
| - | <code> | + | <code python> |
| self.head = node | self.head = node | ||
| </code> | </code> | ||
| + | </details> | ||
| + | <details> | ||
| + | <summary>PHP</summary> | ||
| - | PHP | + | <code php> |
| - | + | ||
| - | <code> | + | |
| <?php | <?php | ||
| $this->head= $node; | $this->head= $node; | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| head = node; | head = node; | ||
| </code> | </code> | ||
| + | </details> | ||
| ===== Вставка узла в конец списка ===== | ===== Вставка узла в конец списка ===== | ||
| Строка 331: | Строка 359: | ||
| Перейдем к вставке узла в конец списка: | Перейдем к вставке узла в конец списка: | ||
| - | <code> | + | <code javascript> |
| insertEnd(value) { | insertEnd(value) { | ||
| if (this.tail == null) { | if (this.tail == null) { | ||
| Строка 344: | Строка 372: | ||
| } | } | ||
| </code> | </code> | ||
| + | <details> | ||
| + | <summary>Python</summary> | ||
| - | Python | + | <code python> |
| - | + | ||
| - | <code> | + | |
| def insert_end(self, value): | def insert_end(self, value): | ||
| if self.tail is None: | if self.tail is None: | ||
| Строка 358: | Строка 386: | ||
| self.tail = node | self.tail = node | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| Строка 377: | Строка 407: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| class DoublyLinkedList { | class DoublyLinkedList { | ||
| // ... | // ... | ||
| Строка 397: | Строка 429: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Такая вставка симметрична вставке в начало. Разница только в том, что здесь мы должны везде менять местами ''head'' и ''tail'', а также ''previous'' и ''next''. | + | Такая вставка симметрична вставке в начало. Разница только в том, что здесь мы должны везде менять местами <color red>head</color> и <color red>tail</color>, а также <color red>previous</color> и <color red>next</color>. |
| ===== Удаление узла ===== | ===== Удаление узла ===== | ||
| Строка 404: | Строка 437: | ||
| Перейдем к операциям удаления: | Перейдем к операциям удаления: | ||
| - | <code> | + | <code javascript> |
| removeBegin() { | removeBegin() { | ||
| if (this.head == null) { | if (this.head == null) { | ||
| Строка 424: | Строка 457: | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| + | <summary>Python</summary> | ||
| - | <code> | + | <code python> |
| def remove_begin(self): | def remove_begin(self): | ||
| if self.head is None: | if self.head is None: | ||
| Строка 442: | Строка 476: | ||
| return result | return result | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| Строка 467: | Строка 503: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | ||
| - | <code> | + | <details> |
| + | <summary>Java</summary> | ||
| + | |||
| + | <code java> | ||
| class DoublyLinkedList { | class DoublyLinkedList { | ||
| // ... | // ... | ||
| Строка 493: | Строка 532: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Метод удаления возвращает значение из удаленного узла. Если список пуст и удалять нечего, метод возвращает ''undefined''. В остальных случаях мы сохраняем значение в переменную ''result'': | + | Метод удаления возвращает значение из удаленного узла. Если список пуст и удалять нечего, метод возвращает <color red>undefined</color>. В остальных случаях мы сохраняем значение в переменную <color red>result</color>: |
| - | <code> | + | <code javascript> |
| if (this.head == null) { | if (this.head == null) { | ||
| return undefined; | return undefined; | ||
| Строка 504: | Строка 544: | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| + | <summary>Python</summary> | ||
| - | <code> | + | <code python> |
| if self.head is None: | if self.head is None: | ||
| return None | return None | ||
| Строка 512: | Строка 553: | ||
| result = self.head.value | result = self.head.value | ||
| </code> | </code> | ||
| + | </details> | ||
| + | <details> | ||
| + | <summary>PHP</summary> | ||
| - | PHP | + | <code php> |
| - | + | ||
| - | <code> | + | |
| <?php | <?php | ||
| Строка 524: | Строка 566: | ||
| $result = $this->head->value; | $result = $this->head->value; | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| if (head == null) { | if (head == null) { | ||
| return null; | return null; | ||
| Строка 534: | Строка 578: | ||
| var result = head.value; | var result = head.value; | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Если ''this.head == this.tail'', значит, в списке находится один последний узел — он является одновременно и головой, и хвостом. Чтобы его удалить, достаточно обнулить ''head'' и ''tail'': | + | Если <color red>this.head == this.tail</color>, значит, в списке находится один последний узел — он является одновременно и головой, и хвостом. Чтобы его удалить, достаточно обнулить <color red>head</color> и <color red>tail</color>: |
| - | <code> | + | <code javascript> |
| if (this.head == this.tail) { | if (this.head == this.tail) { | ||
| this.head = null; | this.head = null; | ||
| Строка 544: | Строка 589: | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| + | <summary>Python</summary> | ||
| - | <code> | + | <code python> |
| if self.head == self.tail: | if self.head == self.tail: | ||
| self.head = None | self.head = None | ||
| self.tail = None | self.tail = None | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| Строка 562: | Строка 610: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| if (head == tail) { | if (head == tail) { | ||
| head = null; | head = null; | ||
| Строка 571: | Строка 621: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| - | А теперь посмотрим обратный пример — избавимся от первого узла в списке. Сначала записываем в ''head'' ссылку на второй узел, а потом обнуляем у нее поле ''previous'': | + | А теперь посмотрим обратный пример — избавимся от первого узла в списке. Сначала записываем в <color red>head</color> ссылку на второй узел, а потом обнуляем у нее поле <color red>previous</color>: |
| - | <code> | + | <code javascript> |
| this.head = this.head.next; | this.head = this.head.next; | ||
| this.head.previous = null; | this.head.previous = null; | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| + | <summary>Python</summary> | ||
| - | <code> | + | <code python> |
| self.head = self.head.next | self.head = self.head.next | ||
| self.head.previous = None | self.head.previous = None | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| Строка 594: | Строка 648: | ||
| $this->head->previous = null; | $this->head->previous = null; | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| head = head.next; | head = head.next; | ||
| head.previous = null; | head.previous = null; | ||
| </code> | </code> | ||
| + | </details> | ||
| ===== Перебор значений в прямом порядке ===== | ===== Перебор значений в прямом порядке ===== | ||
| Строка 612: | Строка 669: | ||
| **Итератор** — это объект, который одинаковым образом перебирает элементы коллекции, независимо от структуры данных. Скажем, мы можем написать функцию суммирования элементов любой коллекции и вызвать ее для списка: | **Итератор** — это объект, который одинаковым образом перебирает элементы коллекции, независимо от структуры данных. Скажем, мы можем написать функцию суммирования элементов любой коллекции и вызвать ее для списка: | ||
| - | <code> | + | <code javascript> |
| const sum = (items) => { | const sum = (items) => { | ||
| let result = 0; | let result = 0; | ||
| Строка 626: | Строка 683: | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| + | <summary>Python</summary> | ||
| - | <code> | + | <code python> |
| def sum(items): | def sum(items): | ||
| result = 0 | result = 0 | ||
| Строка 638: | Строка 696: | ||
| print(sum([1, 2, 3, 4])) # => 10 | print(sum([1, 2, 3, 4])) # => 10 | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| Строка 657: | Строка 717: | ||
| print_r(sum([1, 2, 3, 4])); // => 10 | print_r(sum([1, 2, 3, 4])); // => 10 | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| class App { | class App { | ||
| public static int sum(Iterable<Integer> items) { | public static int sum(Iterable<Integer> items) { | ||
| Строка 675: | Строка 737: | ||
| System.out.println(App.sum(List.of(1, 2, 3, 4))); // => 10 | System.out.println(App.sum(List.of(1, 2, 3, 4))); // => 10 | ||
| </code> | </code> | ||
| + | </details> | ||
| Эта функция сможет работать и с нашим двусвязным списком, но для этого нам потребуется реализовать собственный итератор. | Эта функция сможет работать и с нашим двусвязным списком, но для этого нам потребуется реализовать собственный итератор. | ||
| Строка 685: | Строка 748: | ||
| Поэтому двусвязный список должен иметь два итератора — прямой и обратный. Чтобы так сделать, можно возвращать итераторы из методов класса. Например, метод ''fore()'' может создавать и возвращать прямой итератор: | Поэтому двусвязный список должен иметь два итератора — прямой и обратный. Чтобы так сделать, можно возвращать итераторы из методов класса. Например, метод ''fore()'' может создавать и возвращать прямой итератор: | ||
| - | <code> | + | <code javascript> |
| fore() { | fore() { | ||
| let iterator = { | let iterator = { | ||
| Строка 703: | Строка 766: | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| + | <summary>Python</summary> | ||
| - | <code> | + | <code python> |
| def fore(self): | def fore(self): | ||
| current = self.head | current = self.head | ||
| Строка 712: | Строка 776: | ||
| current = current.next | current = current.next | ||
| </code> | </code> | ||
| + | </details> | ||
| + | <details> | ||
| + | <summary>PHP</summary> | ||
| - | PHP | + | <code php> |
| - | + | ||
| - | <code> | + | |
| <?php | <?php | ||
| Строка 728: | Строка 793: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| Использовать итератор можно так: | Использовать итератор можно так: | ||
| - | <code> | + | <code javascript> |
| let list = new DoublyLinkedList(); | let list = new DoublyLinkedList(); | ||
| list.insertBegin(1); | list.insertBegin(1); | ||
| Строка 741: | Строка 807: | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| + | <summary>Python</summary> | ||
| - | <code> | + | <code python> |
| lst = DoublyLinkedList() | lst = DoublyLinkedList() | ||
| lst.insert_begin(1) | lst.insert_begin(1) | ||
| Строка 752: | Строка 819: | ||
| print(sum(lst.fore())) | print(sum(lst.fore())) | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| Строка 766: | Строка 835: | ||
| print_r(sum($list->fore())); // => 10 | print_r(sum($list->fore())); // => 10 | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| class DoubleLinkedList implements Iterable<Object> { | class DoubleLinkedList implements Iterable<Object> { | ||
| // ... | // ... | ||
| Строка 806: | Строка 877: | ||
| System.out.println(App.sum(list)); // => 10 | System.out.println(App.sum(list)); // => 10 | ||
| </code> | </code> | ||
| + | </details> | ||
| - | В JavaScript используется синтаксис ''function*'' и ''yield'', который упрощает работу с итераторами. В нашем примере порядок действий такой: | + | В JavaScript используется синтаксис <color red>function*</color> и <color red>yield</color>, который упрощает работу с итераторами. В нашем примере порядок действий такой: |
| * Начинаем с первого узла, адрес которого хранится в поле head | * Начинаем с первого узла, адрес которого хранится в поле head | ||
| * Пробегаем по всем узлам списка | * Пробегаем по всем узлам списка | ||
| - | * Передаем значения узлов в вызывающую функцию с помощью конструкции ''yield'' | + | * Передаем значения узлов в вызывающую функцию с помощью конструкции <color red>yield</color> |
| ===== Выводы ===== | ===== Выводы ===== | ||
| Строка 817: | Строка 889: | ||
| * Односвязный список подходит не для всех задач — вставка и удаление в конец списка гораздо медленнее, чем вставка и удаление в начало. Кроме того, в односвязном списке нельзя вставить узел перед другим узлом. | * Односвязный список подходит не для всех задач — вставка и удаление в конец списка гораздо медленнее, чем вставка и удаление в начало. Кроме того, в односвязном списке нельзя вставить узел перед другим узлом. | ||
| * Чтобы справиться с этими трудностями, программисты используют такую структуру данных, как двусвязный список. | * Чтобы справиться с этими трудностями, программисты используют такую структуру данных, как двусвязный список. | ||
| + | * В каждом узле двусвязного списка хранится не только ссылка на следующий узел (как у односвязного), но и на предыдущий. | ||
| + | * К плюсам двусвязного списка можно отнести возможность «пробегать» по списку как вперед, так и назад, а к минусам — сложный код и больший расход памяти. | ||
| + | * Итераторы позволяют писать один код для работы с коллекциями разных типов. Мы можем реализовать итераторы для тех структур данных, которые мы разрабатываем. | ||
| + | ===== Примеры ===== | ||
| + | |||
| + | **solutions/solution.js** | ||
| + | Импортируйте в solution.js класс <color red>DoubleLinkedListNode</color> и функцию <color red>getDoubleLinkedList()</color> следующим образом: | ||
| + | <code javascript> | ||
| + | import DoubleLinkedListNode from '../double_linked_list/DoubleLinkedListNode.js'; | ||
| + | import getDoubleLinkedList from '../helpers/helper.js'; | ||
| + | </code> | ||
| + | |||
| + | Реализуйте функцию, которая принимает на вход массив и возвращает также массив. Внутри функция должна создавать двусвязный список, после этого поменять первые два элемента списка местами и вернуть массив всех значений. | ||
| + | |||
| + | Для преобразования массива в список используйте функцию <color red>getDoubleLinkedList()</color>, а чтобы получить массив из списка воспользуйтесь методом <color red>toArray()</color> на объекте списка. | ||
| + | |||
| + | Экспортируйте функцию по умолчанию. | ||
| + | |||
| + | <code javascript> | ||
| + | import solution from './solution.js'; | ||
| + | |||
| + | const items = [[10, 20], 0, -1, ['hey']]; | ||
| + | </code> | ||
| + | |||
| + | <details> | ||
| + | <summary>**solutions/solution.php**</summary> | ||
| + | Импортируйте в solution.php код из файлов DoubleLinkedListNode.php и helper.php следующим образом: | ||
| + | <code php> | ||
| + | <?php | ||
| + | |||
| + | require_once(__DIR__ . '/../DoubleLinkedList/DoubleLinkedListNode.php'); | ||
| + | require_once(__DIR__ . '/../helpers/helper.php'); | ||
| + | </code> | ||
| + | Реализуйте функцию <color red>solution()</color>, которая принимает на вход массив и возвращает также массив. Внутри функция должна создавать двусвязный список, после этого поменять первые два элемента списка местами и вернуть массив всех значений. | ||
| + | |||
| + | Для преобразования массива в список используйте функцию <color red>getDoubleLinkedList()</color>, а чтобы получить массив из списка воспользуйтесь методом <color red>toArray()</color> на объекте списка. | ||
| + | |||
| + | <code php> | ||
| + | <?php | ||
| + | |||
| + | $items = [[10, 20], 0, -1, ['hey']]; | ||
| + | solution($items); // [0, [10, 20], -1, ['hey']] | ||
| + | solution([]); // [] | ||
| + | </code> | ||
| + | </details> | ||
| + | |||
| + | <details> | ||
| + | <summary>**solutions/solution.py**</summary> | ||
| + | Импортируйте в solution.py класс <color red>DoubleLinkedListNode</color> и функцию <color red>getListFromArray()</color> следующим образом: | ||
| + | <code python> | ||
| + | import os | ||
| + | import sys | ||
| + | |||
| + | sys.path.append(os.path.abspath('/usr/src/app/')) | ||
| + | |||
| + | from double_linked_list.DoubleLinkedListNode import DoubleLinkedListNode # noqa: E402 | ||
| + | from helpers.helper import get_double_linked_list # noqa: E402 | ||
| + | </code> | ||
| + | |||
| + | Реализуйте функцию <color red>solution()</color>, которая принимает на вход список и возвращает также список. Внутри функция должна создавать двусвязный список, после этого поменять первые два элемента двусвязного списка местами и вернуть список всех значений. | ||
| + | |||
| + | Для преобразования списка в двусвязный список используйте функцию <color red>get_double_linked_list()</color>, а чтобы получить список из экземпляра двусвязного списка воспользуйтесь методом <color red>to_array()</color> на объекте двусвязного списка. | ||
| + | <code python> | ||
| + | import solution from solution | ||
| + | |||
| + | items = [[10, 20], 0, -1, ['hey']] | ||
| + | |||
| + | solution(items) # [0, [10, 20], -1, ['hey']] | ||
| + | solution([]) # [] | ||
| + | </code> | ||
| + | |||
| + | </details> | ||
| + | |||
| + | <details> | ||
| + | <summary>**solutions/Solution.java**</summary> | ||
| + | * Создайте в классе пакет <color red>solutions</color> и определите в нем публичный класс <color red>Solution</color> | ||
| + | * Создайте в классе публичный статический метод <color red>swap()</color>, который меняет местами первые два элемента двусвязного списка. Метод принимает в качестве параметра двусвязный список <color red>DoubleLinkedList</color>, меняет местами первые два элемента и возвращает новый связный список | ||
| + | <code java> | ||
| + | import linkedlist.DoubleLinkedList; | ||
| + | |||
| + | DoubleLinkedList list = new DoubleLinkedList(); | ||
| + | list.append(1); | ||
| + | list.append(2); | ||
| + | list.append(3); | ||
| + | list.append(4); | ||
| + | list.toList(); // [1, 2, 3, 4] | ||
| + | |||
| + | DoubleLinkedList swapped = Solution.swap(list); | ||
| + | |||
| + | swapped.toList(); // [2, 1, 3, 4] | ||
| + | </code> | ||
| + | * Добавьте в класс Solution метод run() со следующим кодом: | ||
| + | |||
| + | <code java> | ||
| + | public static java.util.List<Object> run(java.util.List<Object> coll) { | ||
| + | return helpers.Helper.run(coll); | ||
| + | } | ||
| + | </code> | ||
| + | </details> | ||
basics_of_algorithms/doubly_linked_list.1697810469.txt.gz · Последние изменения: 2023/10/20 17:01 — werwolf
Инструменты страницы
Если не указано иное, содержимое этой вики предоставляется на условиях следующей лицензии: CC Attribution-Share Alike 4.0 International
