PROFILPELAJAR.COM

У рачунарској науци, двоструко повезана листа је повезана структура података која се састоји из сета секвенцијално повезаних података званих чворови. Сваки чвор садржи два поља, звана везе, која су референце на претходни и следећи чвор у секвенци чворова. Претходна и следећа веза почетног и крајњег чвора, показују на неку врсту терминатора, типично на стражарски чвор или нулу, да би олакшало управљање листом. Ако постоји само један чвор чувар, онда је листа циркуларно повезана преко чвора стражара. То може бити конципирано као једноструко повезане листе формиране од истих података, али у обрнутим секвенцијалним редовима.

Двоструко повезана листа чији чворови садрже три поља: целобројну вредност, веза са следећим чвором, и веза са претходним чвором.

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

Концепт је такође основа за 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

Види још

Референце

[1] Avoiding game crashes related to linked lists - Code Of Honor

[2] [1]]

[1]

[2]