[C로 만드는 자료구조]리스트(List)- 이중 원형 연결 리스트

이중 연결 리스트

이중 원형 연결 리스트의 등장은 단순 연결의 문제점을 보완하기 위해 만들 수 있습니다. 어떤 문제점이 있을까요?

• 단순 연결 리스트의 문제점
  
  
• 선행 노드를 찾기 힘듬!(다시 돌아오거나 따로 소스를 복잡하게 짜서 받아놔야함)
• 삽입이나 삭제시에 반드시 선행 노드를 필요로함.

이런것을 보완하는게 이중 연결 리스트인데 이중 연결 리스트의 특징에 대해 알아 보겠습니다.

• 이중 연결 리스트의 특징
  
  
• 하나의 노드가 선행 노드와 후속 노드에 대한 두 개의 링크를 가지는 리스트
• 링크가 양방향이므로 양방향으로 검색이 가능
• 하지만 공간을 많이 차지하고 코드가 복잡하다는 단점을 가짐
  
  

이중 연결 리스트의 노드는 다음과 같은 형태와 소스를 가지게 됩니다.

typedef struct ListNode//노드 개별을 의미
{
    int VALUE;                        //노드에 포함된 값을 정의
    struct ListNode *Before;        //이전 노드를 가리키는 포인터
    struct ListNode *After;            //다음 노드를 가리키는 포인터
}ListNode;

노드에서 노드 자신의 앞, 뒤를 가리지는 링크 즉 포인터를 2개를 가지게 된 것이죠. 이 노드를 여러게 묶에 되면 다음과 같습니다.

양 끝은 NULL값을 가지고 있으며 노드간은 양쪽으로 연결 되어 있음을 확인할 수 있습니다.

이중 연결 리스트 - 삽입 연산

 

삽입 연산은 단순 연결과 같지만 양쪽으로 연결 하여야 하기 때문에 소스 코드가 길어집니다. 소스 구현은 ADT구현에서 하겠습니다.

이중 연결 리스트 - 삭제 연산

삭제 연산은 그나마 삽임 연산에 비해서는 간단합니다. 소스 구현은 ADT 구현에서 하겠습니다.

이중 연결 리스트 - ADT

ADT의 예시입니다. 역시 큰 차이는 없습니다.

이중 연결 리스트 - 구현

제가 구현시에는 이중 연결 원형 리스트로 구현을 하였습니다. 또한 이중 연결이 되어있으면 역방향 정방향 연산이 가능하므로 역방향 함수도 같이 구현을 하였습니다. (이중 연결 원형 리스트를 약간 수정을 가하면 이중 연결 리스트로 쉽게 만들 수 있습니다.)

우선 리스트 구현과 노드 구현에 사용할 구조체 입니다.

typedef struct ListNode//노드 개별을 의미
{
    int VALUE;                        //노드에 포함된 값을 정의
    struct ListNode *Before;        //이전 노드를 가리키는 포인터
    struct ListNode *After;            //다음 노드를 가리키는 포인터
}ListNode;
 
typedef struct List// 리스트 집단 
{
    ListNode *header = NULL;        //첫 노드를 가리키는 포인터
    ListNode *tailer = NULL;        //제일 끝 노드를 가리키는 포인터
}List;

단순 연결 리스트와 비교했을때 노드에는 양쪽을 가르켜야 하기 때문에 포인터가 하나더 추가 되었고 리스트 또한 마지막 노드를 나타내기 위한 tailer 포인터를 추가하였습니다.

제가 만든 ADT 목록입니다.

void Add_first(List *Target_List, int Item)
void Add(List *Target_List, int POSITION, int item)
void Push_Back(List *Target_List, int ITEM)
void Delete(List *Target_List, int POSITION)
void List_Initializer(List *Target_List)
void Replace(List *Target_List, int POSITION, int item)
void Find(List *Target_List, int item)
void Find_R(List *Target_List, int item)
void get_entry(List *Target_List, int POSITION)
void get_entry_R(List *TargetList, int POSITION)
void get_length(List *Target_List)
void Printing(List *Target_List)
void Printing_R(List *Target_List)

