Различия

Здесь показаны различия между двумя версиями данной страницы.

--- basics_of_algorithms:linked_list [2023/10/19 14:16]
werwolf [Удаление элемента из начала списка]
+++ basics_of_algorithms:linked_list [2023/10/19 21:39] (текущий)
werwolf [Пример]
@@ Строка 1207: / Строка 1207: @@
 {{ :basics_of_algorithms:333313asdadcac.png?200 |}}
-}===== Удаление элемента из середины или конца списка =====
+===== Удаление элемента из середины или конца списка =====
 Теперь, когда мы умеем вставлять элементы в начало и середину списка, и удалять их из начала списка, удаление узлов из середины не должно представлять для нас проблемы.
@@ Строка 1213: / Строка 1213: @@
 Мы просто скомбинируем написанный нами ранее код:
-<code>
+<code javascript>
 removeAt(index) {
   if (this.head === null) {
@@ Строка 1234: / Строка 1234: @@
 </code>
-Python
+<details>
+<summary>Python</summary>
-<code>
+<code python>
 def remove_at(self, index):
     if self.head is None:
@@ Строка 1255: / Строка 1256: @@
         return value
 </code>
+</details>
+<details>
+<summary>PHP</summary>
-PHP
+<code php>
-<code>
 <?php
@@ Строка 1281: / Строка 1283: @@
 }
 </code>
+</details>
+<details>
+<summary>Java</summary>
-Java
+<code java>
-<code>
 class LinkedList {
     // ...
@@ Строка 1307: / Строка 1310: @@
 }
 </code>
+</details>
 Единственное нововведение по сравнению с предыдущим кодом заключается в том, что при удалении узла из середины, нам нужно просматривать список на два элемента вперед. Если мы хотим удалить последний узел в списке, нам придется вносить изменения в предпоследний — менять там значение ссылки ''next''.
@@ Строка 1312: / Строка 1316: @@
 Поэтому нам приходится, как особый случай, обрабатывать список из одного элемента. Впрочем, эту проверку мы можем совместить с проверкой на удаление из начала:
-<code>
+<code javascript>
 if (index === 0 || this.head.next === null) {
   return remove();
 }
 </code>
+<details>
+<summary>Python</summary>
-Python
+<code python>
-<code>
 elif index == 0 or self.head.next is None:
     return self.remove()
 </code>
+</details>
+<details>
+<summary>PHP</summary>
-PHP
+<code php>
-<code>
 <?php
@@ Строка 1334: / Строка 1339: @@
 }
 </code>
+</details>
+<details>
+<summary>Java</summary>
-Java
+<code java>
-<code>
 else if (index == 0 || head.next == null) {
     return remove();
 }
 </code>
+</details>
 Меняется и условие в цикле. Если раньше мы проверяли, что ''current.next'' не равен ''null'', то теперь мы проверяем ''current.next.next''. Иными словами, вместо ответа на вопрос «есть ли следующий узел в списке», мы отвечаем на вопрос «есть ли узел за следующим узлом».
@@ Строка 1352: / Строка 1359: @@
 | | Массив | Список |
-| Вставка в начало | | |
+| Вставка в начало | O(n) | O(1) |
-| Вставка в середину | | |
+| Вставка в середину | O(n) | O(n) |
-| Вставка в конец | | |
+| Вставка в конец | O(1) | O(n) |
-| Доступ по индексу | | |
+| Доступ по индексу | O(1) | O(n) |
-| Удаление из начала | | |
+| Удаление из начала | O(n) | O(1) |
-| Удаление из середины | | |
+| Удаление из середины | O(n) | O(n) |
-| Удаление из конца | | |
+| Удаление из конца | O(1) | O(n) |
-| Поиск | | |
+| Поиск | O(n) | O(n) |
-| Длина | | |
+| Длина | O(1) | O(n) |
-Всякий раз, когда нам нужно перебирать элементы в массиве или в списке, производительность составляет   . Односвязный список хорош, если нам приходится часто вставлять и удалять элементы —   .
+Всякий раз, когда нам нужно перебирать элементы в массиве или в списке, производительность составляет O(n). Односвязный список хорош, если нам приходится часто вставлять и удалять элементы — O(1).
-Поиск и в массиве и в списке не очень быстрый, всего   .
+Поиск и в массиве и в списке не очень быстрый, всего O(n).
 Образно, массив похож на ежедневник, а связный список — на дневник. В ежедневнике нам важно быстро найти дату, а в дневнике — следующую пустую страницу. Если мы захотим найти все записи на заданную тему, нам придется перечитывать что дневник, что ежедневник.
