Сегодня мы поговорим, что такое связный список, что делает его таким особенным, как он работает, чем он отличается от обычного массива (о котором я подробно писал в прошлой статье), и попутно мы увидим, как связные списки хороши для решения определенного класса задач.
Прежде чем мы рассмотрим, что такое связный список, давайте посмотрим, какую проблему он пытается решить. Как бы ни были хороши массивы, есть несколько вещей, которые они не могут сделать.
Во-первых, они медленные, когда дело доходит до вставки спереди, каждый раз, когда нам нужно сделать эту вставку, нам нужно скопировать все наверх, а это занимает линейное время, O(n).Во-вторых, массивы занимают место. Иногда очень много. Каждый раз, когда мы создаем массив, нам нужно указать его размер, и, если он очень большой, мы не используем все это пространство, это может быть расточительно.
Для определенного класса задач нам нужна структура данных, которая очень быстро добавляет элементы вперед, А так же может уменьшаться и увеличиваться и где не нужно указывать размер заранее. На сцену выходит связный список.
Свя́зный спи́сок — базовая динамическая структура данных в информатике, состоящая из узлов, содержащих данные и ссылки («связки») на следующий и/или предыдущий узел списка. Принципиальным преимуществом перед массивом является структурная гибкость: порядок элементов связного списка может не совпадать с порядком расположения элементов данных в памяти компьютера, а порядок обхода списка всегда явно задаётся его внутренними связями.
Эти узлы можно представить себе как вагоны в поезде. Первый узел в списке, называемый "голова"(head), — это место, где мы добавляем элементы в начало нашего списка. Последний узел в списке, "хвост"(tail), он всегда указывает на nil. А все остальное в поезде — это просто связующий вагон с указателем, указывающим на следующий вагон в поезде. В коде это выглядит следующим образом:
class Node {
var data: Int
var next: Node?
init(_ data: Int, _ next: Node? = nil) {
self.data = data
self.next = next
}
}Подробнее
Сначала мы можем представить узел как класс и определить два необходимых нам типа данных, data и text, как int. А next будет следующей ссылкой в узле. Node в данном случае необязателен, потому что это может быть nil, который будет представлять хвост нашего связанного списка. Затем у нас есть простой инициализатор. Обратите внимание, что данные здесь могут быть любыми. В данном случае мы выбрали int, но это может быть строка или любой другой тип данных.
Теперь создаем класс LinkedList
class LinkList {
private var head: Node?
func addFront(_ data: Int) {
let newNode = Node(data)
newNode.next = head
head = newNode
}
func getFirst() -> Int? {
if head == nil {
return nil
}
return head!.data
}
func addBack(_ data: Int) {
let newNode = Node(data)
if head == nil {
head = newNode
return
}
var node = head!
while(node.next != nil) {
node = node.next!
}
node.next = newNode
}
func getLast() -> Int? {
if head == nil {
return nil
}
var node = head!
while(node.next != nil) {
node = node.next!
}
return node.data
}
func insert(position: Int, data: Int) {
if position == 0 {
addFront(data)
return
}
let newNode = Node(data)
var currentNode = head
for _ in 0..<position - 1{
currentNode = currentNode?.next!
}
newNode.next = currentNode?.next
currentNode?.next = newNode
}
func deleteFirst() {
head = head?.next
}
func delete(at position: Int) {
if position == 0 {
self.deleteFirst()
return
}
var nextNode = head
var previousNode: Node?
for _ in 0..<position {
previousNode = nextNode
nextNode = nextNode?.next
}
previousNode?.next = nextNode?.next
}
func deleteLast() {
if head?.next == nil {
head = nil
return
}
var nextNode = head
var previousNode: Node?
while(nextNode?.next != nil) {
previousNode = nextNode
nextNode = nextNode?.next
}
previousNode?.next = nil
}
func delete(data: Int) {
if head == nil { return }
if head!.data == data {
head = head?.next
}
let current = head
while current?.next != nil {
if current?.next?.data == data {
current?.next = current?.next?.next
return
}
}
}
var isEmpty: Bool {
return head == nil
}
func clear() {
head = nil
}
func printLinkedList() {
if head == nil {
print("Empty")
return
}
var result = [Int]()
var node = head
result.append(node!.data)
while node?.next != nil {
result.append(node!.next!.data)
node = node?.next
}
print(result)
}
}
let linkedList = LinkList()Пройдем по каждому методу и посмотри как он работает.
addFront
Главная особенность каждого связного списка - это добавление элемента в начало списка. Мы создаем новый узел, указываем его на head, а затем берем указатель head и указываем его на новый узел. И когда мы это делаем, мы получаем новый узел, вставленный в начало нашего связанного списка. В коде это будет выглядеть следующим образом.
func addFront(_ data: Int) {
let newNode = Node(data)
newNode.next = head
head = newNode
}Подробнее
Сначала принимаем переданные данные и создаем наш новый узел. Затем мы возьмем наш новый узел nodes.next и направим его в head. Мы просто перенаправляем этот указатель на новый узел. В итоге получим новый узел на передней панели.
Эта способность добавлять спереди - постоянное время. O(1) И это то, чего не может сделать массив. Вы не можете добавить новый элемент в массив за постоянное время. Для этого требуется O(n). Метод отлично подходит когда вам нужно быстро добавить что-то на передний план. Следующее, что вы увидите во многих связанных списках - это метод Get First.
func getFirst() -> Int? {
if head == nil {
return nil
}
return head!.data
}Подробнее
Давайте посмотрим, как он работает. Мы хотим получить первый элемент нашего связанного списка. На самом деле, мы просто проверяем две вещи. Во-первых, является ли наш связный список пустым или нулевым? Мы можем определить, пуст ли связанный список, посмотрев на его голову, проверив, равна ли она nil, и если да, то просто вернули nil. Но если у нас есть данные и мы знаем, что head не равна nil, мы можем спуститься, использовать return и просто вернуть данные.
Так мы получим самый первый элемент нашего связного списка, потому что это фронт, который также является O(1). Очень, очень быстро. Далее давайте посмотрим, как мы можем добавить что-то в конец нашего списка с помощью функции Add Back.
addBack
Добавление в конец работает следующим образом. Допустим, мы хотим добавить узел в самый конец, сначала мы создадим наш новый узел. Мы можем сделать проверку в начале. Если бы head был равен nil, мы могли бы просто указать head на новый узел, и все было бы готово. Это был бы одноэлементный связный список. Но если в связанном списке есть другие элементы, то нам нужно пройтись по списку до конца. Мы узнаем, что в конце, когда следующая из самых последних записей будет равна nil. Так мы поймем, что находимся в хвосте. Указываем его следующую точку на новый узел. Теперь у нас есть новый узел, добавленный в хвост. В коде это выглядит следующим образом:
func addBack(_ data: Int) {
let newNode = Node(data)
if head == nil {
head = newNode
return
}
var node = head!
while(node.next != nil) {
node = node.next!
}
node.next = newNode
}Подробнее
Новый узел newNode, который мы хотим создать на основе переданных данных. Если head равна nil, мы просто возьмем этот head, направим ее на новый узел и вернемся. У нас получился одноэлементный связный список. Но если в нем есть другие элементы, и head не равен nil, мы создадим новую переменную node, направим ее на head, а затем просто начнем идти по списк, пока node.next не станет равен nil. Когла следующий указатель равен nil, мы поймем, что находимся в хвосте. Тогда просто берем этот узел next, указываем его на новый узел.
Теперь обратите внимание, что всякий раз, когда вы видите этот цикл while в связанном списке, скорость операции будет O(n). Вы уже знаете что в массиве эта операция происходит быстрее.
Метод getLastможно разобрать по аналогии:
func getLast() -> Int? {
if head == nil {
return nil
}
var node = head!
while(node.next != nil) {
node = node.next!
}
return node.data
}Подробнее
Исходя из того, что мы делали ранее, получение последнего будет очень похожим. Сначала, мы можем просто проверить, равна ли head нулю. Если да, то у нас пустой связный список, поэтому мы можем просто вернуть nil. Но если у нас есть данные в начале, мы можем пройтись по списку. Пройдем по списку пока не попадем в хвост, где next равен nil, а затем просто вернем эти данные.
Insert
Как мы будем вставлять данные в определенную позицию нашего связного списка? Вставка - это как ходьба, только мы должны остановиться в том месте, куда хотим вставить узел, и манипулировать указателями, чтобы они указывали на наш новый узел. Нам не нужно делать никаких сдвигов или копирования. Нам просто идти по списку и манипулировать указателями. Как только мы это сделаем, наш новый узел окажется в нужном месте, прямо посередине. В коде это будет выглядеть следующим образом:
func insert(position: Int, data: Int) {
if position == 0 {
addFront(data)
return
}
let newNode = Node(data)
var currentNode = head
for _ in 0..<position - 1{
currentNode = currentNode?.next!
}
newNode.next = currentNode?.next
currentNode?.next = newNode
}Подробнее
Сначала мы проверим, находимся ли мы в самом начале связанного списка. Если да, то мы можем просто взять данные и добавить их в начало. Больше здесь ничего делать не нужно. Если мы не находимся в начале списка, мы делаем то же самое, что и раньше. Создаем новый узел, определяем переменную current node, равную head, и проходим по связанному списку. Теперь обратите внимание, что мы проходим его немного по-другому. Вместо того чтобы использовать цикл while и просто постоянно проверяя next на наличие nil, в данном случае мы хотим перейти к определенной позиции минус один, постоянно переходя к текущей позиции node.next.
deleteFirst
Когда речь идет об удалении элементов из связанного списка, все очень похоже. Вместо того чтобы вставлять элементы, мы собираемся их пропустить. Давайте рассмотрим метод deleteFirst. Чтобы удалить первый элемент или пропустить самую первую node в нашем связанном списке, все, что нам нужно сделать, это взять head и переназначить head на head.next. Это, по сути, приведет к тому, что head будет указывать на первый элемент, в данном случае на самый первый элемент 1, и пропустит его, заставив его указатель перейти к head.next. В данном случае на элемент два. Очень быстро, без хождения по списку, время O(1). В коде это буквально одна строка.
func deleteFirst() {
head = head?.next
}Подробнее
Мы просто переходим к head, и если в head есть значение, присваиваем его next.
deleteLast
По сути, здесь мы можем использовать предыдущий и следующий узлы, чтобы понять, где мы находимся в нашем цикле. А затем, если мы каким-то образом отслеживаем предыдущий узел в конце, мы можем назначить этот предыдущий узел не для указания на следующий узел. Мы можем пропустить его и указать на nil. Поэтому, по сути, нам нужно выполнить цикл до конца, захватить этот последний узел, а затем присвоить его nill.
func deleteLast() {
if head?.next == nil {
head = nil
return
}
var nextNode = head
var previousNode: Node?
while(nextNode?.next != nil) {
previousNode = nextNode
nextNode = nextNode?.next
}
previousNode?.next = nil
}Подробнее
Прежде всего, вы захотите дойти до самого конца, используя тот же трюк, что и раньше, назначив следующий узел равным head и просто итерируя до конца. Здесь нам не нужна проверка if head nil. Если head равен nil, мы просто не будем никуда переходить. Мы выполняем цикл, пока не дойдем до самого конца, постоянно переходя к следующему узлу. Previos node - это то, как мы можем отслеживать предыдущий узел до того, который находится в конце. Таким образом, когда мы добираемся до конца и следующий узел находится в самом конце. мы можем пропустить этот самый последний узел просто изменяя точку next предыдущего узла и присваивая ей значение nil.
Delete at position
Мы просто переходим к тому месту, где хотим выполнить удаление, а затем пропускаем его, просто переназначая следующий указатель предыдущего узла. . Обратите внимание, что это линейная задача, имеет время выполнения O(n), и в коде она будет выглядеть следующим образом.
func delete(data: Int) {
if head == nil { return }
if head!.data == data {
head = head?.next
}
let current = head
while current?.next != nil {
if current?.next?.data == data {
current?.next = current?.next?.next
return
}
}
}Подробнее
Сначала мы хотим проверить нашу позицию и убедиться, что мы находимся на самом первом элементе нашего связанного списка. Если да, то мы можем просто удалить первый элемент и вернуться. В противном случае мы проделаем тот же трюк, что и с delete last. Мы возьмем наш nextNode и присвоим его head, но мы будем отслеживать предыдущий узел, присвоив ему переменную, а затем перейдем к нашей позиции. Мы будем постоянно обновлять предыдущий узел. Мы будем переходить к тому месту в списке, где нам нужно быть. А затем, как только мы окажемся там, мы просто перейдем к следующему, взяв точку next узла и указав ее на точку next предыдущего узла.
Итак, прежде чем мы завершим нашу работу и рассмотрим, как связанные списки используются в реальном мире, рассмотрим эти два метода isEmpty и clear.
var isEmpty: Bool {
return head == nil
}Если head равен nil, то мы знаем, что у нас пустой связный список. Супер простое вычисление O(1).
func clear() {
head = nil
}Как очистить связный список? Простой способ очистить связный список - это просто взять его head и установить ее равной nil. Здесь у нас может быть сколько угодно элементов связного списка, но если просто присвоить head = nil, то все они исчезнут.
Применение
Связанные списки используются повсеместно в реальном мире. Например связанные списки используются в фреймворке UIKit компании Apple. UIKit с использованием Responder Chain. Для тех из вас, кто не знаком с responder chain, это то, что обеспечивает работу практически всех элементов управления iOS на вашем телефоне. Когда вы создаете приложение, с окном и представлениями, за кулисами есть механизм, который запускает события через эту цепочку ответчиков, и это, по сути, связанный список. Если вам когда-либо приходилось работать с клавиатурой в iOS и вам приходилось отказываться от first responder, то это, по сути, означает, что это вью должно, сделать себя первым, кто будет реагировать в случае прикосновения к экрану. И этот механизм цепочки ответчиков сам по себе является связным списком. Подробнее про Responder Chain.
Отличие от массива
Хорошо, прежде чем мы закончим, давайте просто быстро сравним и поговорим о различиях между связанными списками и массивами. В чем разница?
Во-первых, связанные списки очень быстры, когда мы выполняем операции на фронте. Так что вставка спереди, удаление спереди, получение элемента спереди - все это O(1), очень быстрое преимущество связанных списков. Другое преимущество связных списков - нам не нужно заранее определять их размер. Они могут динамически расти по мере необходимости. Просто путем добавления к задней части. Они могут вырасти до любого размера и всегда будут именно того размера, который нужен. Никакой напрасной траты памяти.
Недостатки связного списка - отсутствие случайного доступа.Вот где массив действительно выигрывает. Возможность использовать индекс и переходить к любому элементу массива за время O(1) очень быстра. Именно поэтому массивы так популярны. Также get и set в связанном списке выполняются за O(n). Если у вас есть цикл или цикл while, в котором нам нужно пройтись по связному списку, знайте, что эта операция будет O(n).
Но связные списки часто используются в стеках и очередях, потому что когда вы попадаете в стеки и очереди, вы увидите, что многие операции мы выполняем на самом первом или переднем элементе, и это только одно место, где вы часто видите связные списки.
Заключение
Итак, когда речь заходит о связных списках, вот что вам нужно знать для технического собеседования.
Все, что находится впереди, O(1), добавить впереди, получить первым, удалить первым, если кто-то спросит вас, в чем преимущество связного списка?
Он действительно хорош в операциях на фронте, O(1).
Каждый раз, когда вам нужно пройтись по чему-либо в любой структуре данных, это O(n).
В связаном списке addLast/getLast/deleteLast - все эти операции будут O(n).
Всегда правильный размер, и как мы уже говорили, нет случайного доступа.
