Связные списки

← →
Redwwq (2007-03-18 15:36) [0]

Чем отличается односвязный список от двусвязного?

← →
Eraser © (2007-03-18 15:38) [1]

> Redwwq (18.03.07 15:36)

тем что в первом одна связь, а во втором - две :)

← →
xayam © (2007-03-18 15:44) [2]

> Eraser © (18.03.07 15:38) [1]
> > Redwwq (18.03.07 15:36)
> тем что в первом одна связь, а во втором - две :)

железная логика ))

← →
vuk © (2007-03-18 15:54) [3]

У элемента односвязного списка есть только ссылка на следующий за ним элемент. У элемента двусвязного - на следующий и предыдущий. В результате по односвязному можно перемещаться только в одну сторону, а по двусвязному - в обе. Вставка/удаление на двусвязных списках работает быстрее.

← →
Anatoly Podgoretsky © (2007-03-18 15:59) [4]

> vuk (18.03.2007 15:54:03) [3]

> Вставка/удаление на двусвязных списках работает быстрее.

Я бы не сказал, в двухсвязном списке надо поправить две ссылки, вместо одной.

← →
vuk © (2007-03-18 16:01) [5]

to Anatoly Podgoretsky © (18.03.07 15:59) [4]:
>Я бы не сказал, в двухсвязном списке надо поправить две ссылки, вместо
>одной.
При этом предыдущий элемент (ссылку в котором тоже надо поправить) находится только перебором от начала списка. В отличие от.

← →
Anatoly Podgoretsky © (2007-03-18 16:07) [6]

> vuk (18.03.2007 16:01:05) [5]

Эта ссылка будет получена при поиске текущего элемента.

← →
vuk © (2007-03-18 16:17) [7]

to Anatoly Podgoretsky © (18.03.07 16:07) [6]:
>Эта ссылка будет получена при поиске текущего элемента.
Зависит от того, в какую ситуацию попадем. Может и не быть этой ссылки в каком-то конкретном случае. Если рассматривать ситуацию, когда есть элемент списка который нам нужно вставить и место, куда его нужно вставить заданное другим элементом списка, то для односвязных списков операции "вставить элемент после" и "вставить элемент до" сильно отличаются, т.к. в одном из случаев необходим перебор для поиска. С удалением ровно та же история.

← →
Anatoly Podgoretsky © (2007-03-18 16:28) [8]

> vuk (18.03.2007 16:17:07) [7]

Если сохраненая ссылка, то конечно так

← →
isasa © (2007-03-18 16:50) [9]

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

← →
antonn © (2007-03-18 16:51) [10]

isasa © (18.03.07 16:50) [9]
тоже самое касается под-рут, только не так интересно:)

← →
default © (2007-03-18 16:58) [11]

isasa © (18.03.07 16:50) [9]
а разве плохо когда весело?:)

← →
isasa © (2007-03-18 17:04) [12]

default © (18.03.07 16:58) [11]
а разве плохо когда весело?:)

А кто-ж спорит? :)

← →
clickmaker © (2007-03-18 17:09) [13]

> нужно как зеницу ока хранить Root

root всегда надо хранить. Чтобы в него зрить (зреть?) периодически

← →
isasa © (2007-03-18 17:12) [14]

clickmaker © (18.03.07 17:09) [13]

Это был намек? Или как ... ? :)

← →
Ант (2007-03-18 20:04) [15]

Ребяты, а кто-нить в ральных программах использует эти фишки?
Я вот как то по жизни всегда обхожусь TList"ом, и не представвляю ситуации, когда на практике понадобится односвязный (двухсвязный) список.
Ну разве что курсовую по программированию в ВУЗе сдать.
Но я говорю о реальной жизни.

Поправьте если не прав

← →
Eraser © (2007-03-18 20:08) [16]

> Ант (18.03.07 20:04) [15]

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

← →
default © (2007-03-18 20:55) [17]

Eraser © (18.03.07 20:08) [16]
во второй фремворк внесли класс двусвязного списка
видно кому-то он таки нужен:)

← →
Ант (2007-03-18 21:01) [18]

> Eraser ©
</I
> default ©

>

Давайте конкретику, хорошо? :-)

← →
vuk © (2007-03-18 21:05) [19]

to Ант (18.03.07 20:04) [15]:
>не представвляю ситуации, когда на практике понадобится односвязный
>(двухсвязный) список.
У массивов (а TList это внутри всё-таки массив) эффективность операций добавления/удаления сильно ниже, чем у списков и ещё зависит от количества злементов. Вот и получается - для случаев с активной вставкой-удалением элементов списки использовать лучше, чем TList и иже с ними.

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

