На видео более подробное объяснение каждого решения
Постановка задачи
Ссылка на задачу: https://leetcode.com/problems/middle-of-the-linked-list
Дан указатель head на начало односвязного списка, нужно вернуть средний узел списка.
Если средних узлов два, нужно вернуть второй средний узел.
1. Решение с использованием массива
Подход
Преобразование списка в массив упрощает доступ к элементам по индексу. Мы проходим по списку и сохраняем все узлы в массив, так как доступ по индексу в массиве осуществляется за постоянное время O(1). После этого мы легко можем найти средний элемент, просто взяв элемент по индексу len(items) // 2
Алгоритм
Пройти по списку и сохранить все его элементы в массив.
Определить индекс среднего элемента массива.
Вернуть элемент, находящийся по этому индексу.
Код решения
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
items = []
while head: #None
items.append(head)
head = head.next
return items[len(items) // 2]Сложность алгоритма
• По времени: O(n), где n — количество элементов в списке.
• По памяти: O(n), так как мы сохраняем все элементы списка в массив.
Визуализация
Исходный список:
1 -> 2 -> 3 -> 4 -> 5Массив после прохождения по списку:
[1, 2, 3, 4, 5]Индекс среднего элемента:
5 // 2 = 2Средний элемент в массиве: 3
0 1 2 3 4
[1, 2, {3}, 4, 5]
2. Решение с подсчетом длины списка
Подход
В этом подходе мы сначала считаем количество элементов в списке, чтобы точно знать, сколько узлов в нем содержится. Считая количество узлов, мы можем определить индекс среднего элемента как length // 2. Затем, проходя список во второй раз, мы останавливаемся на этом индексе и возвращаем соответствующий узел.
Алгоритм
Пройти по списку и подсчитать количество элементов.
Пройти по списку снова до среднего элемента и вернуть его.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
count = self.count(head)
for _ in range(count // 2):
head = head.next
return head
def count(self, head):
res = 0
while head:
res += 1
head = head.next
return resСложность алгоритма
• По времени: O(n), где n — количество элементов в списке.
• По памяти: O(1), так как мы не используем дополнительную память.
Визуализация
Исходный список:
1 -> 2 -> 3 -> 4 -> 5-
Проход 1: Подсчет длины списка
• Длина списка:
5 Средний индекс:
5 // 2 = 2-
Проход 2: Получение среднего элемента
• Проходим через узлы до индекса, который мы вычислили на 3 шаге:
1 (0), 2 (1), 3 (2) Средний элемент: 3
3. Решение с использованием метода быстрого и медленного указателя
Подход
Этот метод использует два указателя: быстрый и медленный. Быстрый указатель движется по два узла за раз, а медленный - по одному. Когда быстрый указатель достигает конца списка или выходит за пределы списка, медленный находится на середине. Это происходит потому, что быстрый указатель проходит вдвое больше узлов за одно и то же время. Этот метод эффективен, так как требует только одного прохода по списку и использует минимальное дополнительное пространство.
Алгоритм
Инициализировать два указателя, быстрый и медленный, которые указывают на начало списка.
Перемещать медленный указатель на один шаг, а быстрый на два шага, пока быстрый указатель не достигнет конца списка.
Когда быстрый указатель достигнет конца списка или выходит за его пределы, медленный указатель будет находиться на среднем элементе.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slowСложность алгоритма
• По времени: O(n), где n — количество элементов в списке.
• По памяти: O(1), так как используем только два указателя.
Визуализация
Исходный список:
1 -> 2 -> 3 -> 4 -> 5-
Начальное положение:
• Медленный указатель (S) на 1
• Быстрый указатель (F) на 1
-
Шаг 1:
•
S: 2(двигается на 1 узел вперед)•
F: 3(двигается на 2 узла вперед)• Список:
1 -> [2 (S)] -> 3 -> [4 (F)] -> 5 -
Шаг 2:
•
S: 3(двигается на 1 узел вперед)•
F: 5(двигается на 2 узла вперед)• Список:
1 -> 2 -> [3 (S)] -> 4 -> [5 (F)] -
Конец:
• Быстрый указатель (F) достигает конца списка или выходит за его пределы.
• Медленный указатель (S) находится на 3, который и является средним элементом.
Итоговый результат: Средний элемент списка 3.
Комментарии (96)
IvanZaycev0717
04.08.2024 10:48Хочу поинтеросоваться у автора - каким образом была выбрана задача? Когда я проходил собеседование, мне сказали написать random.randrange (3000) и что выведится в консоль, то и решай.
idsulik Автор
04.08.2024 10:48В первую очередь подбираю задачи, так чтобы объяснить какую-то тему, которая будет полезна на интервью, на примере этой задачи или саму задачу, которая часто встречается на интервью.
У меня на канале идут подряд задачи связанные с какой-то темой(two pointers, sliding window), сейчас перешел на тему fast and slow pointer и на примере этой задачи объяснил, что это такое + объяснил что такое связный список и какие они бывают(на видео).
Мне вот давали Reverse Linked List(фаанг в РФ) и десятки других задач(easy/medium/hard).
AlexSky
04.08.2024 10:48Три года назад была эта задача, когда собеседовался на нынешнюю работу. На нервах от собеседования (очень мало на них ходил) решил её каким-то безумным способом с двумя указателями. Нормальное решение пришло минут через 5 после окончания этапа собеседования. Было стыдно, но в итоге работу и так получил.
idsulik Автор
04.08.2024 10:48речь про Reverse задачу?) я тоже с горем пополам решил, с помощью интервьюера, потому что трудно в голове держать связи между нодами
AlexSky
04.08.2024 10:48Да, реверс.
Решил сам, но помучился изрядно. Надо было сначала успокоиться и подумать, а я сразу рванул код писать
idsulik Автор
04.08.2024 10:48поэтому перед интервью всегда просят приступать к коду в самую последнюю очередь) сначала вопросы, потом объяснение своей идеи и только после приступать к решению
NevoWin
04.08.2024 10:48+63 вариант не лучше, чем второй. В 3 варианте за один проход, но в этом 1 проходе нужно двигать 2 указателя, с точки зрения количества операций будет одинаково со 2 вариантом.
Единственное, что в 3 варианте более красивая и элегантная идея.
Но 2 вариант проще в понимании и чтении кода в будущем.
Я бы взял на работу того, кто не усложняет код, где это не требуется, а пишет более просто.
wataru
04.08.2024 10:48+1Второй и третий варинаты имеют одинаковое количество сравнений и обращений к памяти.
Но из-за архитектурных ньюансов, сложно сказать, какой будет быстрее.
Третий вариант имеет меньше условных переходов (n/2 в случае одного цикла и n+n/2 в случае двух). Но это хорошо предсказываемые условные переходы на следующую итерацию цикла, поэтому они относительно дешевые.
С другой стороны, во втором варианте циклы короче.
С точки зрения кода второй вариант лучше, я с вами согласен.
idsulik Автор
04.08.2024 10:48Согласен, что третий вариант довольно хитрий и да, второй вариант проще в понимании
SquareRootOfZero
04.08.2024 10:48+1Идея 3 варианта довольно проста, только "у кого-то это щёлкает, а у кого-то не щёлкает". Предварить реализацию коротеньким комментарием о том, что происходит и почему это работает, и по лёгкости понимания и чтения оно, на мой взгляд, не только не уступит второму варианту, а даже его превзойдёт.
idsulik Автор
04.08.2024 10:48ну третий вариант, думаю, ненадолго остановит человека, чтобы действительно понять, что происходит, когда как второй вариант более интуитивный
SquareRootOfZero
04.08.2024 10:48+1Начнём с того, что сама постановка задачи, возникни она не на интервью, а в реальных условиях, ненадолго остановит человека, чтобы действительно понять: а) зачем нужно находить середину связного списка? б) зачем выбирать именно связный список как упорядоченный контейнер для данных, у которого надо находить серединный элемент. Что-то тут, наверное, придумать можно, как-то обосновать - но ненадолго остановит.
С другой стороны, а зачем человеку действительно понимать, что происходит? Есть функция, возвращает срединный элемент, вот аргумент(ы), вот возвращаемое значение. Работает? Работает. Ну и не трожь, пускай работает. Можно, опять-таки, представить ситуацию, когда понадобилось действительно понять - прошёл, допустим, год, два, три, и почему-то понадобилось переделать. Но не по нескольку же раз на дню человек будет читать именно эту часть кода, каждый раз ненадолго останавливаясь, чтобы понять.
idsulik Автор
04.08.2024 10:48ну порой нужно понимать код, а не только надеяться на название метода) ну или проверить разные кейсы, что если пустой список, что если четное или нечетное количество нод
x89377
04.08.2024 10:48Хорошо было бы добавить голосование, что бы каждый мог выбрать правильный вариант № 3.
idsulik Автор
04.08.2024 10:48Самый оптимальный вариант третий) а две другие лишь подводят к третьему
aamonster
04.08.2024 10:48+3Вы проверили? Асимптотика у второго и третьего одинаковая, стоило сделать бенчмарк.
В боевом коде не задумываясь писал бы второй ("пиши код так, будто поддерживать его будет склонный к насилию психопат, знающий, где ты живёшь").
idsulik Автор
04.08.2024 10:48стоило сделать бенчмарк
это уж точно, как будет свободное время надо будет сделать
kibergus
04.08.2024 10:48Быстрый и медленный указатель имеет ровно такую же сложность, как и с подсчетом длины. Оба требует два прохода.
idsulik Автор
04.08.2024 10:48согласен, в случае с быстрым и медленным указателем, проходим каждый элемент 1.5 раз, но в рамках одного цикла
aamonster
04.08.2024 10:48Быстрый и медленный указатель, вероятно, тиснуты из более сложной задачки про кольцевой список :-)
idsulik Автор
04.08.2024 10:48не понял про кольцевой список
aamonster
04.08.2024 10:48Google "поиск цикла в односвязном списке" или "алгоритм черепахи и зайца".
Вкратце: у нас есть односвязный список неизвестной длины, возможно, он с какого-то места зацикливается. Надо узнать, зацикливается ли, и определить длину цикла и точку входа в него.
SpiderEkb
04.08.2024 10:48+1Проверка списка на "зацикливание". Классически решается через "быстрый" и "медленный" указатели.
SquareRootOfZero
04.08.2024 10:48По Big-O такую же, одинаковое количество переходов к следующему элементу, но в третьем варианте отсутствуют операции сравнения текущего индекса указателя с вычисленной длиной списка, делённой пополам. Впрочем, выше @wataru, по-моему, уже написал про то же самое.
kibergus
04.08.2024 10:48+2Если хочется извращений, можно съэкономить половину итераций на втором итераторе: заводим два допонительных итератора i1, i2. Когда основной прохтдит через степень двойки (2, 4, 8, 16,...) сохраняем:
i1 = i2
i2 = i
Теперь когда дойдем до конца списка у нас есть закешированный итератор, который между 1/4 и 1/2 длины.
Но общая сложность все равно линия.
Alexandroppolus
04.08.2024 10:48По сабжу вспоминается забавная, но специфичная для С/С++ задачка в жанре "ненормальное программирование". Надо сначала ввести с клавиатуры N чисел (N произвольное, но не слишком большое), потом вывести их в том же порядке. По условию, нельзя использовать массивы и динамически выделяемую память (кучу).
idsulik Автор
04.08.2024 10:48получилось решить?)
wataru
04.08.2024 10:48Обязательно вывести потом, а не во время ввода? N задается, или читаем до условного перевода строки?
Можно ли исползовать N переменных, раз оно небольшое? Можно ли использовать препроцессор?
idsulik Автор
04.08.2024 10:48Можно ли исползовать N переменных, раз оно небольшое? Можно ли использовать препроцессор?
first_input
second_input
third_input
n_input
это будет довольно интересный подход)
Alexandroppolus
04.08.2024 10:48Обязательно вывести потом, а не во время ввода?
Разумеется, в этом и суть ) Сначала читаем N, потом читаем числа N раз, потом выводим тоже N штук.
Это самое N может быть равно несколько тысяч, заваливать переменными не вариант.. По поводу препроцессора не помню, но вполне можно без него. Эта задача явно не о препроцессоре.
wataru
04.08.2024 10:48Принимается ли хак с рекурсивной функцией и доступом к локальным переменным выше по стеку, эмулируя таким образом массив? Надо только смещение между двумя копиями локальной переменной узнать. Это можно сделать, передав указатель на локальную переменную в рекурсивный вызов.
Еще можно эти локальные переменные организовать в односвязный список. Тогда локальная переменная будет пара число+указатель на предыдущую. В рекурсивный вызов передаем указатель на локальную переменную (которая последняя нода в списке) + указатель на первую локальную переменную. в локальную переменную перед этим читаем и дописываем ее в список. В самом нижнем рекурсивном вызове выводим список.
Еще, кажется, можно было бы написать вариадическую рекурсивную функцию, но пока не понятно, как можно передать дальше все параметры и еще один int в конце.
Alexandroppolus
04.08.2024 10:48можно эти локальные переменные организовать в односвязный список.
Я так решал. Это честный вариант без хаков с адресами. Потому и вспомнил задачу в теме про списки.
wataru
04.08.2024 10:48Ох, не люблю я эти задачи с искусственными ограничениями.
Alexandroppolus
04.08.2024 10:48+1Согласен, жанр на любителя. Это вроде металлических головоломок, у них тоже ограничения - не использовать плоскогубцы, например.
wataru
04.08.2024 10:48Не, это же совсем искусственные ограничения. Если и брать металлические головоломки, то можно их собирать только в варежках. Или только смотря в зеркало.
Вот в этой задаче, например, массив фактически есть. Только он размазан по стеку.
Foror
04.08.2024 10:48А зачем вы решаете подобные задачи на собеседовании? Вам там доступ к гугл и чатгпт запрещают? А на работе потом доступ в гугл и чатгпт тоже только по спец пропускам?
P.S. Как в LinkedList найти средний элемент начиная перебирать с head?Чтобы найти средний элемент в связном списке (LinkedList), начиная с головы (head), можно использовать два указателя: один будет двигаться на один элемент за раз (slow), а другой — на два элемента за раз (fast). Когда указатель fast достигнет конца списка, указатель slow будет находиться на среднем элементе. Вот пример алгоритма на Python:
class Node:
def init(self, data):
self.data = data
self.next = Noneclass LinkedList:
def init(self):
self.head = Nonedef find_middle(self): slow = self.head fast = self.head while fast and fast.next: slow = slow.next fast = fast.next.next return slow.data if slow else NoneВ этом коде метод find_middle возвращает значение среднего элемента. Если список пуст, он вернет None.
wataru
04.08.2024 10:48Да, на интервью не дают доступа к интернету, ибо проверяют ваши знания и навыки, а не chatgpt.
Потом, chatgpt не заменяет программиста. Он только по самым боянистым, раскопипащеным по всему интернету задачам выдает правильный ответ. Иногда можно чуть-чуть слова в условии поменять и он выдает очень правдоподобный и очень неправильный бред. И вот понять, что оно не работает и почему - это будет посложнее чем эти задачки решать самостоятельно.
Foror
04.08.2024 10:48>Иногда можно чуть-чуть слова в условии поменять и он выдает очень правдоподобный и очень неправильный бред
Вы или крестик снимите или трусы наденьте. Так чего тогда не даёте людям доступ к чатгпт? Поменяйте слова в условии, если конечно хватит ваших мясных мозгов обойти чатгпт.
>Да, на интервью не дают доступа к интернету, ибо проверяют ваши знания и навыки, а не chatgpt.
Так и на работе запретите гугл и чатгпт. Вы работника наняли или халявщика? Он же в гугл полезет, в чатгпт зайдет и всё скопирует! А вы ему деньги заплатите!idsulik Автор
04.08.2024 10:48+1а как тогда проверить того, кого хотят нанимать?) ведь нужен какой-то фильтр
Foror
04.08.2024 10:48В вузе, когда преподаватель видел, что мне было лень делать лабу и я её позаимствовал у местного ботана, просто просил мне объяснить, что здесь происходит. Я ему объяснял и ко мне претензий не было.
idsulik Автор
04.08.2024 10:48молодец!
но к чему это?)Foror
04.08.2024 10:48Спросите у чатгпт, правда я не уверен, что сможете ли вы правильно сформулировать вопрос. Поэтому я сделаю это за вас:
В вузе, когда преподаватель видел, что мне было лень делать лабу и я её позаимствовал у местного ботана, просто просил мне объяснить, что здесь происходит. Я ему объяснял и ко мне претензий не было.
к чему это?)
Это может быть примером ситуации, когда преподаватель хочет убедиться, что студент действительно понимает материал, даже если он использовал чужую работу. Это подчеркивает важность понимания и усвоения знаний, а не просто выполнения заданий. Преподаватель, вероятно, ценит усилия студента объяснить материал, что может свидетельствовать о его понимании, даже если работа была заимствована.idsulik Автор
04.08.2024 10:48так ты можешь у местного ботана спросить, что там написано, выучить это и рассказать учителю)
Foror
04.08.2024 10:48>Это было сказано при споре о выполнении алгоритмических заданий при приёме на работу
В таком контексте это может указывать на то, что работодатели ценят не только конечный результат, но и способность кандидата объяснить свои решения и подходы к задачам. Это важно в алгоритмических заданиях, где понимание принципов и логики может быть более значимым, чем просто правильный ответ. Способность объяснить свои действия может свидетельствовать о глубоком понимании темы и умении применять знания на практике.idsulik Автор
04.08.2024 10:48никто же этого и не отрицает) если написать правильное решение, но молча, есть больше вероятность НЕ попасть на работу, нежели если решить неправильно, НО объясняя ход своих мыслей
idsulik Автор
04.08.2024 10:48+1ну разные виды разработок бывают) раньше были Google Driven Development, Stackoverflow Driven Development, а теперь Chatgpt Driven Development. но это все тебе не поможет на собеседовании, там только ты и твой опыт, если ты раньше скопипастил решение откуда-то и не вникал, то это не поможет на интервью)
Foror
04.08.2024 10:48Я вас не пойму, так доступ с чатгпт даёте или нет?
idsulik Автор
04.08.2024 10:48+1Чтобы проверить что? ваше умение печатать?) задавать вопрос ИИ?)
Foror
04.08.2024 10:48Умение задавать вопрос ИИ и гуглить в частности, получая верный ответ очень ценный навык. Если вы этого не понимаете, то вам ещё предстоит долгий путь к этому.
idsulik Автор
04.08.2024 10:48с этим навыком вы далеко не пойдете, если нет других навыков)) наймете себе человека, который только и будет делать, что гуглить и спрашивать у чатгпт, завершит проект через пару лет
SpiderEkb
Если мне приходится делать реализации списков, я обычно сразу закладываю туда счетчик элементов. Если реализован двусвязный список, то любой элемент по номеру можно получить не более чем за length / 2 шагов - если n <= length / 2 - считаем с начала списка, иначе - с конца.
Вообще, двусвязный список предпочитаю делать кольцевым с двумя типами узлов.
Один узел имеет тип HEAD и содержит счетчик элементов и ссылки на первый и последний элементы списка (при необходимости там же могут быть какие-то другие свойства списка). Остальные элементы имеют тип NODE и содержат блок данных и ссылки на следующий и предыдущий элементы (первый в качестве предыдущего ссылается на HEAD, последний, в качестве следующего, аналогично ссылается на HEAD.
Сам объект "список" - это ссылка на HEAD.
idsulik Автор
Это тоже хороший и полезный способ, но все зависит от самой задачи, если достаточно односвязного списка без доп. данных, то нет смысла добавлять доп. данные, а если для задачи полезно держать какие-то данные в узлах, то делаем так)
SpiderEkb
Да, конечно от задачи. Иногда вообще ничего не нужно - можно использовать готовые библиотечные реализации.
monpa
Тут структура данных неподходящая выбрана) Искать середину полной итерацией - ну такое себе развлечение.
YMA
Вариант с 2 указателями хорош для олимпиады - оптимально, изящно. Он приходит в голову сразу, когда читаешь заголовок.
А вот в реальной работе предпочитаю первый, с конвертацией списка в массив... Потому как обычно нахождением среднего элемента обработка данных не ограничивается, памяти сейчас много, а ждать пользователь не любит. ;)
idsulik Автор
А что если элементов действительно много? миллионы элементов, каждый элемент содержит большое количество данных?)
лучше за один проход решить, если такая возможность есть) и быстро и памяти потребляет мало
acsent1
Если нужно найти серединный элемент в таком случае, то значит где-то неверно выбрали способ хранения данных
idsulik Автор
ну да, если задача заключается в просто нахождении середины, то это неоптимальный вариант хранения данных
avost
Самое интересное в этом комментарии не озвучено :). Расскажите, пожалуйста, что это были за задачи (во множестве числе!), для решения которых вам приходилось не только использовать связные списки, но и писать свои реализации?
Я спрашиваю без подколок - иногда на тех же собеседованиях спрашивают когда linked list лучше, чем array list - обычно ничего вменяемого придумать не удаётся.
В практических, конечно, задачах, не в литкодных/олимпиадных.
idsulik Автор
надо было мне это объяснить на видео.
проблема массивов в том, что когда место заканчивается, тебе надо создать новый массив большего размера, скопировать туда все элементы старого массива и добавить новый элемент уже в новый массив, когда как linked list может расширяться сколько угодно и по одному элементу.
а вот реально применять связный список мне пока не приходилось)
avost
Обычно, это не очень большая проблема и если уж стало припекать по объёму занимаемой памяти, то стоит задуматься либо о том, так ли хорошо всё делается или о ручном управлении памятью (насколько это в яве возможно). LinkedList в этом случае о-о-очень сомнительное решение, тк у него офигенный оверхед по памяти, особенно, на небольших целевых объектах, который может сожрать всю "выгоду" от переаллокации массивов.
Из других предложенных вариантов часть тоже весьма сомнительна - какие-то мутные схемы с большими объёмами данных и пересортировками... Особенно пересортировки меня удивили - делать сортировки на связных списках - то ещё развлечение. Ну, и для сортировки таких больших объектов ключ-значение лучше сортировать индексы.
Fifo-Lifo прекрасно делаются на массивах.
Частые дополнения большого количества - я бы тоже подумал о кастомных ArrayList-ах
Про объекты больших размеров - ну, такое,.. смотреть по месту, конечно, надо...
А, вот список поверх другой структуры данных (типа LRU структур) - это да-а! Как раз и список и его реализация. И в яве уже даже есть LinkedHash[Map|Set] - весьма полезная штуковина. В том числе, чтобы на собеседовании сказать если вопрос возникнет ))
Вот, в том-то и дело ))
SpiderEkb
Свои реализации делаются или когда что-то очень специфическое по данным, или когда готовой нет в наличии (такое тоже бывает в жизни), или когда нужна предельная эффективность вкупе с какой-то спецификой задачи и приспособить готовое получается достаточно коряво.
Список или массив... Нам часто приходится иметь дело с очень большими объемами данных. Память в целом не проблема, можно считать что она не ограничена. Но есть ограничение - 16Мб одним куском (ну можно 2Тб, но там уже приходится "танцевать вприсядку" - это другая модель памяти и, в общем случае, даже другой размер указателя). И вот если нет уверенности что получится выделить массив (даже динамический массив все равно в памяти одним куском будет), то тогда используется список.
Там еще есть варианты - списки ключ-данные с необходимостью поиска по ключу. Можно организовать это массивом, отсортировать его и потом использовать быстрый двоичный поиск (быстрее не бывает). Но тут есть момент - если у нас данные постоянно меняются, то каждый раз пересортировывать массив из хотя бы сотни тысяч элементов (а для нас это не сказать чтобы сильно много) приводит просто к катастрофической потере производительности. И вот тут лучше список ключ-данные.
А если это статика - один раз заполнил, отсортировал и потом 100500 раз ищешь - там сортированный массив по производительности лучше.
Sap_ru
Нужен FIFO или LIFO доступ к элементам.
Нужны частые операции добавляения большого количества элементов или объединения списков.
Список состоит из элементов большого размера, может содержать большое колличество элеметнов и при этом все время растет. Использование массивов тут неоптимально по причине часто реаллокации больших объёмов памяти.
Массив состоит из структур и по причине экономии ресурсов или необходимости обеспечения эффекивного многопоточного атомарного доступа нужно, чтобы элементы структур были сразу элементами списка (т.е. отказ от работы с указателями даёт какие-то преимущества). Крайне редкая ситуация.
idsulik Автор
Лучше не опишешь, добавлю это в комментарии к видео и оставлю ссылку на источник)
aamonster
В практических задачах обычно linked list делается не отдельно, а поверх уже существующей структуры данных, чтобы выстроить в цепочку объекты, которые существуют без него. Как контейнер – не припомню...
idsulik Автор
не понял этот момент, что имеется в виду?
aamonster
В смысле у вас уже есть какое-то хранилище объектов (массив, дерево, ещё что – что вам диктует задача) и вам понадобилось для каких-то нужд объединить эти объекты в цепочки. Можно хранить отдельно списки указателей на ваши объекты, а можно просто добавить в каждый объект поле next.
idsulik Автор
ну это как-то не очень, лучше создать LinkedList, чтобы код был чище)
aamonster
Ага, и фигакнуть на ровном месте по выделению памяти в куче на каждый элемент.
idsulik Автор
ну значение ноды будет ССЫЛКА на нужный объект, поэтому не вижу в этом проблем) ну или плохо понял идею
aamonster
Ага, только на N объектов вам придётся выделить N нод. Каждая будет хранить указатель на объект, указатель на следующую ноду + накладные расходы кучи. И затраты времени на выделение/освобождение.
А если вы прямо внутри вашего объекта сделаете поле указателя на следующий – это куда выгоднее.
Если же вам надо очередь делать снаружи, не модифицируя объекты – обычно выгоднее (и по памяти, и по быстродействию) кольцевой буфер.
idsulik Автор
На самом деле есть место и тому и другому и третьему варианту) тут зависит от конкретной задачи.
Но я не знаю кейса, где понадобится такая оптимизация, что нужно менять объякты и добавлять туда указатели, вместо использования linked list
aamonster
Я за 29 лет практики не припомню задачи, где мне понадобился бы именно отдельный Linked list :-)
idsulik Автор
тоже не припоминаю) ни в том, ни в другмо виде
SpiderEkb
Вопрос - а что были за задачи в практике?
slonopotamus
В C такое делают постоянно.
idsulik Автор
а можно конкретный пример?)
wataru
Например, при реализации LRU кеша. Там при доступе у ключу, он перемещается в конец списка. При переполнении кеша (хеш таблица значений), удаляется элемент из начала списка.
SpiderEkb
Например, в ситуациях, когда по какой-причине нужно вставлять или удалять элементы внутри цепочки.
aamonster
Учитывая, что чтобы вставить или удалить элемент, нужно вначале найти его место за O(n) – редко когда linked list в качестве контейнера оправдан.
SpiderEkb
Простейший случай - идете по цепочке от начала к концу и для каждого элемента принимаете решение - оставить его или удалить. Такой вот play-off алгоритм.
Есть еще очереди. Например, на отправку сообщений. Сообщение для отправки берется из начала очереди. Новые сообщения добавляются в конец. Отправленное (точнее, отправленное на которое получено подтверждение о поиеме) сообщение удаляется из начала очереди.
aamonster
Очередь обычно делается кольцевым буфером, не linked list. Исключение – когда объекты уже лежат где-то и вы их просто связываете прямо на месте.
Play-off – тот же один проход по массиву (двумя указателями) удаляет всё лишнее за O(n), как и в случае linked list.
Я не говорю, что linked list нигде не пригодится, но его использование в качестве контейнера – лютая экзотика.
AlexSky
В ядре Линукса нередко встречается.
aamonster
Он там обычно владеет объектами или связывает хранящиеся не в нём?
morijndael
да, но там часто недопустимы случайные задержки из-за необходимости амортизации. Если же это не критично, то почти всегда предпочтительнее цельный кусок памяти
idsulik Автор
как используется?
SpiderEkb
Кольцевые буфера хороши там, где поток сообщений относительно невелик, а ресурсы сильно ограничены. Например, на промконтроллере.
А вот когда у вас ядро, обеспечивающее связь десятком контроллеров с несколькими интерфейсными клиентами, да еще количество контроллеров (а значит плотность потока сообщений) может варьироваться в широких пределах, тут уже кольцевые буфера сильно неудобны. Хотя бы тем, что вам придется сразу выделить ну очень много памяти в статике.
Помножьте на то, что размер сообщения может быть разным - от десятков байт до килобайт. В статическом буфере вам придется выделять память под максимальный размер сообщения.
Помножьте на то, что могут быть "приоритетные" сообщения, которые помещаются не в конец, а в начало очереди.
А еще сообщение может не получить подтверждения и его нужно передвинуть в очереди на перепосылку через какое-то время...
У поверьте, я с этим много наелся когда занимался разработкой ядра системы мониторинга инженерного оборудования зданий. Начинали с буферов, но достаточно быстро наелись с этим и перешли на очереди. С которыми все стало намного проще.
Сейчас задачи другие, но вот есть параллельная обработка больших объемов данных (десятки и сотни элементов). И там есть такая штука как "конвейер". Тоже на FIFO очередях строится.
Play-Off, как следует из названия, подразумевает многократный проход по списку с удалением элементов на каждом проходе.
В общих чертах - пришло некоторое условие. По нему составляется список элементов, удовлетворяющих этому условию (ну для понимания - 500-600 тысяч элементов). Приходит второе условие - проходим по списку и удаляем все, что не проходит по второму условию. Потом третье, пятое, десятое... Каждый раз список сокращается. Поскольку элементы физически удаляются, то каждый новый проход будет короче предыдущего. С массивом тоже можно, но там придется или два массива делать с перебросом из одного в другой и обратно (менять их местами на каждом проходе), или с одним, но с копированием последнего элемента массива на место очередного выбывшего. Что тоже требует времени.
В результате по скорости (подтверждено PEX статистиками) разницы нет - что связанный список, что два массива, что один. А вот простоте и понятности кода со списком намного проще.
wataru
Ничего не мешает держать хеш-таблицу из идентификаторов элементов в указатели/итераторы в list. Популярное применение - LRU cache. Там список навешан сверху на хеш-таблицу и задает порядок элементов, чтобы выбирать, какой элемент самый старый и его надо удалить. При доступе элемент из центра списка будет перемещен в конец.
aamonster
Это то, про что я говорил: linked list не как контейнер, а связываем хранящиеся отдельно данные.