본문 바로가기

Datastructure/[4] 리스트

[4] 리스트 ⑤ 이중 연결리스트 : ADT

728x90
반응형

이중 연결리스트의 ADT

단일 연결리스트의 ADT에 포함된 함수와 설명은 아래 링크를 참조한다.
 
 

[4] 리스트 ④ 이중 연결리스트 : 알고리즘

이중 연결리스트의 알고리즘 이중 연결 리스트는 두 방향으로 연결되어 있다. 따라서 나와 연결된 다음 노드와 내 이전 노드를 알 수 있다. 따라서 역행하여 노드를 확인하거나 추가/수정에 용

udangtangtang-cording-oldcast1e.tistory.com

struct 구조체 선언

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

typedef int element;
  • 데이터의 자료형을 element로 정의한다.
typedef struct DListNode{
   element data;
   struct DListNode* prev;
   struct DListNode* next;
}DListNode;
  • 연결리스트 노드를 선언한다.
  • 연결리스트의 데이터와 이전(prev)/다음(next) 노드의 방향을 나타낼 구조체 포인터 선언한다.
void init(DListType* DList) {
   DList->Head = NULL;
   DList->Tail = NULL;
   DList->size = 0;
}
  • 연결리스트 노드 타입을 선언한다.
  • 연결리스트의 헤더 노드와 테일 노드를 선언하고, 연결리스트의 개수를 저장한 size 변수를 선언한다.
  • 이때 헤드와 테일 노드는 값이 저장되는 유효 노드로서 동작한다.

init 함수: 연결리스트 초기화

① 리스트의 Head와 Tail를 NULL로 선언한다. 이때 인자로 받는 같은 DListType 값이다.

② 이중 연결리시트는 이전과 다음 노드로의 접근이 가능하다.

③ 리스트의 사이즈를 초기화한다.

void init(DListType* DList) {
   DList->Head = NULL;
   DList->Tail = NULL;
   DList->count = 0;
}

insertFirst 함수 : 연결리스트의 첫 부분에 노드 추가

① 새로운 노드(new)를 동적 할당한다.

② 인자로 받은 노드 타입의 헤드(Head) 노드를 저장할 임의의 노드 p를 동적할당한다.

③ 새로운 노드(new)에 값을 저장한다.

new의 이전 노드는 NULL이다. (∵ 연결리스트의 첫 노드 이전 값은 항상 NULL)

⑤ new의 next를 p 혹은 Head 노드와 연결한다.

p가 NULL이라면, Head와 Tail 노드에 new를 저장한다. (∵ 노드가 한 개일 때 헤드와 테일 노드가 같다.)

p가 NULL이 아니라면, p의 이전 노드에 new를 저장한다.

헤드 노드new를 저장한다. ⭐️⭐️⭐️

연결리스트의 개수를 증가한다.

void insertFirst(DListType* DList, element e) {
   DListNode* new = (DListNode*)malloc(sizeof(DListNode));
   //새로운 노드 동적할당
   DListNode* p = DList->Head;
   new->data = e; // 새로운 노드에 값 저장
   new->prev = NULL; // 새로운 노드의 이전 노드를 NULL : 첫 노드이므로
   
   new->next = p;// 새로운 노드의 next를 H(헤드)를 저장한 p로 연결

   if (p == NULL) {DList->Head = DList->Tail = new;}//p가 널이면 헤드-테일을 각각 new로 초기화
   else {//아니라면
      p->prev = new;//헤드를 저장한 p의 이전 노드를 new로 설정
      DList->Head = new;//연결리스트의 헤드를 new로 설정
   }

   DList->size++;
}

 

insertLast 함수 : 연결리스트의 뒷 부분에 노드 추가

① 새로운 노드(new)를 동적 할당한다.

② 인자로 받은 노드 타입의 헤드(Head) 노드를 저장할 임의의 노드 p를 동적할당한다.

