search

kzhereb / kpi-acts-ta2020

Materials for "Algorithm theory" course
MIT License
0 stars 0 forks source link

D03.2.Why do we need doubly linked list? #56

Open chihh opened 4 years ago

chihh commented 4 years ago

Навіщо потрібні двозв’язні списки? Доступ за індексом вдвічі швидше Також додавання та видалення за індексом Можна рухатись назад Обхід з кінця Доступ за індексом – вдвічі швидше Додавання, якщо не зберігати початок та кінець Для реалізації черги

Index access is twice as fast Also add and remove by index You can move back Bypass from the end Index access is twice as fast Add if you do not save the beginning and the end To implement the queue

chihh commented 4 years ago

In singly linked list, to delete a node, pointer to the previous node is needed. To get this previous node, sometimes the list is traversed. In DLL, we can get the previous node using previous pointer. from https://www.geeksforgeeks.org/doubly-linked-list/

PickDough commented 4 years ago

У питанні наведені хороші варіанти, тому я перерахую, ті, з якими ми зустрічаємось у повсякденному житті:

Yuliiaa commented 4 years ago

Ще одна перевага має значення тільки при деяких несправностях. Оскільки весь список можна пройти не лише за прямими, але і за зворотніми посиланнями, то в разі, якщо якесь із посилань стане невірним, цілісність списку можна відновити за іншим посиланням.

DmytroTarasov commented 4 years ago

Quite a lot has been said about the benefits of doubly-linked lists and their practical application, I want to add that they are also used to represent different states of games.

Here are a few disadvantages of this data structure. To my mind, when implementing a certain data structure, it is also necessary to pay attention to its disadvantages, not just advantages. So, 1) It uses extra memory when compared to array and singly linked list. 2) To get to a particular item, we need to review all items that are in front of it.

robertdubson commented 4 years ago

There are various application of doubly linked list in the real world. Some of them can be listed as:

Doubly linked list can be used in navigation systems where both front and back navigation is required. It is used by browsers to implement backward and forward navigation of visited web pages i.e. back and forward button. It is also used by various application to implement Undo and Redo functionality. It can also be used to represent deck of cards in games. It is also used to represent various states of a game. https://www.geeksforgeeks.org/list-cpp-stl/