Инструменты пользователя
basics_of_algorithms:doubly_linked_list
Различия
Здесь показаны различия между двумя версиями данной страницы.
| Предыдущая версия справа и слева Предыдущая версия Следующая версия | Предыдущая версия | ||
|
basics_of_algorithms:doubly_linked_list [2023/10/20 17:12] werwolf [Вставка узла в начало списка] |
basics_of_algorithms:doubly_linked_list [2023/10/20 22:16] (текущий) werwolf [Примеры] |
||
|---|---|---|---|
| Строка 359: | Строка 359: | ||
| Перейдем к вставке узла в конец списка: | Перейдем к вставке узла в конец списка: | ||
| - | <code> | + | <code javascript> |
| insertEnd(value) { | insertEnd(value) { | ||
| if (this.tail == null) { | if (this.tail == null) { | ||
| Строка 372: | Строка 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: | ||
| Строка 386: | Строка 386: | ||
| self.tail = node | self.tail = node | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| Строка 405: | Строка 407: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| class DoublyLinkedList { | class DoublyLinkedList { | ||
| // ... | // ... | ||
| Строка 425: | Строка 429: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Такая вставка симметрична вставке в начало. Разница только в том, что здесь мы должны везде менять местами ''head'' и ''tail'', а также ''previous'' и ''next''. | + | Такая вставка симметрична вставке в начало. Разница только в том, что здесь мы должны везде менять местами <color red>head</color> и <color red>tail</color>, а также <color red>previous</color> и <color red>next</color>. |
| ===== Удаление узла ===== | ===== Удаление узла ===== | ||
| Строка 432: | Строка 437: | ||
| Перейдем к операциям удаления: | Перейдем к операциям удаления: | ||
| - | <code> | + | <code javascript> |
| removeBegin() { | removeBegin() { | ||
| if (this.head == null) { | if (this.head == null) { | ||
| Строка 452: | Строка 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: | ||
| Строка 470: | Строка 476: | ||
| return result | return result | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| Строка 495: | Строка 503: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | ||
| - | <code> | + | <details> |
| + | <summary>Java</summary> | ||
| + | |||
| + | <code java> | ||
| class DoublyLinkedList { | class DoublyLinkedList { | ||
| // ... | // ... | ||
| Строка 521: | Строка 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; | ||
| Строка 532: | Строка 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 | ||
| Строка 540: | Строка 553: | ||
| result = self.head.value | result = self.head.value | ||
| </code> | </code> | ||
| + | </details> | ||
| + | <details> | ||
| + | <summary>PHP</summary> | ||
| - | PHP | + | <code php> |
| - | + | ||
| - | <code> | + | |
| <?php | <?php | ||
| Строка 552: | Строка 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; | ||
| Строка 562: | Строка 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; | ||
| Строка 572: | Строка 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 | ||
| Строка 590: | Строка 610: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| if (head == tail) { | if (head == tail) { | ||
| head = null; | head = null; | ||
| Строка 599: | Строка 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 | ||
| Строка 622: | Строка 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> | ||
| ===== Перебор значений в прямом порядке ===== | ===== Перебор значений в прямом порядке ===== | ||
| Строка 640: | Строка 669: | ||
| **Итератор** — это объект, который одинаковым образом перебирает элементы коллекции, независимо от структуры данных. Скажем, мы можем написать функцию суммирования элементов любой коллекции и вызвать ее для списка: | **Итератор** — это объект, который одинаковым образом перебирает элементы коллекции, независимо от структуры данных. Скажем, мы можем написать функцию суммирования элементов любой коллекции и вызвать ее для списка: | ||
| - | <code> | + | <code javascript> |
| const sum = (items) => { | const sum = (items) => { | ||
| let result = 0; | let result = 0; | ||
| Строка 654: | Строка 683: | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| + | <summary>Python</summary> | ||
| - | <code> | + | <code python> |
| def sum(items): | def sum(items): | ||
| result = 0 | result = 0 | ||
| Строка 666: | Строка 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 | ||
| Строка 685: | Строка 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) { | ||
| Строка 703: | Строка 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> | ||
| Эта функция сможет работать и с нашим двусвязным списком, но для этого нам потребуется реализовать собственный итератор. | Эта функция сможет работать и с нашим двусвязным списком, но для этого нам потребуется реализовать собственный итератор. | ||
| Строка 713: | Строка 748: | ||
| Поэтому двусвязный список должен иметь два итератора — прямой и обратный. Чтобы так сделать, можно возвращать итераторы из методов класса. Например, метод ''fore()'' может создавать и возвращать прямой итератор: | Поэтому двусвязный список должен иметь два итератора — прямой и обратный. Чтобы так сделать, можно возвращать итераторы из методов класса. Например, метод ''fore()'' может создавать и возвращать прямой итератор: | ||
| - | <code> | + | <code javascript> |
| fore() { | fore() { | ||
| let iterator = { | let iterator = { | ||
| Строка 731: | Строка 766: | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| + | <summary>Python</summary> | ||
| - | <code> | + | <code python> |
| def fore(self): | def fore(self): | ||
| current = self.head | current = self.head | ||
| Строка 740: | Строка 776: | ||
| current = current.next | current = current.next | ||
| </code> | </code> | ||
| + | </details> | ||
| + | <details> | ||
| + | <summary>PHP</summary> | ||
| - | PHP | + | <code php> |
| - | + | ||
| - | <code> | + | |
| <?php | <?php | ||
| Строка 756: | Строка 793: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| Использовать итератор можно так: | Использовать итератор можно так: | ||
| - | <code> | + | <code javascript> |
| let list = new DoublyLinkedList(); | let list = new DoublyLinkedList(); | ||
| list.insertBegin(1); | list.insertBegin(1); | ||
| Строка 769: | Строка 807: | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| + | <summary>Python</summary> | ||
| - | <code> | + | <code python> |
| lst = DoublyLinkedList() | lst = DoublyLinkedList() | ||
| lst.insert_begin(1) | lst.insert_begin(1) | ||
| Строка 780: | Строка 819: | ||
| print(sum(lst.fore())) | print(sum(lst.fore())) | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| Строка 794: | Строка 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> { | ||
| // ... | // ... | ||
| Строка 834: | Строка 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> |
| ===== Выводы ===== | ===== Выводы ===== | ||
| Строка 845: | Строка 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.1697811175.txt.gz · Последние изменения: 2023/10/20 17:12 — werwolf
Инструменты страницы
Если не указано иное, содержимое этой вики предоставляется на условиях следующей лицензии: CC Attribution-Share Alike 4.0 International
