Dvostruko povezana lista
U računarskoj nauci, dvostruko povezana lista je povezana struktura podataka koja se sastoji iz seta sekvencijalno povezanih podataka zvanih čvorovi. Svaki čvor sadrži dva polja, zvana veze, koja su reference na prethodni i sledeći čvor u sekvenci čvorova. Prethodna i sledeća veza početnog i krajnjeg čvora, pokazuju na neku vrstu terminatora, tipično na stražarski čvor ili nulu, da bi olakšalo upravljanje listom. Ako postoji samo jedan čvor čuvar, onda je lista cirkularno povezana preko čvora stražara. To može biti koncipirano kao jednostruko povezane liste formirane od istih podataka, ali u obrnutim sekvencijalnim redovima.
Dve veze s čvorovima omogućavaju rukovanje listom s bilo koje strane. Dok dodavanje ili sklanjanje čvora u dvostruko povezanoj listi zahteva menjanje više veza nego iste operacije na jednostruko povezanoj listi, operacije su jednostavnije i potencijalno efikasnije (za čvorove koji nisu početni) jer ne postoji potreba za praćenjem prethodnog čvora tokom rukovanja ili ne postoji potreba da se pređe lista da bi se pronašao prethodni čvor, tako da se njegova veza može modifikovati.
Koncept je takođe osnova za mnemonic link system memorization tehniku.
Nomenklatura i implementacija[uredi | uredi izvor]
Prvi i poslednji čvorovi dvostruko povezane liste su odmah dostupne (tj., dostupne bez prelaženja, i obično se nazivaju glava i rep) i premda dozvoljavaju prelazak liste s početka ili kraja liste: tj., prelaženje liste od početka do kraja, ili od kraja do početka, u potrazi za čvorom sa određenom vrednošću podatka. Bilo koji čvor u dvostruko povezanoj listi, jednom kada se dobije, može da se iskoristi za početak novog prelaženja liste, u bilo kom pravcu (prema početku ili kraju), od datog čvora.
Polja za veze čvora dvostruko povezanih listi se često nazivaju sledeća i prethodna ili napred i nazad. Reference sačuvane u poljima za veze su često implementirane kao pokazivači, ali (kao u svakoj povezanoj strukturi podataka) takođe mogu da budu ofseti adresa ili indeksi u nizu gde žive čvorovi.
Osnovni algoritmi[uredi | uredi izvor]
Razmotrite sledeće osnovne algoritme napisane u Adi:
Otvorene dvostruko povezane liste[uredi | uredi izvor]
record DoublyLinkedNode {
prev // A reference to the previous node
next // A reference to the next node
data // Data or a reference to data
}
record DoublyLinkedList {
DoublyLinkedNode firstNode // points to first node of list
DoublyLinkedNode lastNode // points to last node of list
}
Prenošenje liste[uredi | uredi izvor]
Prelaženje dvostruko povezane liste može da se odvija u bilo kom pravcu. U stvari, pravac prelaska može da se promeni puno puta, ako to želimo. Prelazak se takođe naziva i iteracija, ali taj izbor terminologije je nesrećan, za iteraciju postoji dobro definisana semantika (tj., u matematici) koja nije analogna prelasku.
Unapred
node := list.firstNode
while node ≠ null
<do something with node.data>
node := node.next
Unazad
node := list.lastNode
while node ≠ null
<do something with node.data>
node := node.prev
Ubacivanje čvora[uredi | uredi izvor]
Ove simetrične funkcije ubacuju čvor ili posle ili pre datog čvora:
function insertAfter(List list, Node node, Node newNode)
newNode.prev := node
newNode.next := node.next
if node.next == null
list.lastNode := newNode
else
node.next.prev := newNode
node.next := newNode
function insertBefore(List list, Node node, Node newNode)
newNode.prev := node.prev
newNode.next := node
if node.prev == null
list.firstNode := newNode
else
node.prev.next := newNode
node.prev := newNode
Takođe nam je potrebna funkcija za ubacivanje čvora na početak moguće prazne liste:
function insertBeginning(List list, Node newNode)
if list.firstNode == null
list.firstNode := newNode
list.lastNode := newNode
newNode.prev := null
newNode.next := null
else
insertBefore(list, list.firstNode, newNode)
Simetrična funkcija ubacuje na kraj:
function insertEnd(List list, Node newNode)
if list.lastNode == null
insertBeginning(list, newNode)
else
insertAfter(list, list.lastNode, newNode)
Uklanjanje čvora[uredi | uredi izvor]
Uklanjanje čvora je lakše od ubacivanja, ali zahteva posebno rukovanje ako je čvor koji treba da se ukloni prvi ili poslednji čvor:
function remove(List list, Node node)
if node.prev == null
list.firstNode := node.next
else
node.prev.next := node.next
if node.next == null
list.lastNode := node.prev
else
node.next.prev := node.prev
Jedna mala posledica gore pomenute procedura je da brisanje poslednjeg čvora liste postavlja i prvi i poslednji čvor na nulu, i tako se korektno rukuje uklanjanjem čvora iz jednoelementne liste. Primetite da nam takođe nisu potrebne metode ukloni pre i ukloni posle, jer u dvostruko povezanim listama možemo da koristimo samo jednu za oba smera. Ovo takođe pretpostavlja da čvor koji je uklonjen garantovano postoji. Ako čvor ne postoji u listi, onda je potrebna neka vrsta rukovanja greškama.
Cirkularna dvostruko povezana lista[uredi | uredi izvor]
Prenošenje liste[uredi | uredi izvor]
Pretpostavljajući da neki čvor u nepraznoj listi postoji, ovaj kod prolazi kroz tu listu počevši od tog čvora (bilo kog):
Unapred
node := someNode
do
do something with node.value
node := node.next
while node ≠ someNode
Unazad
node := someNode
do
do something with node.value
node := node.prev
while node ≠ someNode
//NODEPA Primetite odlaganje testa na kraju petlje. Ovo je važno u slučaju kada lista sadrži samo jedan čvor odnosno taj čvor.
Dodavanje čvora[uredi | uredi izvor]
Ova jednostavna funkcija ubacuje čvor u u dvostruko povezanu cirkularno povezanu listu nakon datog elementa:
function insertAfter(Node node, Node newNode)
newNode.next := node.next
newNode.prev := node
node.next.prev := newNode
node.next := newNode
Da bi smo dodali pre, jednostavno možemo da "insertAfter(node.prev, newNode)".
Dodavanje elementa u moguće praznu listu zahteva posebnu funkciju:
function insertEnd(List list, Node node)
if list.lastNode == null
node.prev := node
node.next := node
else
insertAfter(list.lastNode, node)
list.lastNode := node
Da bi smo dodali na očetak mi jednostavno "insertAfter(list.lastNode, node)".
Konačno, uklanjanje čvora mora da se izbori sa slučajem kada se lista isprazni:
function remove(List list, Node node)
if node.next == node
list.lastNode := null
else
node.next.prev := node.prev
node.prev.next := node.next
if node == list.lastNode
list.lastNode := node.prev;
destroy node
Implementacija dvostruko povezane liste[uredi | uredi izvor]
Sledeće funkcije ilustruju funkcionalnost implementaciju dvostruko povezanih listi u C/C++ programskim jezicima. Funkcije za dodavanje, brisanje, traženje, prikazivanje, unazad i detektovanje ciklusa u čvorovima su prikazane ispod.
/*
Description:
Double linked list header file
License: GNU GPL v3
*/
#ifndef DOUBLELINKEDLIST_H
#define DOUBLELINKEDLIST_H
/* Codes for various errors */
#define NOERROR 0x0
#define MEMALLOCERROR 0x01
#define LISTEMPTY 0x03
#define NODENOTFOUND 0x4
/* True or false */
#define TRUE 0x1
#define FALSE 0x0
/* Double linked DoubleLinkedList definition */
typedef struct DoubleLinkedList
{
int number;
struct DoubleLinkedList* pPrevious;
struct DoubleLinkedList* pNext;
}DoubleLinkedList;
/* Get data for each node */
extern DoubleLinkedList* GetNodeData(DoubleLinkedList* pNode);
/* Add a new node forward */
extern void AddNodeForward(void);
/* Add a new node in the reverse direction */
extern void AddNodeReverse(void);
/* Display nodes in forward direction */
extern void DisplayNodeForward(void);
/*Display nodes in reverse direction */
extern void DisplayNodeReverse(void);
/* Delete nodes in the DoubleLinkedList by searching for a node */
extern void DeleteNode(const int number);
/* Function to detect cycle in a DoubleLinkedList */
extern unsigned int DetectCycleinList(void);
/*Function to reverse nodes */
extern void ReverseNodes(void);
/* function to display error message that DoubleLinkedList is empty */
void ErrorMessage(const int Error);
#endif
/* Double linked List functions */
/*****************************************************
Name: DoubledLinked.c
version: 0.1
Description: Implementation of a DoubleLinkedList.
These functions provide functionality of a double linked List.
Change history:
0.1 Initial version
License: GNU GPL v3
******************************************************/
#include "DoubleLinkedList.h"
#include "stdlib.h"
#include "stdio.h"
/* Declare pHead */
DoubleLinkedList* pHead = NULL;
/* Variable for storing error status */
unsigned int Error = NOERROR;
DoubleLinkedList* GetNodeData(DoubleLinkedList* pNode)
{
if(!(pNode))
{
Error = MEMALLOCERROR;
return NULL;
}
else
{
printf("\nEnter a number: ");
scanf("%d",&pNode->number);
return pNode;
}
}
/* Add a node forward */
void AddNodeForward(void)
{
DoubleLinkedList* pNode = malloc(sizeof(DoubleLinkedList));
pNode = GetNodeData(pNode);
if(pNode)
{
DoubleLinkedList* pCurrent = pHead;
if (pHead== NULL)
{
pNode->pNext= NULL;
pNode->pPrevious= NULL;
pHead=pNode;
}
else
{
while(pCurrent->pNext!=NULL)
{
pCurrent=pCurrent->pNext;
}
pCurrent->pNext= pNode;
pNode->pNext= NULL;
pNode->pPrevious= pCurrent;
}
}
else
{
Error = MEMALLOCERROR;
}
}
/* Function to add nodes in reverse direction,
Arguments; Node to be added.
Returns : Nothing
*/
void AddNodeReverse(void)
{
DoubleLinkedList* pNode = malloc(sizeof(DoubleLinkedList));
pNode = GetNodeData(pNode);
if(pNode)
{
DoubleLinkedList* pCurrent = pHead;
if (pHead==NULL)
{
pNode->pPrevious= NULL;
pNode->pNext= NULL;
pHead=pNode;
}
else
{
while(pCurrent->pPrevious != NULL )
{
pCurrent=pCurrent->pPrevious;
}
pNode->pPrevious= NULL;
pNode->pNext= pCurrent;
pCurrent->pPrevious= pNode;
pHead=pNode;
}
}
else
{
Error = MEMALLOCERROR;
}
}
/* Display Double linked list data in forward direction */
void DisplayNodeForward(void)
{
DoubleLinkedList* pCurrent = pHead;
if (pCurrent)
{
while(pCurrent != NULL )
{
printf("\nNumber in forward direction is %d ",pCurrent->number);
pCurrent=pCurrent->pNext;
}
}
else
{
Error = LISTEMPTY;
ErrorMessage(Error);
}
}
/* Display Double linked list data in Reverse direction */
void DisplayNodeReverse(void)
{
DoubleLinkedList* pCurrent = pHead;
if (pCurrent)
{
while(pCurrent->pNext != NULL)
{
pCurrent=pCurrent->pNext;
}
while(pCurrent)
{
printf("\nNumber in Reverse direction is %d ",pCurrent->number);
pCurrent=pCurrent->pPrevious;
}
}
else
{
Error = LISTEMPTY;
ErrorMessage(Error);
}
}
/* Delete nodes in a double linked List */
void DeleteNode(const int SearchNumber)
{
unsigned int Nodefound = FALSE;
DoubleLinkedList* pCurrent = pHead;
if (pCurrent != NULL)
{
DoubleLinkedList* pNextNode = pCurrent->pNext;
DoubleLinkedList* pTemp = (DoubleLinkedList* ) NULL;
if (pNextNode != NULL)
{
while((pNextNode != NULL) && (Nodefound==FALSE))
{
// If search entry is at the beginning
if(pHead->number== SearchNumber)
{
pCurrent=pHead->pNext;
pHead= pCurrent;
pHead->pPrevious= NULL;
Nodefound =TRUE;
}
/* if the search entry is somewhere in the DoubleLinkedList or at the end */
else if(pNextNode->number == SearchNumber)
{
Nodefound = TRUE;
pTemp = pNextNode->pNext;
pCurrent->pNext = pTemp;
/* if the node to be deleted is not NULL,,,
then point pNextnode->pNext to the previous node
which is pCurrent */
if(pTemp)
{
pTemp->pPrevious= pCurrent;
}
free(pNextNode);
}
/* iterate through the Double Linked List until next node is NULL */
pNextNode=pNextNode->pNext;
pCurrent=pCurrent->pNext;
}
}
else if (pCurrent->number == SearchNumber)
{
/* add code to delete nodes allocated with other functions if
the search entry is found.
*/
Nodefound = TRUE;
free(pCurrent);
pCurrent= NULL;
pHead = pCurrent;
}
}
else if (pCurrent == NULL)
{
Error= LISTEMPTY;
ErrorMessage(Error);
}
if (Nodefound == FALSE && pCurrent!= NULL)
{
Error = NODENOTFOUND;
ErrorMessage(Error);
}
}
/* Function to detect cycle in double linked List */
unsigned int DetectCycleinList(void)
{
DoubleLinkedList* pCurrent = pHead;
DoubleLinkedList* pFast = pCurrent;
unsigned int cycle = FALSE;
while( (cycle==FALSE) && pCurrent->pNext != NULL)
{
if(!(pFast = pFast->pNext))
{
cycle= FALSE;
break;
}
else if (pFast == pCurrent)
{
cycle = TRUE;
break;
}
else if (!(pFast = pFast->pNext))
{
cycle = FALSE;
break;
}
else if(pFast == pCurrent)
{
cycle = TRUE;
break;
}
pCurrent=pCurrent->pNext;
}
if(cycle)
{
printf("\nDouble Linked list is cyclic");
}
else
{
Error=LISTEMPTY;
ErrorMessage(Error);
}
return cycle;
}
/*Function to reverse nodes in a double linked list */
void ReverseNodes(void)
{
DoubleLinkedList *pCurrent= NULL, *pNextNode= NULL;
pCurrent = pHead;
if (pCurrent)
{
pHead =NULL;
while (pCurrent != NULL)
{
pNextNode = pCurrent->pNext;
pCurrent->pNext = pHead;
pCurrent->pPrevious=pNextNode;
pHead = pCurrent;
pCurrent = pNextNode;
}
}
else
{
Error= LISTEMPTY;
ErrorMessage(Error);
}
}
/* Function to display diagnostic errors */
void ErrorMessage(const int Error)
{
switch(Error)
{
case LISTEMPTY:
printf("\nError: Double linked list is empty!");
break;
case MEMALLOCERROR:
printf("\nMemory allocation error ");
break;
case NODENOTFOUND:
printf("\nThe searched node is not found ");
break;
default:
printf("\nError code missing\n");
break;
}
}
/* main.h header file */
#ifndef MAIN_H
#define MAIN_H
#include "DoubleLinkedList.h"
/* Error code */
extern unsigned int Error;
#endif
/***************************************************
Name: main.c
version: 0.1
Description: Implementation of a double linked list
Change history:
0.1 Initial version
License: GNU GPL v3
****************************************************/
#include <stdio.h>
#include <stdlib.h>
#include "main.h"
int main(void)
{
unsigned int choice =0;
int InputNumber=0;
printf("\nThis program creates a double linked list");
printf("\nYou can add nodes in forward and reverse directions");
do
{
printf("\n1.Create Node Forward");
printf("\n2.Create Node Reverse");
printf("\n3.Delete Node");
printf("\n4.Display Nodes in forward direction");
printf("\n5.Display Nodes in reverse direction");
printf("\n6.Reverse nodes");
printf("\n7.Exit\n");
printf("\nEnter your choice: ");
scanf("%u",&choice);
switch(choice)
{
case 1:
AddNodeForward();
break;
case 2:
AddNodeReverse();
break;
case 3:
printf("\nEnter the node you want to delete: ");
scanf("%d",&InputNumber);
DeleteNode(InputNumber);
break;
case 4:
printf("\nDisplaying node data in forward direction \n");
DisplayNodeForward();
break;
case 5:
printf("\nDisplaying node data in reverse direction\n");
DisplayNodeReverse();
break;
case 6:
ReverseNodes();
break;
case 7:
printf("Exiting program");
break;
default:
printf("\nIncorrect choice\n");
break;
}
} while (choice !=7);
return 0;
}
Napredni koncepti[uredi | uredi izvor]
Asimetrična dvostruko povezana lista[uredi | uredi izvor]
Asimetrična dvostruko povezana lista je negde između jednostruko povezane liste i regularne dvostruko povezane liste. Deli neke stavke sa jednostruko povezanom listom (prelaženje u jednom pravcu) i neke iz dvostruko povezane liste (lakoću modifikacije).
To je lista gde veza za prethodni čvor svakog čvora ne pokazuje na prethodni čvor, već na vezu samu za sebe. Dok ovo ima malo razlike između čvorova (samo pokazuje na ofset unutar prethodnog čvora), menja glavu liste: dozvoljava prvom čvoru da modifikuje vezu s prvim čvorom vrlo lako. [1][2]
Dokle god je čvor u listi, njegova veza sa prethodnim nikada nije nula.
Dodavanje čvora[uredi | uredi izvor]
Da bismo dodali čvor pre nekog drugog, menjamo vezu koja je pokazivala na stari čvor, koristeći vezu za prethodni; zatim podesimo vezu sa sledećim čvorom ovog čvora da pokazuje na stari, i promenimo vezu sa prethodni čvor tog čvora prema tome.
function insertBefore(Node node, Node newNode)
if node.prev == null
error "The node is not in a list"
newNode.prev := node.prev
atAddress(newNode.prev) := newNode
newNode.next := node
node.prev = addressOf(newNode.next)
function insertAfter(Node node, Node newNode)
newNode.next := node.next
if newNode.next != null
newNode.next.prev = addressOf(newNode.next)
node.next := newNode
newNode.prev := addressOf(node.next)
Brisanje čvora[uredi | uredi izvor]
Da bi smo uklonili čvor, jednostavno modifikujemo vezu koja pokazuje na prethodni, nezavisno da li je čvor prvi u listi.
function remove(Node node)
atAddress(node.prev) := node.next
if node.next != null
node.next.prev = node.prev
destroy node
Vidi još[uredi | uredi izvor]
- Lista (struktura podataka)
- XOR linked list
- SLIP (programming language)