R이 붙어있는 함수는 역방향으로 진행하는 함수입니다. 그리고 Push_Back 이라는 함수는 제일 뒤에 노드를 삽입해 주는 것입니다.

• Add_First()
  
  

  void Add_first(List *Target_List, int Item)
  {
      ListNode *New = (ListNode *)malloc(sizeof(ListNode));        //새로 값을 넣을 곳(동적 할당)
      New->VALUE = Item;                                            //새로 만든 노드에 값 대입
      if (Target_List->header == NULL)//노드가 비었는지를 판단(노드가 비어있음)
      {
          Target_List->tailer = New;                    //원래 아무것도 없기 떄문에 테일러와 헤더를 설정해줘야함
          Target_List->tailer->After = New;            //테일러의 뒤을 설정 : New
          Target_List->tailer->Before = New;            //테일러의 앞을 설정 : New
          New->After = Target_List->tailer;            //New의 뒤를 설정 : 테일러
          New->Before = Target_List->tailer;            //New의 앞을 설정 : 테일러
          Target_List->header = New;                    //헤더로 처음 노드를 가리켜줌
          return;
      }
      if (Target_List->header != NULL)//노드가 비었는지를 판단(노드가 차있음)
      {
          New->Before = Target_List->header->Before;    //새로 생성하여 기존의 첫 노드의 앞 값을 받아옴
          Target_List->tailer->After = New;            //첫 노드가 변했기 때문에 테일러는 새로운 첫 노드를 가리킴
          New->After = Target_List->header;            //새로운 노드가 처음으로 가서 새로운 노드의 다음을 설정
          Target_List->header->Before = New;            //역시 반대로도 가르키게 설정
          Target_List->header = New;                    //헤더는 이제 새로운 첫 노드를 가리킴
          return;
      }
  }

  제일 처음에 해주는 노드입니다. 단순 연결에 비해 복잡하기 때문에 일일이 주석을 달아봤습니다. 무슨 리스트 구현이든지 그렇지만 이중 연결에서는 특히나 처음이 중요합니다. 처음이 잘되 있어야 모든 함수들이 올바르게 작동하게됩니다.
  
  

• Add()
  
  

  void Add(List *Target_List, int POSITION, int item)
  {
      if (POSITION == 1)                                //1번째의 경우와 그 이외의 경우의 연산 차이가 있으므로 1번 쨰 경우를 분리
      {
          Add_first(Target_List, item);
          return;
      }
      int pos = 1;                                    //위치 한계값 설정을 위해 지정
      ListNode *Cur = Target_List->header;
      ListNode *Temp = NULL;
      ListNode *New = (ListNode *)malloc(sizeof(ListNode));
      if (POSITION == 2)                                //시작시에 커서 이동을 해야하나 이전 것을 체크해줘야 하기 때문에 2번쨰와 그 이후를 분리
      {
          Temp = Cur;                                    
          Cur = Cur->After;
          New->VALUE = item;
          New->Before = Cur->Before;
          New->After = Temp->After;
          Temp->After = New;
          New->After = Cur;
          return;
      }
      Cur = Cur->After;
      pos++;
      while (pos > POSITION - 1)
      {
          Cur = Cur->After;
          pos++;
          if (pos = POSITION - 2)
              Temp = Cur;
      }
      New->VALUE = item;
      New->Before = Cur->Before;
      Cur->Before = New;
      New->After = Cur;
      Temp->After = Cur;
  }

  특정 위치 추가의 연산의 경우는 더 길게 됩니다. 이유는 12번째 줄 부터 23번째 줄에 있습니다. 1번째 와 2번째의 경우를 그냥 루프만을 돌리게 할 수 없는데 왜냐하면 루프의 조건은 header를 만나지 않으면 인데 처음 시작부가 header가 되기 때문에 우선 다음 노드로 이동을 시킨 뒤에 루프를 돌리기 때문에 그렇게 됩니다.
  
  

