[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

저작자표시

'Datastructure > [4] 리스트' 카테고리의 다른 글

[4] 리스트 ⑥ 이중 연결리스트 : ADT (1)	2024.05.06
[4] 리스트 ④ 이중 연결리스트 : 알고리즘 (0)	2024.05.06
[4] 리스트 ③ 단일 연결리스트: 다항식 (0)	2024.05.06
[4] 리스트 ② 단일 연결리스트 : ADT (0)	2024.05.06
[4] 리스트 ① 단일 연결리스트 (0)	2024.03.10

일	월	화	수	목	금	토
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30	31

우당탕탕 코딩 제작소

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

이중 연결리스트의 ADT

struct 구조체 선언

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

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

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

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

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

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

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

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

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

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

전체 코드

'Datastructure > [4] 리스트' 카테고리의 다른 글

티스토리툴바

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

이중 연결리스트의 ADT

struct 구조체 선언

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

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

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

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

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

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

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

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

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

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

전체 코드

'Datastructure > [4] 리스트' 카테고리의 다른 글

'Datastructure/[4] 리스트' 관련글

티스토리툴바