5-1. 이중 연결 리스트 (Doubly Linked List)

단순 연결 리스트 단점 보완 - 전위 node 접근을 용이하게 하기 위해 양방향 연결 field 가짐

 

이중 연결 리스트 class 정의

class DblList;		// 전방 선언

class DblListNode {
friend class DblList;
private:
   int data;
   DblListNode *left, *right;
};

class DblList {
public:
   // 연산 함수
private:
   DblListNode *first;	// head node
};

 

 

이중 연결 원형 리스트 삽입

void DblList::Insert (DblListNode *p, DblListNode *x){
// node x 오른쪽에 node p 삽입
   p->left = x; 
   p->right=x->right;
   x->right->left=p; 
   x->right=p;
}

 

 

이중 연결 원형 리스트 삭제

void DblList::Delete(DblListNode *x){
   if ( x == first )	// head node
      cerr << "Deletion of headnode not permitted" << endl;
   else {
      x->left->right = x->right;
      x->right->left = x->left;
      delete x;
   }
}