← →
cyborg © (2007-03-18 21:08) [20]

> [15] Ант (18.03.07 20:04)

Я, вот, не представляю как без них можно делать.

← →
isasa © (2007-03-18 21:15) [21]

Ну это "третий" компонент, но TdxDBTreeView из Dev. Express, чем не список.

← →
vuk © (2007-03-18 21:16) [22]

to isasa © (18.03.07 21:15) [21]:
>но TdxDBTreeView из Dev. Express, чем не список.
Ничем. Потому, что он дерево. :)

← →
isasa © (2007-03-18 21:20) [23]

Принцип тот же ... Остальное нюансы. :)

← →
vuk © (2007-03-18 21:35) [24]

to isasa © (18.03.07 21:20) [23]:
>Принцип тот же ... Остальное нюансы. :)
Ну... Не зная того, как устроен внутри элемент дерева в TTreeView я не брался бы утверждать, что там именно списочные структуры внутри используются. А как оно там у MS реализовано - фиг их знает.

А вот если взять TdxTreeList тех же DevExpress (и соответственно QuantumGrid до 4-й версии), то там подэлементы в узле дерева в TList хранятся.

← →
Ант (2007-03-18 22:27) [25]

Мне кажется, времена печения о быстродействии программы при работе с оперативкой до такой степени, остались в прощлом

ну пробегитесь миллион раз по списку первым и вторым способом - и разница составит сотые доли секунды

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

← →
DVM © (2007-03-18 22:33) [26]

> Мне кажется, времена печения о быстродействии программы
> при работе с оперативкой до такой степени, остались в прощлом

времена всегда одинаковые, задачи стали объемнее, и где раньше был миллион, теперь миллиард.

← →
vuk © (2007-03-18 22:43) [27]

Блин. А потом сидим и удивляеся, почему все тормозное такое... :(

← →
Ант (2007-03-18 23:06) [28]

Ну вот честное пионерское, ни разу ни одна реальная программа не тормозила потому, что работала с массивом вместо связного списка.
А вот за счет бардачной организации доступа к БД - постоянно

> [28] Ант (18.03.07 23:06)

Вы показываете мнение человека, никогда не писавшего приложения с критичной скорости работы(судя по тому, что не считаете сотые доли большим числом... Иногда приходится воевать из-за тысячных) и вообще никогда не учавствовали в больших серьезных проектах не ограничивающихся выборкой из БД(судя по тому, что не знаете куда применить классические вещи, теже списки)...
В этом проблема дельфи(это не лично к вам, это ), натыкали компонетов, работает - и замечательно.
Реально есть куда прикрутить даже конечный автоматы. ;)
P.S>
Тут не далеко обсуждали эффективность использования двусвязных(помоему) список для хранения текстурных объектов.
Кстати, TList по моему тоже список двусвязный.

to @!!ex © (18.03.07 23:19) [29]:
>Кстати, TList по моему тоже список двусвязный.
Массив он. В чистом виде. Исходники смотрите.

← →
Ант (2007-03-18 23:27) [31]

← →
Ант (2007-03-18 23:31) [32]

> что не считаете сотые доли большим числом.

Я имел в виду - на всю операцию, на весь массив (список)

> Массив он. В чистом виде. Исходники смотрите.

Ну скажем не в чисто.. Всетаки массив указателей, а не чистый массив...
Но вообще вы правы, перепутал с Сишными.

> [31] Ант (18.03.07 23:27)

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

to @!!ex © (18.03.07 23:32) [33]:
>Ну скажем не в чисто.. Всетаки массив указателей, а не чистый массив...
А как это называть? Если контейнер для указателей хранит их в массиве указателей, это не массив в чистом виде? :)

← →
Ант (2007-03-18 23:45) [36]

← →
Ант (2007-03-18 23:46) [37]

блин...
применять конечно же

> [36] Ант (18.03.07 23:45)

Игры - единственное место, где используются динамических структуры?
Я говорю об играх. потому как именно там я их и использую, но это же не единственное место. :)

Реальный пример использования связанных списков — список закладок в браузере. Когда их можно свободно перемещать, удалять и выполнять другие операции. Можно, конечно, хранить позицию каждой закладки в массиве и искать при каждом переключении закладки следующую, затрачивая кучу памяти и времени, а можно просто поменять пару указателей местами.

> Zeqfreed (18.03.2007 23:54:39) [39]

Неудачный пример.
Эта задача также мгновенно решается и с помощью массива.

Связные списки Найти похожие ветки