Двоструко повезана листа
У рачунарској науци, двоструко повезана листа је повезана структура података која се састоји из сета секвенцијално повезаних података званих чворови. Сваки чвор садржи два поља, звана везе, која су референце на претходни и следећи чвор у секвенци чворова. Претходна и следећа веза почетног и крајњег чвора, респективно, показују на неку врсту терминатора, типично на стражарски чвор или нулу, да би олакшало управљање листом. Ако постоји само један чвор чувар, онда је листа циркуларно повезана преко чвора стражара. То може бити конципирано као једноструко повезане листе формиране од истих података, али у обрнутим секвенцијалним редовима.
Две везе с чворовима омогућавају руковање листом с било које стране. Док додавање или склањање чвора у двоструко повезаној листи захтева мењање више веза него исте операције на једноструко повезаној листи, операције су једноставније и потенцијално ефикасније (за чворове који нису почетни) јер не постоји потреба за праћењем претходног чвора током руковања или не постоји потреба да се пређе листа да би се пронашао претходни чвор, тако да се његова веза може модификовати.
Концепт је такође основа за mnemonic link system memorization технику.
Номенклатура и имплементација уреди
Први и последњи чворови двоструко повезане листе су одмах доступне (тј., доступне без прелажења, и обично се називају глава и реп) и премда дозвољавају прелазак листе с почетка или краја листе, респективно: тј., прелажење листе од почетка до краја, или од краја до почетка, у потрази за чвором са одређеном вредношћу податка. Било који чвор у двоструко повезаној листи, једном када се добије, може да се искористи за почетак новог прелажења листе, у било ком правцу (према почетку или крају), од датог чвора.
Поља за везе чвора двоструко повезаних листи се често називају следећа и претходна или напред и назад. Референце сачуване у пољима за везе су често имплементиране као показивачи, али (као у свакој повезаној структури података) такође могу да буду офсети адреса или индекси у низу где живе чворови.
Основни алгоритми уреди
Размотрите следеће основне алгоритме написане у Ади:
Отворене двоструко повезане листе уреди
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
}
Преношење листе уреди
Прелажење двоструко повезане листе може да се одвија у било ком правцу. У ствари, правац преласка може да се промени пуно пута, ако то желимо. Прелазак се такође назива и итерација, али тај избор терминологије је несрећан, за итерацију постоји добро дефинисана семантика (тј., у математици) која није аналогна преласку.
Унапред
node := list.firstNode
while node ≠ null
<do something with node.data>
node := node.next
Уназад
node := list.lastNode
while node ≠ null
<do something with node.data>
node := node.prev
Убацивање чвора уреди
Ове симетричне функције убацују чвор или после или пре датог чвора:
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
Такође нам је потребна функција за убацивање чвора на почетак могуће празне листе:
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)
Симетрична функција убацује на крај:
function insertEnd(List list, Node newNode)
if list.lastNode == null
insertBeginning(list, newNode)
else
insertAfter(list, list.lastNode, newNode)
Уклањање чвора уреди
Уклањање чвора је лакше од убацивања, али захтева посебно руковање ако је чвор који треба да се уклони први или последњи чвор:
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
Једна мала последица горе поменуте процедура је да брисање последњег чвора листе поставља и први и последњи чвор на нулу, и тако се коректно рукује уклањањем чвора из једноелементне листе. Приметите да нам такође нису потребне методе уклони пре и уклони после, јер у двоструко повезаним листама можемо да користимо само једну за оба смера. Ово такође претпоставља да чвор који је уклоњен гарантовано постоји. Ако чвор не постоји у листи, онда је потребна нека врста руковања грешкама.
Циркуларна двоструко повезана листа уреди
Преношење листе уреди
Претпостављајући да неки чвор у непразној листи постоји, овај код пролази кроз ту листу почевши од тог чвора (било ког):
Унапред
node := someNode
do
do something with node.value
node := node.next
while node ≠ someNode
Уназад
node := someNode
do
do something with node.value
node := node.prev
while node ≠ someNode
//NODEPA Приметите одлагање теста на крају петље. Ово је важно у случају када листа садржи само један чвор односно тај чвор.
Додавање чвора уреди
Ова једноставна функција убацује чвор у у двоструко повезану циркуларно повезану листу након датог елемента:
function insertAfter(Node node, Node newNode)
newNode.next := node.next
newNode.prev := node
node.next.prev := newNode
node.next := newNode
Да би смо додали пре, једноставно можемо да "insertAfter(node.prev, newNode)".
Додавање елемента у могуће празну листу захтева посебну функцију:
function insertEnd(List list, Node node)
if list.lastNode == null
node.prev := node
node.next := node
else
insertAfter(list.lastNode, node)
list.lastNode := node
Да би смо додали на очетак ми једноставно "insertAfter(list.lastNode, node)".
Коначно, уклањање чвора мора да се избори са случајем када се листа испразни:
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
Имплементација двоструко повезане листе уреди
Следеће функције илуструју функционалност имплементацију двоструко повезаних листи у C/C++ програмским језицима. Функције за додавање, брисање, тражење, приказивање, уназад и детектовање циклуса у чворовима су приказане испод.
/*
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;
}
Напредни концепти уреди
Асиметрична двоструко повезана листа уреди
Асиметрична двоструко повезана листа је негде између једноструко повезане листе и регуларне двоструко повезане листе. Дели неке ставке са једноструко повезаном листом (прелажење у једном правцу) и неке из двоструко повезане листе (лакоћу модификације).
То је листа где веза за претходни чвор сваког чвора не показује на претходни чвор, већ на везу саму за себе. Док ово има мало разлике између чворова (само показује на офсет унутар претходног чвора), мења главу листе: дозвољава првом чвору да модификује везу с првим чвором врло лако. [1][2]
Докле год је чвор у листи, његова веза са претходним никада није нула.
Додавање чвора уреди
Да бисмо додали чвор пре неког другог, мењамо везу која је показивала на стари чвор, користећи везу за претходни; затим подесимо везу са следећим чвором овог чвора да показује на стари, и променимо везу са претходни чвор тог чвора према томе.
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)
Брисање чвора уреди
Да би смо уклонили чвор, једноставно модификујемо везу која показује на претходни, независно да ли је чвор први у листи.
function remove(Node node)
atAddress(node.prev) := node.next
if node.next != null
node.next.prev = node.prev
destroy node
Види још уреди
- Листа (структура података)
- XOR linked list
- SLIP (programming language)