[4] 리스트 ⑤ 이중 연결리스트 : ADT
이중 연결리스트의 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);
}