③ 새로운 노드(new)에 값을 저장한다.

 new의 이전 노드는 NULL이다. (∵ 연결리스트의 첫 노드 이전 값은 항상 NULL)

⑤ new의 next를 p 혹은 Head 노드와 연결한다.

 p가 NULL이라면, Head와 Tail 노드에 new를 저장한다. (∵ 노드가 한 개일 때 헤드와 테일 노드가 같다.)

 p가 NULL이 아니라면, p의 다음 노드에 new를 저장한다.

 테일 노드 new를저장한다. ⭐️⭐️⭐️

 연결리스트의 개수를 증가한다

void insertLast(DListType* DList, element e) {
   DListNode* new = (DListNode*)malloc(sizeof(DListNode));
   //새로운 노드 동적할당
   
   DListNode* p = DList->Tail;
   //테일 노드를 저장하는 노드

   new->data = e; // 새로운 노드에 값 저장
   new->prev = p; //새로운 노드를 테일의 이전 노드와 연결
   new->next = NULL;//새로운 노드의 다음은 NULL : 마지막에 추가했음

   if (p == NULL) {DList->Head = DList->Tail = new;}
   else {
      p->next = new;//테일 노드의 다음을 new로 지정 : new가 추가됨
      DList->Tail = new;//테일 초기화
   }
   DList->size++;
}

insert함수: 연결리스트의 노드 추가 함수(pos: 노드를 추가할 위치)

insert 함수의 기본 로직은 아래와 같다.

 

ⓞ 노드를 추가할 순위가 유효하지 않은 경우 오류 문구를 출력하고 함수를 종료한다.

① 새로운 노드(new)를 동적 할당한다.

② 인자로 받은 노드 타입의 헤드(Head) 노드를 저장할 임의의 노드 p를 동적할당한다.

rank의 값이 1이라면, 노드의 첫 번째의 값을 추가하는 것이므로 insertFirst함수를 실행한다.

rank의 값이 (DList->size + 1)이라면, 노드의 끝에 값을 추가하는 것이므로 insertLast함수를 실행한다.

rank의 값이 ③,④ 조건에 맞지 않는 경우 pos의 위치까지 이동한다.(순회)

⑥ new에 값을 저장한다. 

연결리스트의 연결을 진행한다. ⭐️⭐️⭐️

new->prev = p->prev;  
new->next = p;

 p->prev->next = new;
p->prev = new;

 

⑧ 노드의 사이즈를 증가한다.

void insert(DListType* DList, int pos, element e) {
   if (pos < 1 || pos > DList->size) {
        printf("Invalid pos\n");
        return ;
    }
   DListNode* new = (DListNode*)malloc(sizeof(DListNode));
   DListNode* p = DList->Head;//임의의 노드 생성

   if (pos == 1) {//맨 처음에 추가
      insertFirst(DList, e);
   }
   else if (pos == DList->size + 1) {//(맨 마지막 + 1)위치 추가
      insertLast(DList, e);
   }
   else {//처음과 마지막 노드가 아닌경우
      for (int i = 1; i < pos; i++) {p = p->next;}
      //원하는 위치까지 이동
      new->data = e;//새로운 노드에 값 저장
      new->prev = p->prev;
      // 새로운 노드의 이전 노드를 원래 해당 위치에 있던 노드의 이전 노드로
      new->next = p;
      //새로운 노드의 다음 노드를 원래 위치의 노드로 설정
      
      p->prev->next = new;
      //기존 위치의 이전 노드의  next를 새로운 노드로 : 이중연결리스트
      p->prev = new;
      //기존 위치의 이전 노드를 새로운 노드로

      DList->size++;
   }
}

deleteFirst 함수: 연결리스트의 첫 부분에 노드 삭제

① DList->Head (헤드 노드)가 NULL이면 -1을 리턴한다. 즉, 아무것도 수행하지 않는다.

② del이라는 연결리스트 노드를 선언하고 헤드 노드를 저장한다.

리스트의 헤드 노드에 del의 next를 저장한다. 이는 헤드 노드가 값을 저장하는 유효 노드이기 때문에 가능하다. 

