[자료구조] 이중 연결 리스트

• 이중연결리스트(doublely linked list)

 - 두 개의 포인터를 사용하여 선행 노드와 후속 노드에 모두 연결되는

   양방향 구조

 ‣ 자료삽입

   (1) 새로운 노드 생성하여 데이터 영역에 자료(나)를 저장

   (2) (나)의 오른쪽 포인터 영역이 다음 노드(다)를 가리키게 하고,

         (나)의 왼쪽 포인터 영역이 이전 노드(가)를 가리키게 함

   (3) 후속 노드(다)의 왼쪽 포인터 영역이 (나)를 가리키게 하고,

         선행 노드(가)의 오른쪽 포인터 영역 역시 (나)를 가리키게 함

 

맨 앞 삽입 코드

void insert_front_dnode(int data) {
	// 삽입할 새로운 node 선언
    Dnode* newNode = (Dnode*)malloc(sizeof(Dnode));
    newNode -> value = data;
    newNode -> prev = NULL;
    newNode -> next = NULL;
    
    if (head == NULL) {		// 리스트가 비어있다면
    	head = newNOde;
        tail = newNode;
        return;
	}
    
    // newNode의 next가 head를 가리키는 노드를 가리킬 수 있도록 함
    newNode -> next = head;
    
    // head가 가리키는 노드의 이전 포인터가 newNode를 가리키도록 함
    head -> prev = newNode;
    
    // head가 newNode를 가리킬 수 있도록 함
    head = newNode;
}

맨 뒤 삽입 코드

void insert_rear_dnode(int data) {
	// 삽입할 새로운 node 선언
    Dnode* newNode = (Dnode*)malloc(sizeof(Dnode));
    newNode -> value = data;
    newNode -> prev = NULL;
    newNode -> next = NULL;
    
    if (head == NULL) {		// 리스트가 비어있다면
    	head = newNOde;
        tail = newNode;
        return;
	}
    
    // newNode의 prev가 tail이 가리키는 노드를 가리킬 수 있도록 함
    newNode -> prev = tail;
    
    // tail이 가리키는 이전 노드가 다음 노드로 newNode를 가리키도록 함
    tail -> next = newNode;
    
    // tail이 newNode를 가리키도록 함
    tail = newNode;
}

 

 ‣ 자료삽입

   (1) 삭제하고자 하는 노드(나)의 이전 노드(가)의 오른쪽 포인터 영역이

         다음 노드(다)를 가리키게 함
   (2) 삭제하고자 하는 노드(나)의 다음 노드(다)의 왼쪽 포인터 영역이

         이전 노드(가)를 가리키게 함

 

맨 앞 삭제 코드

void remove_front_dnode() {
	Dnode* delNode;			// 삭제할 노드를 저장할 노드 선언
    
    if (head == NULL) {		// 리스트가 비어있는 경우
    	return;
    }
    
    delNode = head;			// 삭제할 node를 delNode에 저장
    // 헤드가 가리키는 노드의 다음 노드를 가리키도록 설정
    head = head -> next;
    free(delNode);			// 삭제된 node의 메모리 제거
    
    if(head)				// head가 존재 한다면
    	head -> prev = NULL;// head의 이전 포인터를 NULL
    
    if(!head)				// head가 존재하지 않는다면
    	tail = NULL;		// list가 없다는 것으로 tail도 NULL
}

맨 뒤 삭제 코드

void remove_rear_dnode() {
	Dnode* delNode;			// 삭제할 노드를 저장할 노드 선언
    
    if (head == NULL) {		// 리스트가 비어있는 경우
    	return;
    }
    
    delNode = tail;			// 삭제할 node를 delNode에 저장
    // tail이 가리키는 노드가 이전 노드를 가리키도록 함
    tail = tail -> prev;
    free(delNode);			// 삭제된 node의 메모리 제거
    
    if(tail)				// tail이 존재 한다면
    	tail -> next = NULL;// tail의 다음 포인터를 NULL
	
    if(!tail)				// tail이 존재하지 않는다면
    	head = NULL;		// list에 값이 없다는 것으로 head도 NULL
}