Без дальнейших церемоний, очень разрекламированный и до сих пор не доставленный пост о связанных списках! Связанные списки — одна из самых фундаментальных и важных структур данных в компьютерных науках, и будьте уверены, если вы проходите собеседование на должность программиста, от вас ожидают, что вы будете знать, как их реализовать, работать с ними и описывать некоторые факты. о них. Но, во-первых, зачем использовать связанный список?

Как начинающий программист, вы склонны всякий раз, когда вас просят представить данные в виде списка, бежать к резервному, старому верному, массиву. И это правильно. Массивы великолепны... для некоторых приложений. Учтите, однако, стоимость добавления элемента в массив. Если вы добавите элемент в конце, это будет операция O(1). Просто найдите последний элемент, затем добавьте еще один. Великолепный. Однако что, если вы хотите добавить элемент в какое-то место, отличное от конечного индекса? Вы должны найти индекс, заменить элемент и отодвинуть каждый последующий элемент назад на один индекс, операция O (n). Именно здесь на помощь приходят связанные списки.

Связанный список, как следует из его простого названия, представляет собой список элементов, в котором каждый элемент «связывается» со следующим элементом в списке через указатель. Существуют разные реализации связанных списков, но общая идея заключается в том, что каждый «узел» в списке хранит свои данные, а также указатель на следующий узел. Связанные списки могут быть односвязными, и в этом случае они работают точно так, как описано здесь, или двусвязными, что означает, что они также сохраняют указатель на предыдущий узел в списке. Они почти всегда имеют головной указатель, т. е. указатель на первый узел в списке, и могут опционально иметь хвостовой указатель, т. е. указатель на последний узел. В отличие от массивов, добавление и удаление элементов в начале — это простая операция O(1), псевдокод для которой выглядит так (предполагая двусвязный список).

deletenode(node) { 
	 node.prev.next = node.next
}

Другое основное преимущество связанных списков в отличие от массивов заключается в том, что массивы имеют фиксированную длину, что требует от вас создания нового массива, копирования всех данных из исходного массива и добавления новых данных каждый раз, когда длина массива превышена. , связанные списки могут расти безгранично, пока память компьютера не будет заполнена. Вообще говоря, связанные списки поддерживают добавление и удаление элементов в начале, добавление и удаление элементов в конце, добавление и удаление элементов до и после заданного элемента, поиск первого элемента, поиск последнего элемента, поиск любого элемента и проверку того, список пуст.

Добавление, поиск и удаление элемента в начале всегда выполняются за O(1), а псевдокод для добавления элемента в начало отдельного списка выглядит следующим образом:

pushFront(key) {  
   if head == null ; error: empty list
   key.next = head.next 
	 head.next = key 
}

Добавление и поиск элемента в конце — это операции O(n) при отсутствии хвостового указателя и O(1) при наличии хвостового указателя. В односвязных списках удаление последнего элемента равно O(n) с хвостовым указателем или без него, поскольку необходимо перебирать список до тех пор, пока не будет достигнут предпоследний элемент, чтобы установить его указатель в значение null. Это можно сократить до O(1) в двусвязном списке с хвостовым указателем, так как tail.prev.next можно просто установить равным нулю. Псевдокод для удаления последнего элемента в односвязном списке выглядит так

popBack() { 
   if head == null ; error: empty list
    node = head
    while node.next.next != tail 
        node = node.next  
    node.next = null 
		tail = node 
}

Поиск заданного элемента в любом связанном списке без указателя на этот элемент — это O(n), требующее итерации к этому узлу в списке. Добавление элемента после заданного элемента равно O(1) и добавление перед элементом равно O(n) в односвязном списке и O(1) в двусвязном списке по той же причине, что и для удаления последний элемент. Стирание данного элемента без указателя на этот элемент — это O(n) в любом связанном списке, а проверка того, пуст ли список, — это простая операция O(1), т. е. проверка того, является ли указатель на начало нулевым.

Особый интерес представляет нахождение данного узла в связанном списке. В массиве поиск элемента — это операция O(1), просто вопрос поиска правильного индекса. В связанном списке это становится O(n), поэтому в этом смысле массивы работают лучше. Фактически, эта дихотомия между массивами и связанными списками, идея о том, что массивы лучше находят элементы, а связанные списки лучше добавляют и удаляют их, является центральной точкой анализа при выборе того, что использовать. Как правило, используйте массив, когда элементы нужно будет часто находить, и связанный список, когда элементы будут часто добавляться и удаляться спереди или сзади. По этой причине связанные списки являются распространенной реализацией стеков и очередей, которые обсуждались в предыдущем сообщении блога. Они также используются при обработке коллизий в хэш-таблице, о чем будет рассказано в следующем посте.

И последнее замечание о связанных списках: при работе с ними в большинстве случаев используйте односвязные списки. Если вы можете реализовать и работать с односвязным списком, то вы можете реализовать и работать с двусвязным списком, но нельзя предполагать обратное.

Спасибо за чтение, и следите за новостями, чтобы узнать больше о жаргоне CS. Сегодняшние слова мудрости приходят к нам аж из Бхагавад-гиты -
«В бою, в лесу, у обрыва в горах, На темном великом море, Среди дротиков и стрел, Во сне , в смятении, в глубине стыда, Добрые дела, совершенные человеком, защищают его ».