Двоструко повезане листе и како их имплементирати у Питхон 3

Повезане листе су линеарни начин чувања података. Састоји се од чворова који садрже податке као и показивача како доћи до следећег дела података. Размислите о чворовима као о ланцу. Сваки ланац зависи један од другог за одржавање снажне везе. Ако, на пример, средњој вези недостаје све након тога не успе. То више није комплетан ланац! Како се то преводи на повезане листе? Ако један од показатеља недостаје или је нетачан, остатак података се више не може очитати.

Није валидан ланац! Ово би прекинуло повезану листу!

Међутим, тема овог чланка је на свестранијој верзији повезаних листа - на двоструко повезаној листи. У поређењу са редовном (или појединачно) повезаном списком, двоструко повезана листа садржи још један показивач који се зове претходни. Као што можда претпостављате, ово чвору омогућава да зна гдје је претходни чвор. Поређења ради, појединачно повезана листа морала би поново прећи цео списак до оне тачке која је претходна да би стигла до исте тачке.

За информације о појединачно повезаним списковима посетите чланак мог разредника:

Као што је раније поменуто, чворови упућују на друге локације у меморији. Шта то значи? Па, за разлику од низова који се чувају на непрекидним локацијама, повезане листе једноставно имају показиваче. У дијаграму испод сваког блока меморије (црвени) постоје два показивача која га упућују. Те информације приступају гледајући следећи показивач (црни). Ако жели да пронађе блок претходног, погледаће Претходни показивач (бели).

Па како имплементирати двоструко повезан списак? Ево како у Питхон-у 3

Једноставно додајте .прев у вашу класу Ноде. Сада сте спремни за почетак примене!

Предности - Са Питхон 3 кодом!

Које су неке од предности двоструко повезане листе у односу на појединачно повезану листу? Па, с двоструко повезаном списком, можете се кретати напријед и напријед између чворова. То чини ствари попут уметања заиста једноставним. Са двоструко повезаним листама само бисте прешли повезану листу до жељеног чвора и позвали на претходни чвор.

Недостаци

Иако постоје сјајне ствари о повезаним листама, то није свеобухватно решење. Као и код многих података и алгоритама, ово би требало бити алат у вашем арсеналу. Један од недостатака код појединачно повезане листе је тај да постоји већа потрошња меморије јер свака веза на дупло повезаној листи мора пратити тај претходни поинтер. Поред тога, тешко је пратити поменути показивач.

Заправо још увијек сам у пракси практиковања њихове примјене. Ово ће бити моја друга успешна примена од писања овог чланка (април 2019.). Сваки пут ми постаје лакше, али још увек морам да нацртам дијаграме како претходни показивач интерактивно делује са свим мојим осталим функцијама.

Али за шта би се ово користило?

Чујем да питаш. Размислите о сваком тренутку када сте видели претходну и следећу. Постоје неки очити и суптилни начини да се они могу провести.

Извор: хттпс://пбс.твимг.цом/медиа/ДкзКсвУККСгААвмкк.јпг

Шта је са случајем попут музичког плејера? Има врло експлицитни следећи и претходни тастер. Двоструко повезана листа могла би се користити за прелазак између те двије пјесме.

Или шта је са прегледачем? Они такође имају експлицитне начине за кретање унапред и унапред између веб страница које сте посетили.

Сада размислите о свом софтверу за обраду текста или уређивачу фотографија по избору. Сваки пут када погрешите, можете да притиснете ЦТРЛ (ЦМД за Мац) + З да бисте поништили последњу радњу. Исто тако, у могућности сте да поновите оно што сте поништили помоћу ЦТРЛ (ЦМД за Мац) + И. Зашто сада ово звучи познато? Такође се може имплементирати са двоструко повезаном списком! Претходни показивач указује на радње које су учињене, а истовремено можете поновити радње ако превише поништите.

Извор: хттпс://гфицат.цом/бриллиантбеаутифулдассиеИзвор: хттпс://ввв.солитаирецардгамес.цом/хов-то-плаи-солитаире

Мање очигледна примена о којој сам размишљао била је у игри Пасијанс. Са стране је слика терминологија Пасијанса која ће вам помоћи да илуструјем мој став.

Игра је сјајан пример где стално морате бити у могућности да прегледате претходне и следеће карте било да су оне у столу или на хрпи отпада. Док играте карту са гомиле отпада ка столу, гомила отпада се ажурира картицом која је била претходна.

За живахнију дискусију о кориштењима на двоструко повезаним листама, препоручио бих да погледате ову дискусију о стацковерфлову:

Дакле, следећи пут када имплементирате повезану листу, зашто не бисте испробали двоструко повезану листу? Није толико много кода на врху повезане листе и постоје велике предности!

Додатна средства

Потпуна веза за моју Питхон 3 имплементацију двоструко повезане листе може се наћи на мом Гитхуб репо-у.

Ако желите 3Д ланац за штампање двоструко повезаних листа, послао сам га у Тхингиверсе.

хттпс://ввв.геексфоргеекс.орг/доубли-линкед-лист/

хттпс://ввв.туториалспоинт.цом/дата_струцтурес_алгоритхмс/доубли_линкед_лист_алгоритхм.хтм

хттпс://ввв.иоутубе.цом/ватцх?в=ЈдКеНкВЦгуК