• Push_back()
  
  

  void Push_Back(List *Target_List, int ITEM)
  {
      ListNode *New = (ListNode *)malloc(sizeof(ListNode));
      ListNode *Cur = Target_List->tailer;
      if (Target_List->header == NULL)
      {
          Add_first(Target_List, ITEM);
          return;
      }
      New->After = Target_List->tailer->After;
      New->Before = Target_List->header->Before;
      Target_List->header->Before = New;
      Target_List->tailer->After = New;
      New->VALUE = ITEM;
  }

  다음은 가장 마지막에 노드를 추가해주는 Push_back함수 입니다. 마지막 노드를 추가 한 뒤에는 tailer를 새로 생성한 노드로 옮겨주어야합니다.
  
  

• Delete()
  
  

  void Delete(List *Target_List, int POSITION)
  {
      int pos = 1;
      ListNode *Temp = NULL;
      ListNode *Cur = Target_List->header;
      while (pos < POSITION)
      {
          if (pos == POSITION - 1)
              Temp = Cur;
          Cur = Cur->After;
          pos++;
      }
      Cur->After->Before = Cur->Before;
      Cur->Before->After = Cur->After;
      free(Cur);
  }

  삭제 연산은 단순 원형 연결과 비슷합니다. 대신 연결을 2번 해줘야 한다는 것만 조금 다릅니다.
  
  

• List_Initializer)
  
  

  void List_Initializer(List *Target_List)
  {
      Target_List->header = NULL;
      Target_List->tailer = NULL;
  }

  리스트 생성후 초기화때 쓰는 함수입니다. header와 tailer를 초기화 시켜줍니다.
  
  

• Replace
  
  

  void Replace(List *Target_List, int POSITION, int item)
  {
      int pos = 1;
      ListNode *Cur = Target_List->header;
      while (pos < POSITION)
      {
          Cur = Cur->After;
          pos++;
      }
      Cur->VALUE = item;
  }

  값만 교체하는 것이기 때문에 원리는 앞에 있는 단순 원형 연결과 같습니다.
  
  

• Find
  
  

  void Find(List *Target_List, int item)
  {
      ListNode *Cur = Target_List->header;
      int i = 1;
      if (Cur->VALUE == item)
          printf("%d 번째 노드에 %d가 있습니다.\n", i, item);
      i++;
      Cur = Cur->After;
      while (Cur != Target_List->header)
      {
          if (Cur->VALUE == item)
              printf("%d 번째 노드에 %d가 있습니다.\n", i, item);
          i++;
          Cur = Cur->After;
      }
  }

  정방향 탐색 연산입니다. 노드 추가와 같이 다음 노드로 한번 이동후 루프를 돌려야 하기 때문에 첫 번째 노드 탐색과 그 다음 노드들 탐색 연산을 따로 구현했습니다.
  
  

• Find_R()
  
  

  void Find_R(List *Target_List, int item)
  {
      ListNode *Cur = Target_List->tailer;
      int i = 1;
      if (Cur->VALUE == item)
          printf("%d 번째 노드에 %d가 있습니다.\n", i, item);
      i++;
      Cur = Cur->Before;
      while (Cur != Target_List->header)
      {
          if (Cur->VALUE == item)
              printf("%d 번째 노드에 %d가 있습니다.\n", i, item);
          i++;
          Cur = Cur->Before;
      }
  }

  역방향 탐색 연산입니다. 이 또한 이전 노드로 한번 이동후 루프를 돌려야하기 때문에 첫 번째 노드 탐색과 그 다음 노드들 탐색 연산을 따로 구현해놓았습니다.
  
  

• get_entry()
  
  

  void get_entry(List *Target_List, int POSITION)//정방향
  {
      int pos = 1;
      ListNode *Cur = Target_List->header;
      if (POSITION == 1)
      {
          printf("%d번째 노드에는 %d가 있습니다.\n", POSITION, Cur->VALUE);
          return;
      }
      Cur = Cur->After;
      pos++;
      while (pos < POSITION)
      {
          Cur = Cur->After;
          pos++;
      }
      printf("%d번째에는 %d가 있습니다.\n", POSITION, Cur->VALUE);
  }

  위의 탐색과 같이 첫 노드와 다른 노드를 분리하였습니다.
  
  