삭제할 노드의 값(output)을 저장한다.

  노드의 사이즈를 감소한다.

 output을 반환한다.

element deleteFirst(DListType* DList) {//삭제되는 값을 반환한다.
   if(DList->size == 0){
      printf("invaild connection");
      return -1;
   }
   else{
      DListNode* del =  DList->Head;
      element ouput = del->data;
      //입력받은 연결리스트의 다음 노드, 즉 값을 가지는 노드를 del에 저장
      DList->Head = del->next;
      DList->size --;
      return ouput;
   }  
}

deleteLast함수: 연결리스트의 끝 부분에 노드 삭제

① DList->Tail (테일 노드)가 NULL이면 -1을 리턴한다. 즉, 아무것도 수행하지 않는다.

② del이라는 연결리스트 노드를 선언하고 테일 노드를 저장한다.

 삭제할 노드의 값(output)을 저장한다.

연결리스트의 테일 노드값을 NULL로 만든다.

del의 이전노드의 다음노드(del->prev->next)를 del의 다음 노드로(del->next)로 설정한다.

연결리스트의 테일 노드 값에 del->prev을 저장한다.

 output을 반환한다.

⭐️⭐️⭐️⭐️⭐️

 

DList->Tail = NULL;
(del->prev->next) = DList->Tail;
DList->Tail = del->prev;
element deleteLast(DListType* DList) {
   DListNode* del = DList->Tail;
   element ouput = del->data;
   // printf("삭제할 노드의 값: %d\n",del->data);
   DList->Tail = NULL;
   (del->prev->next) = DList->Tail;
   DList->Tail = del->prev;
   return ouput;
}

delete함수: 연결리스트의 노드 삭제 함수(pos: 노드를 삭제할 위치)

① 노드를 추가할 순위가 유효하지 않은 경우 오류 문구를 출력하고 함수를 종료한다.

② 헤드(Head)노드를 저장할 임의의 노드 p에 헤드노드를 저장한다.

rank의 값이 1이라면, 노드의 첫 번째의 값을 추가하는 것이므로 deleteFirst함수를 실행한다.

rank의 값이 (DList->size)이라면, 노드의 끝에 값을 추가하는 것이므로 deleteLast함수를 실행한다.

위 두 조건을 만족하지 않는 경우, pos의 위치까지 이동한다.(순회)

⑤ rank의 위치까지 이동한다.(순회)

 다음 노드가 있으면, 앞 뒤의 두 노드를 연결한다.

다음 노드가 없으면, 뒤 노드와 NULL을 연결한다.

⑨  노드의 사이즈를 감소한다.

output을 반환한다.

⭐️⭐️⭐️⭐️⭐️

 

if (p->next) {//다음 노드가 있으면 
     p->prev->next = p->next; 
     p->next->prev = p->prev;

else  p->prev->next = NULL;//다음 노드가 없으면
element delete(DListType* DList, int pos){
   DListNode* p = DList->Head;//리스트의 헤드 노드를 p에 저장
   element rtn; //반환값
   if (pos == 1) {rtn = deleteFirst(DList);}
   else if (pos == DList->size) {rtn = deleteLast(DList);}
   else {
      for (int i = 1; i < pos; i++) {p = p->next;}
      //원하는 위치로 이동
      rtn = p->data;//원하는 위치의 노드 : 삭제할 노드 -> 반환값 저장
      if (p->next) {//다음 노드가 있으면
      //노드 연결
         p->prev->next = p->next;
         p->next->prev = p->prev;
      }
      else {//다음 노드가 없으면 
         p->prev->next = NULL;
      }
      DList->size--;
      free(p);
   }
   return rtn;
}

getNode함수: 연결리스트의 값 확인 함수 rank: 노드를 확인할 위치)

① 노드를 확인할 순위가 유효하지 않은 경우 오류 문구를 출력하고 함수를 종료한다.

