이전 게시물에 이어서 연결리스트를 이루는 여러 함수들에 대해 알아보겠습니다.
ADT LinkedList
- LinkedList * new() : head와 tail을 초기화 합니다.
- delete_all(LinkedList *lk) : 연결리스트에 할당된 모든 메모리를 해제한다.
- size(LinkedList *lk) : 연결된 연결리스트의 갯수를 반환한다.
- add(LinkedList *lk, char data[]) : 연결리스트의 tail이 가리키는 노드 뒤에 다른 노드를 연결한다.
- insert(LinkedList *lk, int n, char data[]) : 원하는 부분에 노드를 삽입한다.
- delete(LinkedList *lk, int n) : 원하는 부분의 노드를 삭제한다.
- reverse(LinkedList *lk) : 연결리스트의 순서를 뒤집는다.
- *search(LinkedList *lk, char data[]) : 원하는 데이터의 위치를 탐색한다.
- edit(LinkedList *lk, node *target, char data[]) : 특정 노드의 데이터를 수정한다.
- print(LinkedList *lk) : 연결리스트의 처음부터 끝까지 출력한다.
해당 코드의 내용은 https://blog.naver.com/hirit808/221490070600의 내용을 참조했습니다.
이 다음 게시물인 연결리스트를 통해 스택과 큐를 구현하기 위한 초석입니다.
설명되는 순서는 실제로 선언된 순서이며, 게시물 하단에 전체 코드와 실행 결과가 있습니다.
실제 코드와 함께 설명드리겠습니다.
주석을 잘 보고 따라와 주세요!
이 색상의 주석은 제가 코드를 작성하며 주가한 주석입니다.
이 색상의 주석은 게시물을 작석하며 추가한 주석입니다.
2-1) 연결리스트 생성자, 소멸자
연결리스트의 처음과 끝을 가리키는 구조체 포인터와 연결리스트 전체를 삭제하는 함수입니다.
// 연결리스트 생성자
LinkedList * new(){ // 연결리스트를 사용하기 위한 head와 tail을 선언해줍니다.
LinkedList *lk = (LinkedList*)malloc(sizeof(LinkedList)); // 앞서 설명드린 것과 같습니다.
// 구조체 포인터 lk에 LinkedList의 멤버 변수를 사용할 수 있는 메모리를 할당해 줍니다.
lk->head = lk->tail = (node*)malloc(sizeof(node)); // 더미 노드 생성
// 이부분이 중요합니다.
// 이렇게 head와 tail을 묶어서 하나의 주소를 할당해주어야 뒤에 나올 연산이 가능합니다.
// "처음 생성자에서 head와 tail의 메모리 주소는 같다!"를 꼭 기억해주세요.
lk->head->next = NULL; // 더미 노드가 NULL을 가리키도록 초기화
lk->size = 0;
puts("-------------------------------------------------------");
printf("%40s\n", "Linked List Initiated.");
puts("-------------------------------------------------------");
return lk;
}
// 연결리스트 소멸자
void delete_all(LinkedList *lk){ // 현재까지 생성된 모든 연결리스트를 삭제합니다.
node *cur = lk->head; // 이렇게 해주면 cur는 head가 아니라 head가 가리키는 대상을 가리키게 된다.
// 아직 head에 뭐가 들어있는지 모르겠다. : head 노드의 주소를 포함하고 있다.
// cur이라는 node 구조체 포인터를 선언해주고 head의 주소를 넣어줍니다.
while(cur != NULL){
node *nxt = cur->next; // cur->next에는 다른 노드의 주소가 들어간다.
// 구조체 포인터 변수도 그냥 포인터 변수와 동일하게 생각하자!
// nxt는 cur의 next, 즉, head의 next인 첫번째 노드의 주소를 참조합니다.
free(cur); // 첫번째 반복 실행에서 cur이 참조하는 head의 메모리를 해제합니다.
cur = nxt; // 위에서 head의 메모리를 해제하고, cur은 첫번째 노드를 참조합니다.
// 같은 과정이 반복되며 마지막 노드의 메모리까지 해제합니다.
}
free(lk); // 마지막으로 LinkedList 구조체 포인터였던 lk의 메모리를 해제합니다.
puts("--------------------------------------------------");
printf("%40s\n", "Linked List Destructed.");
puts("--------------------------------------------------");
}
2-2) 연결리스트 노드 길이 반환
현재까지 생성된 연결리스트의 길이를 반환해줍니다.
// 연결 리스트 노드 길이 반환 (size)
int size(LinkedList *lk){
return lk->size; // 다음에 설명할 함수들에서 노드를 생성하고 삭제할 때 size의 크기를 변경해줍니다.
}
2-3) 연결리스트 노드 추가
현재 생성된 연결리스트의 마지막 노드 뒤에 새로운 노드를 추가하는 함수를 알아보겠습니다.
// 연결 리스트 노드 추가
void add(LinkedList *lk, char data[]) { // 사용자가 원하는 데이터와 함께 노드를 추가합니다.
node *tmp = (node*)malloc(sizeof(node)); // 현재 마지막 노드의 데이터를 임시롤 저장할 임시 노드를 생성해줍니다.
strcpy(tmp->data, data); // 저장하고자 하는 데이터를 임시 노드의 데이터에 옮겨줍니다.
//아래에서 tail의 주소를 0x01, tmp는 0x02라고 하겠습니다
tmp->next = NULL; // tmp(0x02)의 next는 마지막 노드가 가리겨야 할 주소(NULL == 0x00)를 가리키고 있습니다.
lk->tail->next = tmp; // 현재 tail(0x01)의 next는 tmp(0x02)를 가리킵니다.
lk->tail = tmp; // tail의 주소가 tmp의 주소(0x02)로 갱신됩니다.
// 이전에 tail의 주소였던 0x01의 next는 여전히 0x02를 가리킵니다.
// 가장 중요한 부분입니다.
// 처음 생성자에서 초기 head와 tail의 주소는 같습니다. 즉, 둘 다 초기값은 0x01입니다.
// 정리하면 다음과 같습니다.
// 0x01의 next는 0x02를 가리킵니다.
// 0x02의 next는 0x00(NULL)을 가리킵니다.
// 0x01은 head입니다. (위에서 tail의 주소만 tmp의 주소인 0x02로 갱신했기 때문입니다.)
// 0x02는 tail이자 tmp입니다.
// add를 한번 더 실행시켰을 때를 가정하겠습니다. 이때 새로 새성된 tmp의 주소는 0x03이라고 하겠습니다.
// 현재 tail(0x02)의 next는 tmp(0x03)을 가리킵니다.
// 다시 tail의 주소는 0x03으로 갱신되고, 여전히 0x02의 next는 0x03을 가리킵니다.
// 현재까지 생성된 연결리스트를 정리하면 다음과 같습니다.
// 0x01의 next는 0x02를 가리킵니다. ==> head는 여전히 0x01입니다.
==> 0x02에는 이전에 저장한 data 값이 있습니다.
// 0x02의 next는 0x03을 가리킵니다. ==> 0x03은 tail이자 tmp입니다.
// 0x03의 next는 0x00(NULL)을 가리킵니다.
++lk->size;
//free(tmp); // 절대 안됩니다. tmp의 주소는 현재 tail의 주소입니다. tmp를 해체하면 연결리스트를 추가했다가 바로 삭제하는 것입니다.
}
위의 내용을 이해하시면 아래 함수들은 이해하기 쉽습니다.
굉장히
2-4) 연결리스트 노드 삽입, 삭제
연결리스트에서 사용자가 원하는 위치에 노드를 삽입하거나
원하는 위치의 노드를 삭제하는 함수에 대해 알아보겠습니다.
// 연결 리스트 노드 삽입 (insert)
void insert(LinkedList *lk, int n, char data[]){ // 원하는 위치 n에 원하는 data를 삽입합니다.
if(n == size(lk) + 1) // 맨 끝에 삽입할 때는 그냥 add()를 호출한다.
add(lk, data); // 맨 끝 위치에 삽입하는 것은 add의 역할과 동일하다.
else if(n < 1 || n > size(lk) + 1) // 리스트 범위 밖이라면 error
printf("해당 위치 (%d)에 노드를 삽압할 수 없습니다.\n", n);
else{
node *tmp = (node *)malloc(sizeof(node));
strcpy(tmp->data, data);
node *cur = lk->head; // head의 next는 제일 처음 노드를 가리키기 때문에 cur이 head의 주소를 저장하도록한다.
while(--n) // n-1번만큼 반복된다.
cur = cur->next; // n-1번 헤당 연산을 끝낸 뒤 cur은 사용자가 원하는 위치 바로 앞 (n-1 번째)노드와 동일하다.
tmp->next = cur->next; // n에서 한칸 앞의 노드 (n-1 번째)가 가리키는 노드 (n 번째) 노드를 tmp의 next가 가리킨다.
cur->next = tmp; // n에서 한칸 앞의 노드 (n-1 번째)가 가리키는 노드를 tmp로 갱신한다. (tmp가 n 번째가 된다.)
// tmp는 이전에 n 번째 였던 노드를 가리킨다.
// 현재 tmp가 n 번째이므로, 이전에 n 번째 노드는 n+1 번째가 된다.
++lk->size;
}
}
// 연결 리스트 노드 삭제 (delete)
void delete(LinkedList *lk, int n){ // 원하는 위치 n 번째 노드를 삭제시킨다.
// 슬슬 예상이 되시죠? n-1 번째 노드가 n+1 번째 노드를 가리키게 하고,
// n 번째 노드의 동적할당된 메모리를 해제해주면 됩니다.
if(n < 1 || n > size(lk)) // 리스트 범위 밖이면 error
printf("해당 위치 (%d)의 노드를 삭제할 수 없습니다.\n", n);
else{
node *tmp;
node *cur = lk->head;
int i = n;
while(--i)
cur = cur->next;
tmp = cur->next; // 삭제할 노드는 cur 다음의 노드이다.
// cur이 n-1 번째이므로, cur->next는 n 번째 노드를 가리킨다.
cur->next = cur->next->next; // n-1 번째 노드인 cur의 next가 가리키는 노드를 n+1 번째 노드로 갱신한다.
if(n == size(lk))
lk->tail = cur; // 삭제할 노드가 끝 노드이먼 어차피 cur에 그 노드 앞의 노드가 저장되어 있으므로, tail이 cur을 가리키게 한다.
free(tmp); // n 번째 노드와 동일한 tmp를 해제해준다.
--lk->size;
}
}
2-5) 연결리스트 순서 뒤집기, 원하는 데이터 탐색, 원하는 노드의 데이터 수정
연결리스트 전체의 순서를 뒤집는 함수와 원하는 데이터를 포함하는 노드를 반환해주는 함수
원하는 노드의 데이터를 수정하는 함수를 알아보겠습니다.
// 연결 리스트 뒤집기 (reverse)
void reverse(LinkedList *lk){
if(size(lk) > 1){ // data가 2개 이상일 때만 로직을 수행한다.
node *cur = lk->head->next; // head의 next가 가리키는 첫번째 노드를 cur에 저장합니다.
node *nxt = cur->next; // nxt는 두번째 노드입니다.
node *tmp = nxt->next; // tmp는 세번째 노드입니다.
lk->tail = cur; // tail과 첫번째 노드를 같게 만들어줍니다.
lk->tail->next = NULL; // 원래 첫번째 노드는 두번째 노드를 가리키고 있었기 때문에
마지막 노드의 역할과 동일하게 NULL을 가리키도록 합니다.
for(;;){
nxt->next = cur; // 두번째 노드가 가리키는 주소가 tail이 되도록 만들어줍니다.
if(tmp == NULL) // tmp가 원래 연결리스트의 마지막 노드까지 가면 for 문을 종료합니다.
break;
cur = nxt; // cur을 두번째 노드(nxt)로 만들어줍니다.
nxt = tmp; // nxt를 세번째 노드(tmp)로 만들어줍니다.
tmp = tmp->next; // tmp를 네번째 노드(tmp->next)로 만들어줍니다.
} // 위와 같은 과정을 반복해줍니다.
// 아래와 같이 진행됩니다.
// head->1->2->3->4->5(tail)->NULL
// NULL<-1(tail)
// NULL<-1(tail)<-2
lk->head->next = nxt; // 반복문이 완료됐을 때 nxt는 원래 연결리스트의 마지막 노드와 동일합니다.
// 해당 노드를 head가 가리키게 해줍니다.
}
}
// 연결 리스트 노드 데이터 탐색 (search)
node *search(LinkedList *lk, char data[]){
node *cur = lk->head->next; // head의 next가 가리키는 첫번째 노드를 cur에 저장합니다.
while(cur !=NULL){ // cur이 마지막 노드가 가리키는 NULL이 되면 반복문을 종료합니다.
if(!strcmp(cur->data, data)){ // cur의 data와 찾고싶은 data를 비교한다.
// starcmp는 두 데이터가 일치하면 0을 반환한다.
printf("리스트에서 data \"%s\"을 찾았습니다.\n", data);
break;
}
cur = cur->next;
}
if(cur == NULL)
printf("데이터 \"%s\"이(가) 리스트에 존재하지 않습니다.\n", data);
return cur;
}
// 연결 리스트 노드 데이터 수정 (edit)
void edit(LinkedList *lk, node *target, char data[]){
// 이 함수는 다음과 같이 선언하여 사용합니다.
// edit(lk, search(lk, "수정 전 데이터"), "수정 후 데이터")
// search는 사용자가 원하는 데이터를 포함하는 노드를 포인터 형 변수(== 노드의 주소)로 반환해줍니다.
if(target == NULL)
puts("수정하려는 노드가 리스트에 없습니다.");
else
strcpy(target->data, data);
}
2-6) 연결리스트 출력
요건 앞에 함수를 이해하셨다면 한번 읽어만 보셔도 이해가 되실겁니다.
// 연결 리스트 출력 (print)
void print(LinkedList *lk){
node *cur = lk->head->next;
printf("리스트 구조:");
if(cur != NULL){
for(;;){
printf("%s", cur->data);
if(cur->next == NULL){
printf("\n");
break;
}
else
printf(" -> ");
cur = cur->next;
}
}
else
puts("No data");
}
2-7) main 함수 및 프로그램 실행 결과
int main(void){
LinkedList *lk = new();
add(lk, "리");
add(lk, "스");
add(lk, "트");
print(lk);
delete(lk, 2);
print(lk);
delete(lk, 1);
print(lk);
delete(lk, 1);
print(lk);
add(lk, "거");
add(lk, "꾸");
add(lk, "로");
print(lk);
reverse(lk);
print(lk);
return 0;
}
3개의 데이터를 저장하고, 2번째 글자를 삭제합니다.
다시 1번째 글자를 삭제하고, 다시 1번째 데이터를 삭제합니다.
이후 3개의 데이터를 새롭게 저장하고, 그 데이터를 저장한 노드의 순서를 뒤집어 줍니다.
다음 게시물에는 연결 리스트를 사용하여 스택과 큐를 구현하는 방법에 대해 설명드리겠습니다.
'Programming > C' 카테고리의 다른 글
| [자료구조 C 언어] C 프로그래밍 자료구조 - 8 : 연결리스트를 사용한 큐 (Queue) (0) | 2020.03.05 |
|---|---|
| [자료구조 C 언어] C 프로그래밍 자료구조 - 7 : 연결리스트를 사용한 스택 (Stack) (0) | 2020.03.05 |
| [자료구조 C 언어] C 프로그래밍 자료구조 - 6 : 연결리스트 (Linked List) (추가, 삽입, 삭제, 검색, 뒤집기 등) (0) | 2020.03.05 |
| [자료구조 C 언어] C 프로그래밍 자료구조 - 5 : 배열을 사용한 큐 (Queue) (0) | 2020.03.04 |
| [자료구조 C 언어] C 프로그래밍 자료구조 - 4 : 배열을 사용한 스택 (Stack) (0) | 2020.03.04 |