#2-4. 이중 연결 리스트의 생성

이전 포스팅까지 다룬 연결리스트는 링크를 하나만 갖는 단일 연결리스트이다. 그런데 연결리스트에는 2개의 링크를 갖는 이중 연결리스트와 연결리스트가 원형으로 구성된 원형 연결리스트가 있다.

 

이번 차시에는 이중 연결리스트를 기준으로 다른 구조의 연결리스트를 살펴보자.

이중 연결리스트

이중 연결리스트

각각의 노드가 다음 값 위치를 저장하는 next 구조체 포인터와 이전 값 위치를 저장하는 pre 값을 가진다.

이중 연결리스트는 haed 노드와 tail 노드를 가지며 두 노드는 연결되어 있지 않다.

이중 연결리스트

원형 (이중) 연결리스트

각각의 노드가 next와 pre 구조체 포인터를 가진다는 점에서 일반 이중 연결리스트와 같으나 head 노드와 tail 노드가 서로 연결되어 원형의 형태를 이룬다.

원형 (이중) 연결리스트

이중 연결리스트의 삽입과 삭제 알고리즘

이중 연결리스트의 생성

먼저 이중 연결리스트의 생성에 앞서, 이중 연결리스트를 생성해 보고 이중 연결을 확인해 보자.

typedef struct ListNode {
  element data;
  struct ListNode *next;
  struct ListNode *pre;
} ListNode;

void Initialize(ListNode *head, ListNode *tail) {
  ListNode *NodeArr[5];
  for (int i = 0; i < 5; i++)
    NodeArr[i] = (ListNode *)malloc(sizeof(ListNode));

  for (int i = 0; i < 5; i++) {
    if (i == 0) {
      head->next = NodeArr[i];
      NodeArr[i]->data = 'A';
      NodeArr[i]->pre = head;
    } else {
      NodeArr[i - 1]->next = NodeArr[i];
      NodeArr[i]->pre = NodeArr[i - 1];
      NodeArr[i]->data = 'A' + i;
      printf("<<NodeArr[i]->data: %c | NodeArr[i]->pre->data: %c>>\n",
             NodeArr[i]->data, NodeArr[i]->pre->data);
    }
  }
  NodeArr[4]->next = tail;
  tail->pre = NodeArr[4];
}

이중 연결리스트 구조체를 선언할 때 next와 pre를 선언한 것을 볼 수 있고, 연결리스트의 생성에서 각각의 노드들을 서로 앞뒤 연결한 것을 확인할 수 있다.

ListNode *head = (ListNode *)malloc(sizeof(ListNode)); //헤드 노드 생성
ListNode *tail = (ListNode *)malloc(sizeof(ListNode)); //테일 노드 생성
head->next = NULL;

Initialize(head, tail);

단일 연결리스트에 비해 헤드 노드와 테일 노드가 이중 연결에서 마지막을 구분하고 판단하는 기준이 되므로 따로 분명히 하기 위해 선언해 준다.

/*순회용 노드*/
  printf("[기본 연결리스트의 값] ");
  int cnt = 0;
  ListNode *chc = head->next;
  while (chc != NULL) { //연결리스트 출력
    printf("%c ", chc->data);
    chc = chc->next;
    cnt++;
  }
  cnt--;
  printf("\ncnt = %d\n", cnt);

  ListNode *prt = (ListNode *)malloc(sizeof(ListNode));
  prt = tail;
  prt = prt->pre;
  printf("[연결리스트의 반전 값] ");
  while (cnt > 0) {
    printf("%c ", prt->data);
    prt = prt->pre;
    cnt--;
  }

순회용 노드를 통해 연결리스트가 정방향, 역방향 각각 next, pre 구조체 포인터를 통해 작동하는지 확인해 볼 수 있다.

이제 이중 연결리스트의 생성을 성공했다. 시간 상 다음 포스팅에서 이를 다시 수정해 이중 연결리스트의 삽입과 삭제 함수를 작성해 보자.

전체 코드

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef char element;

typedef struct ListNode {
  element data;
  struct ListNode *next;
  struct ListNode *pre;
} ListNode;

void Initialize(ListNode *head, ListNode *tail) {
  ListNode *NodeArr[5];
  for (int i = 0; i < 5; i++)
    NodeArr[i] = (ListNode *)malloc(sizeof(ListNode));

  for (int i = 0; i < 5; i++) {
    if (i == 0) {
      head->next = NodeArr[i];
      NodeArr[i]->data = 'A';
      NodeArr[i]->pre = head;
    } else {
      NodeArr[i - 1]->next = NodeArr[i];
      NodeArr[i]->pre = NodeArr[i - 1];
      NodeArr[i]->data = 'A' + i;
      printf("<<NodeArr[i]->data: %c | NodeArr[i]->pre->data: %c>>\n",
             NodeArr[i]->data, NodeArr[i]->pre->data);
    }
  }
  NodeArr[4]->next = tail;
  tail->pre = NodeArr[4];
}

int main() {

  ListNode *head = (ListNode *)malloc(sizeof(ListNode)); //헤드 노드 생성
  ListNode *tail = (ListNode *)malloc(sizeof(ListNode)); //테일 노드 생성
  head->next = NULL;

  Initialize(head, tail);

  /*순회용 노드*/
  printf("[기본 연결리스트의 값] ");
  int cnt = 0;
  ListNode *chc = head->next;
  while (chc != NULL) { //연결리스트 출력
    printf("%c ", chc->data);
    chc = chc->next;
    cnt++;
  }
  cnt--;
  printf("\ncnt = %d\n", cnt);

  ListNode *prt = (ListNode *)malloc(sizeof(ListNode));
  prt = tail;
  prt = prt->pre;
  printf("[연결리스트의 반전 값] ");
  while (cnt > 0) {
    printf("%c ", prt->data);
    prt = prt->pre;
    cnt--;
  }
  return 0;
}