② 헤드(Head)노드를 저장할 임의의 노드 p에 헤드노드를 저장한다.

③ rank의 위치까지 이동한다.

④ rank의 위치의 노드의 값을 반환한다.

element get(DListType* DList, int rank) {
    if (rank < 1 || rank > DList->size) {
        printf("Invalid rank\n");
        return -1; // 유효하지 않은 순위일 경우 -1 반환
    }
    DListNode* p = DList->Head;
    for (int i = 1; i < rank; i++) {
        p = p->next;
    }
    return p->data;
}

isEmpty함수: 연결리스트가 비어있는지 확인하는 함수

① 노드의 헤드가 NULL이면 1을 반환한다.

int isEmpty(DListType* DList) {
   return DList->Head == NULL;
   //return DList->Tail == NULL; // 둘 중에 하나만 쓰면 됨
}

print함수: 연결리스트 출력 함수

① 헤드(Head)노드를 저장할 임의의 노드 p에 헤드노드를 저장한다.

② 임의의 노드 p를 이용해 p의 next가 NULL이 아닐 때까지 순회하며 노드의 데이터를 출력한다.

void print(ListType* DList) {
   for (Listnode* p = DList->Head; p != NULL; p = p->next) {
      printf("[%d] -> ", p->data);
   }printf("\b\b\b\b   \n");
}

전체 코드

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

typedef int element;

typedef struct DListNode{
   element data;
   struct DListNode* prev;
   struct DListNode* next;
}DListNode;

typedef struct {
   DListNode* Head;
   DListNode* Tail;
   int size;
}DListType;

void init(DListType* DList) {
   DList->Head = NULL;
   DList->Tail = NULL;
   DList->size = 0;
}

void insertFirst(DListType* DList, element e) {
   DListNode* new = (DListNode*)malloc(sizeof(DListNode));
   //새로운 노드 동적할당
   DListNode* p = DList->Head;
   new->data = e; // 새로운 노드에 값 저장
   new->prev = NULL; // 새로운 노드의 이전 노드를 NULL : 첫 노드이므로
   
   new->next = p;// 새로운 노드의 next를 H(헤드)를 저장한 p로 연결

   if (p == NULL) {DList->Head = DList->Tail = new;}//p가 널이면 헤드-테일을 각각 new로 초기화
   else {//아니라면
      p->prev = new;//헤드를 저장한 p의 이전 노드를 new로 설정
      DList->Head = new;//연결리스트의 헤드를 new로 설정
   }

   DList->size++;
}

void insertLast(DListType* DList, element e) {
   DListNode* new = (DListNode*)malloc(sizeof(DListNode));
   //새로운 노드 동적할당
   
   DListNode* p = DList->Tail;
   //테일 노드를 저장하는 노드

   new->data = e; // 새로운 노드에 값 저장
   new->prev = p; //새로운 노드를 테일의 이전 노드와 연결
   new->next = NULL;//새로운 노드의 다음은 NULL : 마지막에 추가했음

   if (p == NULL) {DList->Head = DList->Tail = new;}
   else {
      p->next = new;//테일 노드의 다음을 new로 지정 : new가 추가됨
      DList->Tail = new;//테일 초기화
   }
   DList->size++;
}