@@ Строка 1373: / Строка 1380: @@
   * Структура данных — это способ хранения данных в памяти компьютера Одни и те же операции могут быть быстрыми для одних структур и медленными для других
   * Сложные структуры данных — объекты и массивы — хранятся в куче.
+  * Массив не очень хорош, если нам приходиться добавлять или удалять элементы. Связный список хорош
+  * Определение длины и поиск элемента по индексу быстрее в массиве. Массив и связный список похожи на ежедневник и дневник
+===== Пример =====
+Задача:
+**solutions/solution.js**
+Импортируйте в solution.js класс LinkedList и функцию getListFromArray() следующим образом:
+<code javascript>
+import LinkedList from "../lists/LinkedList.js";
+import getListFromArray from "../helpers/helpers.js";
+</code>
+Реализуйте функцию, которая принимает на вход массив и возвращает также массив. Внутри функция должна создавать связный список, в котором узлы будут расположены в обратном порядке и возвращать массив этих значений.
+Для преобразования массива в список используйте функцию getListFromArray(), а чтобы получить массив из списка воспользуйтесь методом toArray() на объекте списка.
+Экспортируйте по умолчанию.
+<code javascript>
+import solution from './solution.js';
+const items = [[10, 20], 0, -1, ['hey']];
+solution(items); // [['hey'], -1, 0, [10, 20]]
+solution([]); // []
+</code>
+<details>
+<summary>**solutions/solution.py**</summary>
+Импортируйте в solution.py класс LinkedList и функцию get_linked_list_from_array следующим образом:
+<code python>
+import os
+import sys
+sys.path.append(os.path.abspath('/usr/src/app/'))
+from lists.LinkedList import LinkedList
+from helpers.helpers import get_linked_list_from_array
+</code>
+Реализуйте функцию solution(), которая принимает на вход список и возвращает также список. Внутри функция должна создавать связный список, в котором узлы будут расположены в обратном порядке и возвращать список этих значений.
+Для преобразования массива в связный список используйте функцию get_linked_list_from_array(), а чтобы получить список из экземпляра связного списка воспользуйтесь методом to_array() на объекте связного списка.
+<code python>
+import solution from solution
+items = [[10, 20], 0, -1, ['hey']]
+solution(items) # [['hey'], -1, 0, [10, 20]]
+solution([]) # []
+</code>
+</details>
+<details>
+<summary>**solutions/solution.php**</summary>
+Импортируйте в solution.php код из файлов LinkedList.php и helpers.php следующим образом:
+<code php>
+<?php
+require_once(__DIR__ . '/../lists/LinkedList.php');
+require_once(__DIR__ . '/../helpers/helpers.php');
+</code>
+Реализуйте функцию solution(), которая принимает на вход массив и возвращает также массив. Внутри функция должна создавать связный список, в котором узлы будут расположены в обратном порядке и возвращать массив этих значений.
+Для преобразования массива в список используйте функцию getListFromArray(), а чтобы получить массив из списка воспользуйтесь методом toArray() на объекте списка.
+<code php>
+<?php
+$items = [[10, 20], 0, -1, ['hey']];
+solution($items); // [['hey'], -1, 0, [10, 20]]
+solution([]); // []
+</code>
+</details>
+<details>
+<summary>**solutions/Solution.java**</summary>
++ Создайте в классе пакет solutions и определите в нем публичный класс Solution
++ Создайте в классе публичный статический метод reverse(), который переворачивает связный список. Метод принимает в качестве параметра связный список LinkedList, переворачивает его и возвращает новый связный список, в котором узлы расположены в обратном порядке:
+<code java>
+import linkedlist.LinkedList;
+LinkedList list = new LinkedList();
+list.append(1);
+list.append(2);
+list.head.value; // 1
+list.tail.value; // 2
+LinkedList reversed = Solution.reverse(list);
+reversed.head.value; // 2
+reversed.tail.value; // 1
+</code>
+Добавьте в класс Solution метод run() со следующим кодом:
+<code java>
+public static java.util.List<Object> run(java.util.List<Object> coll) {
+    return helpers.Helpers.run(coll);
+}
+</code>
+</details>
+----
+**LinkedListNode.js**
+<code javascript>
+export default class LinkedListNode {
+  constructor(value, next = null) {
+    this.value = value;
+    this.next = next;
+  }
+}
+</code>
+<details>
+<summary>python</summary>
+<code python>
+class LinkedListNode:
+    def __init__(self, value, next=None):
+        self.value = value
+        self.next = next
+</code>
+</details>
+<details>
+<summary>php</summary>
+<code php>
+<?php
+class LinkedListNode {
+  public function __construct($value, $next = null)
+  {
+    $this->value = $value;
+    $this->next = $next;
+  }
+}
+</code>
+</details>
+<details>
+<summary>java</summary>
+<code java>
+package lists;
+public class LinkedListNode {
+    public Object value;
+    public LinkedListNode next = null;
+    LinkedListNode(Object value, LinkedListNode next) {
+        this.value = value;
+        this.next = next;
+    }
+    LinkedListNode(Object value) {
+        this.value = value;
+    }
+}
+</code>
+</details>
+----
+**LinkedList.js**
+<code javascript>
+import LinkedListNode from './LinkedListNode.js';
+export default class LinkedList {
+  constructor() {
+    this.head = null;
+    this.tail = null;
+  }
+  prepend(value) {
+    // Делаем новый узел головой
+    const newNode = new LinkedListNode(value, this.head);
+    this.head = newNode;
+    // Если нет хвоста, этот узел будет и хвостом
+    if (!this.tail) {
+      this.tail = newNode;
+    }
+    return this;
+  }
+  append(value) {
+    const newNode = new LinkedListNode(value);
+    // Если нет головы, этот узел будет головой
+    if (!this.head) {
+      this.head = newNode;
+      this.tail = newNode;
+      return this;
+    }
+    // Присоеденяем новый узел к концу, делаем его хвостом
+    this.tail.next = newNode;
+    this.tail = newNode;
+    return this;
+  }
+  delete(value) {
+    if (!this.head) {
+      return null;
+    }
+    let deletedNode = null;
+    // Проверяем с головы какие ноды надо удалить
+    while (this.head && this.head.value === value) {
+      deletedNode = this.head;
+      this.head = this.head.next;
+    }
+    let currentNode = this.head;
+    // Если у головы не нашли, проверяем остальные значения в списке
+    if (currentNode !== null) {
+      while (currentNode.next) {
+        if (currentNode.next.value === value) {
+          deletedNode = currentNode.next;
+          currentNode.next = currentNode.next.next;
+        } else {
+          currentNode = currentNode.next;
+        }
+      }
+    }
+    // Проверяе хвост
+    if (this.tail.value === value) {
+      this.tail = currentNode;
+    }
+    return deletedNode;
+  }
+  find(value) {
+    if (!this.head) {
+      return null;
+    }
+    let currentNode = this.head;
+    // Перебираем список с головы, первое найденное значение возвращаем
+    while (currentNode) {
+      if (value !== undefined && currentNode.value === value) {
+        return currentNode;
+      }
+      // Делаем текущей следующий элемент списка
+      currentNode = currentNode.next;
+    }
+    return null;
+  }
+  isEmpty() {
+    return this.head === undefined && this.tail === undefined;
+  }
+  toArray() {
+    const result = [];
+    if (!this.head) {
+      return result;
+    }
+    let currentNode = this.head;
+    while (currentNode) {
+      if (currentNode.value !== undefined) {
+        result.push(currentNode.value);
+      }
+      currentNode = currentNode.next;
+    }
+    return result;
+  }
+}
+</code>
+<details>
+<summary>python</summary>
+<code python>
+from lists.LinkedListNode import LinkedListNode
+class LinkedList:
+    def __init__(self):
+        self.head = None
+        self.tail = None
+    def prepend(self, value):
+        # Делаем новый узел головой
+        new_node = LinkedListNode(value, self.head)
+        self.head = new_node
+        # Если нет хвоста, этот узел будет и хвостом
+        if not self.tail:
+            self.tail = new_node
+        return self
+    def append(self, value):
+        new_node = LinkedListNode(value)
+        # Если нет головы, этот узел будет головой
+        if not self.head:
+            self.head = new_node
+            self.tail = new_node
+            return self
+        # Присоеденяем новый узел к концу, делаем его хвостом
+        self.tail.next = new_node
+        self.tail = new_node
+        return self
+    def delete(self, value):  # noqa: C901
+        if not self.head:
+            return None
+        deleted_node = None
+        # Проверяем с головы какие ноды надо удалять
+        while self.head and self.head.value == value:
+            deleted_node = self.head
+            self.head = self.head.next
+        current_node = self.head
+        # Если у головы не нашли, проверяем остальные значения в списке
+        if current_node is not None:
+            while current_node.next:
+                if current_node.next.value == value:
+                    deleted_node = current_node.next
+                    current_node.next = current_node.next.next
+                else:
+                    current_node = current_node.next
+        # Проверяем хвост
+        if self.tail.value == value:
+            self.tail == current_node
+        return deleted_node
+    def find(self, value):
+        if not self.head:
+            return None
+        current_node = self.head
+        # Перебираем список с головы, первое найденное значение возвращаем
+        while current_node:
+            if current_node.value is not None and current_node.value == value:
+                return current_node
+            # Делаем текущей следующий элемент списка
+            current_node = current_node.next
+        return None
+    def is_empty(self):
+        return self.head is None and self.tail is None
+    def to_array(self):
+        result = []
+        if self.head is None:
+            return result
+        current_node = self.head
+        while current_node:
+            if current_node.value is not None:
+                result.append(current_node.value)
+            current_node = current_node.next
+        return result
+</code>
+</details>
+<details>
+<summary>php</summary>
+<code php>
+<?php
+require_once(__DIR__ . '/LinkedListNode.php');
+class LinkedList
+{
+    public function __construct()
+    {
+        $this->head = null;
+        $this->tail = null;
+    }
+    public function prepend($value)
+    {
+        // Делаем новый узел головой
+        $newNode = new LinkedListNode($value, $this->head);
+        $this->head = $newNode;
+        // Если нет хвоста, этот узел будет и хвостом
+        if (!$this->tail) {
+            $this->tail = $newNode;
+        }
+        return $this;
+    }
+    public function append($value)
+    {
+        $newNode = new LinkedListNode($value);
+        // Если нет головы, этот узел будет головой
+        if (!$this->head) {
+            $this->head = $newNode;
+            $this->tail = $newNode;
+            return $this;
+        }
+        // Присоединяем новый узел к концу, делаем его хвостом
+        $this->tail->next = $newNode;
+        $this->tail = $newNode;
+        return $this;
+    }
+    public function delete($value)
+    {
+        if (!$this->head) {
+            return null;
+        }
+        $deletedNode = null;
+        // Проверяем с головы какие ноды надо удалить
+        while ($this->head && $this->head->value === $value) {
+            $deletedNode = $this->head;
+            $this->head = $this->head->next;
+        }
+        $currentNode = $this->head;
+        // Если у головы не нашли, проверяем остальные значения в списке
+        if ($currentNode !== null) {
+            while ($currentNode->next) {
+                if ($currentNode->next->value === $value) {
+                    $deletedNode = $currentNode->next;
+                    $currentNode->next = $currentNode->next->next;
+                } else {
+                    $currentNode = $currentNode->next;
+                }
+            }
+        }
+        // Проверяем хвост
+        if ($this->tail->value === $value) {
+            $this->tail = $currentNode;
+        }
+        return $deletedNode;
+    }
+    public function find($value)
+    {
+        if (!$this->head) {
+            return null;
+        }
+        $currentNode = $this->head;
+        // Перебираем список с головы, первое найденное значение возвращаем
+        while ($currentNode) {
+            if ($value !== null && $currentNode->value === $value) {
+                return $currentNode;
+            }
+            // Делаем текущей следующий элемент списка
+            $currentNode = $currentNode->next;
+        }
+        return null;
+    }
+    public function isEmpty()
+    {
+        return $this->head === null && $this->tail === null;
+    }
+    public function toArray()
+    {
+        $result = [];
+        if (!$this->head) {
+            return $result;
+        }
+        $currentNode = $this->head;
+        while ($currentNode) {
+            if ($currentNode->value !== null) {
+                $result[] = $currentNode->value;
+            }
+            $currentNode = $currentNode->next;
+        }
+        return $result;
+    }
+}
+</code>
+</details>
+<details>
+<summary>java</summary>
+<code java>
+package lists;
+import java.util.ArrayList;
+import java.util.List;
+public class LinkedList {
+    public LinkedListNode head = null;
+    public LinkedListNode tail = null;
+    public LinkedList prepend(Object value) {
+        LinkedListNode newNode = new LinkedListNode(value, head);
+        head = newNode;
+        if (tail == null) {
+            tail = newNode;
+        }
+        return this;
+    }
+    public LinkedList append(Object value) {
+        LinkedListNode newNode = new LinkedListNode(value);
+        if (head == null) {
+            head = newNode;
+            tail = newNode;
+            return this;
+        }
+        tail.next = newNode;
+        tail = newNode;
+        return this;
+    }
+    public LinkedListNode delete(Object value) {
+        if (head == null) {
+            return null;
+        }
+        LinkedListNode deletedNode = null;
+        while (head != null && head.value == value) {
+            deletedNode = head;
+            head = head.next;
+        }
+        LinkedListNode currentNode = head;
+        if (currentNode != null) {
+            while (currentNode.next != null) {
+                if (currentNode.next.value == value) {
+                    deletedNode = currentNode.next;
+                    currentNode.next = currentNode.next.next;
+                } else {
+                    currentNode = currentNode.next;
+                }
+            }
+        }
+        if (tail.value == value) {
+            tail = currentNode;
+        }
+        return deletedNode;
+    }
+    public LinkedListNode find(Object value)
+    {
+        if (head == null) {
+            return null;
+        }
+        LinkedListNode currentNode = head;
+        while (currentNode != null) {
+            if (value != null && currentNode.value == value) {
+                return currentNode;
+            }
+            currentNode = currentNode.next;
+        }
+        return null;
+    }
+    public boolean isEmpty()
+    {
+        return head == null && tail == null;
+    }
+    public List<Object> toList()
+    {
+        List<Object> result = new ArrayList<>();
+        if (head == null) {
+            return result;
+        }
+        LinkedListNode currentNode = head;
+        while (currentNode != null) {
+            if (currentNode.value != null) {
+                result.add(currentNode.value);
+            }
+            currentNode = currentNode.next;
+        }
+        return result;
+    }
+}
+</code>
+</details>
+----
+**helpers.js**
+<code javascript>
+import LinkedList from '../lists/LinkedList.js';
+const getListFromArray = (collection) => {
+  const linkedList = new LinkedList();
+  // eslint-disable-next-line
+  for (const item of collection) {
+    linkedList.append(item);
+  }
+  return linkedList;
+};
+export default getListFromArray;
+</code>
+<details>
+<summary>python</summary>
+<code python>
+from lists.LinkedList import LinkedList
+def get_linked_list_from_array(items):
+    linked_list = LinkedList()
+    for value in items:
+        linked_list.append(value)
+    return linked_list
+</code>
+</details>
+<details>
+<summary>php</summary>
+<code php>
+<?php
+require_once(__DIR__ . '/../lists/LinkedList.php');
+function getListFromArray($collection)
+{
+    $linkedList = new LinkedList();
+    foreach ($collection as $item) {
+        $linkedList->append($item);
+    }
+    return $linkedList;
+}
+</code>
+</details>
+<details>
+<summary>java</summary>
+<code java>
+package helpers;
+import lists.LinkedList;
+import java.util.List;
+import solutions.Solution;
+public class Helpers {
+    public static LinkedList getLinkedList(List<Object> collection) {
+        LinkedList list = new LinkedList();
+        for (Object item : collection) {
+            list.append(item);
+        }
+        return list;
+    }
+    public static List<Object> run(List<Object> coll) {
+        LinkedList list = Helpers.getLinkedList(coll);
+        LinkedList reversed = Solution.reverse(list);
+        return reversed.toList();
+    }
+}
+</code>
+</details>
+----
+**solution.js**
+<code javascript>
+import LinkedList from '../lists/LinkedList.js';
+import getListFromArray from '../helpers/helpers.js';
+export default (collection) => {
+  const list = getListFromArray(collection);
+  const reversedList = new LinkedList();
+  if (!list.head) {
+    return reversedList.toArray();
+  }
+  reversedList.prepend(list.head.value);
+  let nextNode = list.head.next;
+  while (nextNode !== null) {
+    reversedList.prepend(nextNode.value);
+    nextNode = nextNode.next;
+  }
+  return reversedList.toArray();
+};
+</code>
+<details>
+<summary>python</summary>
+<code python>
+import os
+import sys
+sys.path.append(os.path.abspath('/usr/src/app/'))
+from lists.LinkedList import LinkedList  # noqa: E402
+from helpers.helpers import get_linked_list_from_array  # noqa: E402
+def solution(items):
+    linked_list = get_linked_list_from_array(items)
+    reversed_list = LinkedList()
+    if not linked_list.head:
+        return reversed_list.to_array()
+    reversed_list.prepend(linked_list.head.value)
+    next_node = linked_list.head.next
+    while next_node:
+        reversed_list.prepend(next_node.value)
+        next_node = next_node.next
+    return reversed_list.to_array()
+</code>
+</details>
+<details>
+<summary>php</summary>
+<code php>
+<?php
+require_once(__DIR__ . '/../lists/LinkedList.php');
+require_once(__DIR__ . '/../helpers/helpers.php');
+function solution($collection)
+{
+    $list = getListFromArray($collection);
+    $reversedList = new LinkedList();
+    if ($list->head === null) {
+        return $reversedList->toArray();
+    }
+    $reversedList->prepend($list->head->value);
+    $nextNode = $list->head->next;
+    while ($nextNode !== null) {
+        $reversedList->prepend($nextNode->value);
+        $nextNode = $nextNode->next;
+    }
+    return $reversedList->toArray();
+}
+</code>
+</details>
+<details>
+<summary>java</summary>
+<code java>
+package solutions;
+import lists.LinkedList;
+import lists.LinkedListNode;
+public class Solution {
+    public static LinkedList reverse(LinkedList coll) {
+        LinkedList reversed = new LinkedList();
+        if (coll.head == null) {
+            return reversed;
+        }
+        reversed.prepend(coll.head.value);
+        LinkedListNode nextNode = coll.head.next;
+        while(nextNode != null) {
+            reversed.prepend(nextNode.value);
+            nextNode = nextNode.next;
+        }
+        return reversed;
+    }
+    public static java.util.List<Object> run(java.util.List<Object> coll) {
+        return helpers.Helpers.run(coll);
+    }
+}
+</code>
+</details>

Инструменты пользователя

Инструменты сайта

Различия

Инструменты страницы