• get_entry_R()
  
  

  void get_entry_R(List *TargetList, int POSITION)//역방향
  {
      int pos = 1;
      ListNode *Cur = TargetList->header;
      if (POSITION == 1)
      {
          printf("%d번쨰 노드에는 %d가 있습니다.\n", POSITION, Cur->VALUE);
          return;
      }
      Cur = Cur->Before;
      pos++;
      while (pos < POSITION)
      {
          Cur = Cur->Before;
          pos++;
      }
      printf("%d번쨰 노드에는 %d가 있습니다.\n",POSITION,Cur->VALUE);
  }

  마찬가지 이며 다른점은 역방향으로 간다는 것 입니다.
  
  

• get_length()
  
  

  void get_length(List *Target_List)
  {
      ListNode *Cur = Target_List->header;
      int i = 1;
      i++;
      Cur = Cur->After;
      while (Cur != Target_List->header)
      {
          i++;
          Cur = Cur->After;
      }
      printf("노드의 개수는 %d개 입니다.\n", i);
  }

  길이를 구하는 함수입니다. 단순 연결 원형 리스트와 같지만 역시 다음 노드로 한번 이동후 루프를 돌리는 것을 볼 수 있습니다.
  
  

• is_empty()
  
  

  void is_empty(List *Target_List)
  {
      if (Target_List->header == NULL)
          printf("리스트가 비었습니다.\n");
      if (Target_List->header != NULL)
          printf("리스트에 내용이 있습니다.\n");
  }

  비어있는지를 확인하는 함수입니다. header의 NULL값 여부를 확인하여 비어있는 것인지 아닌지를 확인합니다.
  
  

• printing()
  

  void Printing(List *Target_List)
  {
      if (Target_List->header == NULL)
      {
          printf("There is No Node to display\n");
          return;
      }
      ListNode *Cur = Target_List->header;
      printf("%d -> ", Cur->VALUE);
      Cur = Cur->After;
      while (Cur != Target_List->header)
      {
          printf("%d -> ", Cur->VALUE);
          Cur = Cur->After;
      }
      printf("\n");
  }

  정방향으로 리스트 내의 모든 데이터를 출력하는 함수입니다. 여기서도 한번 다음 노드로 이동 후 루프를 돌려서 출력합니다.
  
  

• printing_R()
  
  

  void Printing_R(List *Target_List)
  {
      ListNode *Cur = Target_List->header;
      printf("%d -> ", Cur->VALUE);
      Cur = Cur->Before;
      while (Cur != Target_List->header)
      {
          printf("%d -> ", Cur->VALUE);
          Cur = Cur->Before;
      }
      printf("\n");
  }

  역방향으로 리스트 내의 모든 데이터를 출력하는 함수입니다. 이전 노드로 먼저 한번 이동후 루프를 돌려 출력합니다.

여기까지 리스트의 포스팅은 끝났습니다. 다음번에는 스텍(Stack) 포스팅을 하겠습니다.

같이 보기

2016/01/22 - [Programming/STL] - STL(Standard Template Library) - Container - List

2015/11/07 - [Programming/자료구조] - [C로 만드는 자료구조]리스트(List)- 단순 원형 연결 리스트

2015/11/06 - [Programming/자료구조] - [C로 만드는 자료구조]리스트(List) - 단순 연결 리스트(2/2)

2015/11/04 - [Programming/자료구조] - [C로 만드는 자료구조]리스트(List) - 단순 연결 리스트(1/2)

2015/11/04 - [Programming/자료구조] - [C로 만드는 자료구조]리스트(List) - 동적 연결 리스트

2015/11/02 - [Programming/자료구조] - [C로 만드는 자료구조]리스트(List) - 배열