void insert(DListType* DList, int pos, element e) {
   if (pos < 1 || pos > DList->size) {
        printf("Invalid pos\n");
        return ;
    }
   DListNode* new = (DListNode*)malloc(sizeof(DListNode));
   DListNode* p = DList->Head;//임의의 노드 생성

   if (pos == 1) {//맨 처음에 추가
      insertFirst(DList, e);
   }
   else if (pos == DList->size + 1) {//(맨 마지막 + 1)위치 추가
      insertLast(DList, e);
   }
   else {//처음과 마지막 노드가 아닌경우
      for (int i = 1; i < pos; i++) {p = p->next;}
      //원하는 위치까지 이동
      new->data = e;//새로운 노드에 값 저장
      new->prev = p->prev;
      // 새로운 노드의 이전 노드를 원래 해당 위치에 있던 노드의 이전 노드로
      new->next = p;
      //새로운 노드의 다음 노드를 원래 위치의 노드로 설정
      
      p->prev->next = new;
      //기존 위치의 이전 노드의  next를 새로운 노드로 : 이중연결리스트
      p->prev = new;
      //기존 위치의 이전 노드를 새로운 노드로

      DList->size++;
   }
}
element deleteFirst(DListType* DList) {//삭제되는 값을 반환한다.
   if(DList->size == 0){
      printf("invaild connection");
      return -1;
   }
   else{
      DListNode* del =  DList->Head;
      element ouput = del->data;
      //입력받은 연결리스트의 다음 노드, 즉 값을 가지는 노드를 del에 저장
      DList->Head = del->next;
      DList->size --;
      return ouput;
   }  
}
element deleteLast(DListType* DList) {
   if (DList->Tail == NULL) return -1; 
    
   DListNode* del = DList->Tail;
   element ouput = del->data;
   // printf("삭제할 노드의 값: %d\n",del->data);
   DList->Tail = NULL;
   (del->prev->next) = DList->Tail;
   DList->Tail = del->prev;
   return ouput;
}

element delete(DListType* DList, int pos){
   if (pos < 1 || pos > DList->size) {
        printf("Invalid pos\n");
        return -1;
    }
   DListNode* p = DList->Head;//리스트의 헤드 노드를 p에 저장
   element output; //반환값
   if (pos == 1) {output = deleteFirst(DList);}
   else if (pos == DList->size) {output = deleteLast(DList);}
   else {
      for (int i = 1; i < pos; i++) {p = p->next;}
      //원하는 위치로 이동
      output = p->data;//원하는 위치의 노드 : 삭제할 노드 -> 반환값 저장
      if (p->next) {//다음 노드가 있으면
         p->prev->next = p->next;
         p->next->prev = p->prev;
      }
      else  p->prev->next = NULL;//다음 노드가 없으면 
      
      DList->size--;
      free(p);
   }
   return output;
}

int isEmpty(DListType* DList) {
   return DList->Head == NULL;
   //return DList->Tail == NULL; // 둘 중에 하나만 쓰면 됨
}

void print(DListType* DList) {
   for (DListNode* p = DList->Head; p != NULL; p = p->next) {
      printf("[%d] <=> ", p->data);
   }printf("\b\b\b\b   \n");
}

element get(DListType* DList, int rank) {
    if (rank < 1 || rank > DList->size) {
        printf("Invalid rank\n");
        return -1; // 유효하지 않은 순위일 경우 -1 반환
    }
    DListNode* p = DList->Head;
    for (int i = 1; i < rank; i++) {
        p = p->next;
    }
    return p->data;
}

int main() {
   DListType DList; // 구조체 변수여서 .을 사용
   init(&DList);
   printf("--------------------insertFirst--------------------\n");
   insertFirst(&DList, 20); print(&DList);
   insertFirst(&DList, 10); print(&DList);
   printf("--------------------insertLast--------------------\n");
   insertLast(&DList, 40); print(&DList);
   insertLast(&DList, 50); print(&DList);
   printf("----------------------insert---------------------\n");
   insert(&DList, 1, 70); print(&DList);
   insert(&DList, DList.size , 100); print(&DList);
   insert(&DList, 4, 80); print(&DList); 
   printf("--------------------deleteFirst------------------\n");
   deleteFirst(&DList);print(&DList);
   printf("--------------------deleteLast-------------------\n");
   deleteLast(&DList);print(&DList);
   printf("----------------------delete---------------------\n");
   delete(&DList, 1); print(&DList);


   // printf("-------------delete: check return value-----------\n");
   // printf("delte list number: ");
   // int input; scanf("%d",&input);
   // printf("[%d] is deleted.\n",delete(&DList,input));
   // print(&DList);
   printf("%d",DList.Head->data);

}
728x90
반응형
댓글