[4] 리스트 ② 단일 연결리스트 : ADT
단일 연결리스트의 ADT
단일 연결리스트의 ADT에 포함된 함수와 설명은 아래 링크를 참조한다.
[4] 리스트 ① 단일 연결리스트
추상자료형추상자료형이란 데이터 구조의 추상형으로서 데이터가 컴퓨터에 저장되고 실행되는 기계적인 메커니즘과는 구분되어 인간이 데이터를 다루는 관점에서 데이터구조를 명세한 것을
udangtangtang-cording-oldcast1e.tistory.com
단일 연결리스트의 ADT 구현 (1): 함수 분리
아래 알고리즘에서 단일 연결리스트의 헤더노드는 값을 저장하는 유효 노드로서 작동한다.
init 함수: 연결리스트 초기화
① 리스트의 Head를 NULL로 선언한다. 이때 인자로 받는 같은 DListType 값이다.
② 리스트의 사이즈를 초기화한다.
쉽게 말해, 연결리스트를 담고 있는 '타입의 초기화'의 과정이다.
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
typedef char element;
typedef struct Listnode {
int data;
struct Listnode* next;
}Listnode;
typedef struct ListType {
struct Listnode* Head;
int size;
}ListType;
void init(ListType* DList) {
DList->Head = NULL;
DList->size = 0;
}insertFirst 함수: 연결리스트의 첫 부분에 노드 추가
① 새로운 노드(new)를 동적 할당한다.
② 인자로 받은 노드 타입의 헤드(Head) 노드를 저장할 임의의 노드 p를 동적할당한다.
③ 새로운 노드(new)에 값을 저장한다.
④ 연결리스트의 첫 부분에 노드를 추가하는 것이므로, new의 next를 Head노드와 연결한다.
⑤ Head노드에 new 노드를 저장한다. → 헤드노드의 위치를 바꾼다.
⑥ 노드의 사이즈를 증가한다.
void insertFirst(ListType* DList, element e) {
Listnode* new = (Listnode*)malloc(sizeof(Listnode));
//새로운 노드 동적할당
Listnode* p = DList->Head;
/*노드 추가 시 기본 알고리즘*/
new->data = e; // 새로운 노드에 값 저장
new->next = p;// 새로운 노드의 next를 H(헤드)를 저장한 p로 연결
if (p == NULL) {DList->Head = new;}//p가 널이면 헤드-테일을 각각 new로 초기화
else {DList->Head = new;}//연결리스트의 헤드를 new로 설정
DList->size++;
}insertLast 함수: 연결리스트의 끝 부분에 노드 추가
① 새로운 노드(new)를 동적 할당한다.
② 인자로 받은 노드 타입의 헤드(Head) 노드를 저장할 임의의 노드 p를 동적할당한다.
③ 임의의 노드 p를 이용해 p의 next가 NULL이 아닐 때까지 순회한다.
④ 순회 후 p가 NULL인 경우, 노드가 없는 경우이므로 헤드노드에 new를 저장한다.
⑤순회 후 p가 NULL이 아닌 경우, p의 next를 new로 지정한다.
⑥ 노드의 사이즈를 증가한다.
void insertLast(ListType* DList, element e) {
Listnode* new = (Listnode*)malloc(sizeof(Listnode));
Listnode* p = DList->Head;
while(p->next != NULL) {
if (p->next == NULL) {
break;
}
p = p->next;
}
new->data = e;
new->next = NULL;
if (p == NULL) DList->Head = new;
else p->next = new;
DList->size++;
}insert함수: 연결리스트의 노드 추가 함수(rank: 노드를 추가할 위치)
insert 함수의 기본 로직은 아래와 같다.
ⓞ 노드를 추가할 순위가 유효하지 않은 경우 오류 문구를 출력하고 함수를 종료한다.
① 새로운 노드(new)를 동적 할당한다.
② 인자로 받은 노드 타입의 헤드(Head)노드를 저장할 임의의 노드 p를 동적할당한다.
③ rank의 값이 1이라면, 노드의 첫 번째의 값을 추가하는 것이므로 insertFirst함수를 실행한다.
④ rank의 값이 (DList->size + 1)이라면, 노드의 끝에 값을 추가하는 것이므로 insertLast함수를 실행한다.
⑤ rank의 값이 ③,④ 조건에 맞지 않는 경우 rank의 위치까지 이동한다.(순회)
⑥ new에 값을 저장한다.
⑦ new의 next를 순회가 끝난 p의 next로 설정한다.
⑧ 노드의 사이즈를 증가한다.
void insert(ListType* DList, element e, int rank) {
if (rank < 1 || rank > DList->size) {
printf("Invalid rank\n");
return ;
}
Listnode* new = (Listnode*)malloc(sizeof(Listnode));
Listnode* p = DList->Head;//임의의 노드 생성
if (rank == 1) {insertFirst(DList, e);}
else if (rank == DList->size + 1) {insertLast(DList, e);}//(맨 마지막 + 1)위치 추가
else {
for (int i = 1; i < rank-1; i++) {p = p->next;}//원하는 위치까지 이동
// printf("inserting...\n");
new->data = e;
new->next = p->next;
p->next = new;
DList->size++;
}
}deleteFirst 함수: 연결리스트의 첫 부분에 노드 삭제
① DList->Head (헤드 노드)가 NULL이면 리턴한다. 즉, 아무것도 수행하지 않는다.
② 인자로 받은 노드 타입의 헤드(Head)노드를 저장할 임의의 노드 p를 동적할당한다.
③ 헤드노드에 p의 next를 저장한다. 이는 헤드 노드가 값을 저장하는 유효 노드이기 때문에 가능하다.
④ 삭제할 노드의 값(output)을 저장한다.
⑤ 삭제할 노드(p)의 메모리를 해제한다.
⑥ 노드의 사이즈를 감소한다.
⑦ output을 반환한다.
element deleteFirst(ListType* DList) {
if (DList->Head == NULL) {
return -1; // 연결리스트가 비어있으면 아무것도 안 함
}
Listnode* p = DList->Head;
element ouput = p->data;
DList->Head = p->next;
free(p); // 삭제된 노드 메모리 해제
DList->size--;
return ouput;
}deleteLast함수: 연결리스트의 끝 부분에 노드 삭제
단일 연결리스트는 이전 노드의 위치를 저장하는 prev 노드가 없으므로, 첫 번째 노드의 삭제가 아닌 경우 뒤 노드와 연결하기 위한 저장 연결리스트 노드가 필요하다. 이를 위해 임의로 prev 노드를 생성한다.
① DList->Head (헤드 노드)가 NULL이면 리턴한다. 즉, 아무것도 수행하지 않는다.
② 인자로 받은 노드 타입의 헤드(Head)노드를 저장할 임의의 노드 p를 동적할당한다.
③ prev 노드를 생성한 후 NULL값을 저장한다.
④ 임의의 노드 p를 이용해 p의 next가 NULL이 아닐 때까지 순회한다. 이때 prev에 초기화되기 전의 p를 저장한다.
⑤ 삭제할 노드의 값(output)을 저장한다.
⑥ prev의 값이 NULL일 때, 즉 리스트에 노드가 하나만 있을 때는 헤드에 NULL을 저장한다.
⑦ prev의 값이 NULL이 아닐 때, prev의 next에 NULL을 저장한다.
⑧ 노드의 사이즈를 감소한다.
⑨ output을 반환한다.
element deleteLast(ListType* DList) {
if (DList->Head == NULL) {
return -1; // 연결리스트가 비어있으면 아무것도 안 함
}
Listnode* p = DList->Head;
Listnode* prev = NULL;
while(p->next != NULL) {
prev = p;
p = p->next;
}element ouput = p->data;
if (prev == NULL) DList->Head = NULL; // 리스트에 노드가 하나만 있을 때
else prev->next = NULL; // 마지막 노드를 삭제하기 위해 이전 노드의 다음 노드를 NULL로 설정
free(p); // 삭제된 노드 메모리 해제
DList->size--;
return ouput;
}delete함수: 연결리스트의 노드 삭제 함수(rank: 노드를 삭제할 위치)
① 노드를 추가할 순위가 유효하지 않은 경우 오류 문구를 출력하고 함수를 종료한다.
② rank의 값이 1이라면, 노드의 첫 번째의 값을 추가하는 것이므로 deleteFirst함수를 실행한다.
③ rank의 값이 (DList->size)이라면, 노드의 끝에 값을 추가하는 것이므로 deleteLast함수를 실행한다.
④ 헤드(Head)노드를 저장할 임의의 노드 p에 헤드노드를 저장한다.
⑤ prev 노드를 생성한 후 NULL값을 저장한다.
⑤ rank의 위치까지 이동한다.(순회)
⑥ 삭제할 노드의 값(output)을 저장한다.
⑦ 삭제할 노드(p)의 메모리를 해제한다.
⑧ 노드의 사이즈를 감소한다.
⑨ output을 반환한다.
element delete(ListType* DList, int rank) {
element ouput ;
if (rank < 1 || rank > DList->size) {
printf("Invalid rank\n");
return -1;
}
if (rank == 1) deleteFirst(DList);
else if (rank == DList->size) deleteLast(DList);
else {
Listnode* p = DList->Head;
Listnode* prev = NULL;
for (int i = 1; i < rank; i++) {
prev = p;
p = p->next;
}ouput = p->data;
prev->next = p->next;
free(p); // 삭제된 노드 메모리 해제
DList->size--;
}
return ouput;
}getNode함수: 연결리스트의 값 확인 함수 rank: 노드를 확인할 위치)
① 노드를 확인할 순위가 유효하지 않은 경우 오류 문구를 출력하고 함수를 종료한다.
② 헤드(Head)노드를 저장할 임의의 노드 p에 헤드노드를 저장한다.
③ rank의 위치까지 이동한다.
④ rank의 위치의 노드의 값을 반환한다.
element getNode(ListType* DList, int rank) {
if (rank < 1 || rank > DList->size) {
printf("Invalid rank\n");
return -1; // 유효하지 않은 순위일 경우 -1 반환
}
Listnode* p = DList->Head;
for (int i = 1; i < rank; i++) {
p = p->next;
}
return p->data;
}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<string.h>
#include<stdlib.h>
#include<time.h>
typedef char element;
typedef struct Listnode {
int data;
struct Listnode* next;
}Listnode;
typedef struct ListType {
struct Listnode* Head;
int size;
}ListType;
void init(ListType* DList) {
DList->Head = NULL;
DList->size = 0;
}
void insertFirst(ListType* DList, element e) {
Listnode* new = (Listnode*)malloc(sizeof(Listnode));
//새로운 노드 동적할당
Listnode* p = DList->Head;
/*노드 추가 시 기본 알고리즘*/
new->data = e; // 새로운 노드에 값 저장
new->next = p;// 새로운 노드의 next를 H(헤드)를 저장한 p로 연결
DList->Head = new;
DList->size++;
}
void insertLast(ListType* DList, element e) {
Listnode* new = (Listnode*)malloc(sizeof(Listnode));
Listnode* p = DList->Head;
while(p->next != NULL) {
if (p->next == NULL) {
break;
}
p = p->next;
}
new->data = e;
new->next = NULL;
if (p == NULL) DList->Head = new;
else p->next = new;
DList->size++;
}
void insert(ListType* DList, element e, int rank) {
if (rank < 1 || rank > DList->size) {
printf("Invalid rank\n");
return ;
}
Listnode* new = (Listnode*)malloc(sizeof(Listnode));
Listnode* p = DList->Head;//임의의 노드 생성
if (rank == 1) {insertFirst(DList, e);}
else if (rank == DList->size + 1) {insertLast(DList, e);}//(맨 마지막 + 1)위치 추가
else {
for (int i = 1; i < rank-1; i++) {p = p->next;}//원하는 위치까지 이동
// printf("inserting...\n");
new->data = e;
new->next = p->next;
p->next = new;
DList->size++;
}
}
element deleteFirst(ListType* DList) {
if (DList->Head == NULL) {
return -1; // 연결리스트가 비어있으면 아무것도 안 함
}
Listnode* p = DList->Head;
element ouput = p->data;
DList->Head = p->next;
free(p); // 삭제된 노드 메모리 해제
DList->size--;
return ouput;
}
element deleteLast(ListType* DList) {
if (DList->Head == NULL) {
return -1; // 연결리스트가 비어있으면 아무것도 안 함
}
Listnode* p = DList->Head;
Listnode* prev = NULL;
while(p->next != NULL) {
prev = p;
p = p->next;
}element ouput = p->data;
if (prev == NULL) DList->Head = NULL; // 리스트에 노드가 하나만 있을 때
else prev->next = NULL; // 마지막 노드를 삭제하기 위해 이전 노드의 다음 노드를 NULL로 설정
free(p); // 삭제된 노드 메모리 해제
DList->size--;
return ouput;
}
element delete(ListType* DList, int rank) {
element ouput ;
if (rank < 1 || rank > DList->size) {
printf("Invalid rank\n");
return -1;
}
if (rank == 1) deleteFirst(DList);
else if (rank == DList->size) deleteLast(DList);
else {
Listnode* p = DList->Head;
Listnode* prev = NULL;
for (int i = 1; i < rank; i++) {
prev = p;
p = p->next;
}ouput = p->data;
prev->next = p->next;
free(p); // 삭제된 노드 메모리 해제
DList->size--;
}
return ouput;
}
element getNode(ListType* DList, int rank) {
if (rank < 1 || rank > DList->size) {
printf("Invalid rank\n");
return -1; // 유효하지 않은 순위일 경우 -1 반환
}
Listnode* p = DList->Head;
for (int i = 1; i < rank; i++) {
p = p->next;
}
return p->data;
}
void print(ListType* DList) {
for (Listnode* p = DList->Head; p != NULL; p = p->next) {
printf("[%c] -> ", p->data);
}printf("\b\b\b\b \n");
}
int main(){
//순환문이용
int n,m,tmp;
ListType DList_A,DList_B;
init(&DList_A);init(&DList_B);
// scanf("%d",&n);
// n = 5;
// srand(time(NULL));
// for(int i=0;i<n;i++){
// // scanf("%d",&tmp);
// tmp = rand() % 99 + 1;
// insert(&DList_A,i+1,tmp);
// }
printf("--------------insertFirst--------------\n");
insertFirst(&DList_A,'A');print(&DList_A);//printf("\n");
insertFirst(&DList_A,'B');print(&DList_A);//printf("\n");
insertFirst(&DList_A,'C');print(&DList_A);//printf("\n");
printf("---------------insertLast---------------\n");
insertLast(&DList_A,'D');print(&DList_A);//printf("\n");
printf("---------------insert [%d]---------------\n",2);
insert(&DList_A,'E',2);print(&DList_A);
printf("---------------insert [%d]---------------\n",4);
insert(&DList_A,'F',4);print(&DList_A);
printf("-------------deleteFirst-----------------\n");
deleteFirst(&DList_A);print(&DList_A);
printf("--------------deleteLast------------------\n");
deleteLast(&DList_A);print(&DList_A);
printf("---------------getNode--------------------\n");
printf("getNode[%d] = [%c]\n",1,getNode(&DList_A,1));
printf("getNode[%d] = [%c]\n",2,getNode(&DList_A,2));
printf("getNode[%d] = [%c]\n",3,getNode(&DList_A,3));
}단일 연결리스트의 ADT 구현 (2): 함수 통합
함수 설명
단일 연결리스트의 순서도는 아래와 같다.
1. 연결리스트 구조체 생성하기
2. 헤드(head) 노드와 엔드(end) 노드를 동적할당으로 생성 후 NULL과 연결
3. Node1이라는 새로운 노드를 생성
4. Node1을 head와 NULL사이에 연결(node1의 꼬리를 head의 꼬리로 연결)
5. Node1의 값을 업데이트
6. 순회용 노드 생성
7. 다음 노드의 방향이 NULL이 아닐 때까지 반복
8. 반복 종료 시 메모리 해제
단일 연결리스트의 함수 : add 함수
add 함수의 기본 로직은 아래와 같다.
① 삽입하고자 하는 위치 바로 앞까지 간다. (i < rank)
② 이때의 노드가 NULL이 아니라면, 이 노드를 임시로 저장한다. 이때의 노드를 curr라고 하자.
③ 새로운 노드를 동적할당하여 생성한다. 이때의 노드를 p라고 하자
④ p에 데이터를 담고, 이 노드의 next를 curr의 next로 저장한다.
⑤ curr의 next를p의 next로 바꾼다.
단일 연결리스트의 함수 : delete 함수
delete 함수의 기본 로직은 아래와 같다.
① 삭제하고자 하는 노드 바로 앞까지 이동한다. (i < rank)
② 다음 노드가 NULL이 아니라면 이 노드를 임시로 저장한다. 이때의 노드를 rear라고 하자.
③ 삭제할 노드는 저장한 노드의 다음 노드이다. 그 노드를 임시로 저장한다. 이때의 노드를 tmp라고 하자
④ tmp의 next를 rear의 next에 저장한다.
⑤ tmp를 삭제한다.
단일 연결리스트의 함수 : print 함수
print 함수의 로직은 순회중 노드의 next값이 NULL이 아닐 때까지 반복하여 리스트에 저장된 값을 출력한다.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
/*연결 리스트를 구현할 구조체*/
typedef struct ListNode{
int data;
struct ListNode* next;//자가 참조 구조체
/*다음 노드의 주소를 저장할 자기참조 구조체포인터*/
}ListNode;
ListNode* add(ListNode *head, int rank, int value){//구조체 함수
/*list의 순위 r에 원소 e를 추가해야함으로 순위r까지 반복한 후 해당 위치에 원소 e를 추가하도록한다.*/
int cnt = 0;
ListNode* check = head->next; //순회용 노드 생성
while(check != NULL){
cnt ++;
check = check->next;
}free(check);
//printf("cnt = %d\n",cnt);
if(cnt > rank) {printf("invalid position");return 0;}
else{
ListNode* curr = head; //순회용 노드 생성
for(int i=0;i<rank;i++)curr= curr->next;
//위 반복문을 통해 이미 순위가 r인 노드까지 이동함.(ㄱ)
ListNode *p=(ListNode *)malloc(sizeof(ListNode));//추가할 노드를 동적할당한다.
p->data = value;
p->next = curr->next;
curr->next = p;
// printf("추가된 노드의 데이터는 %d입니다.\n",p->data);
return head; //다음 노드의 위치를 반환함.
}
}
// delete(list, r) : list의 순위 r에 위치한 원소를 삭제한다 (주교재의 remove와 동일)
ListNode* delete(ListNode *head, int rank){//구조체 함수
ListNode* rear = head; //순회용 노드 생성
for(int i=0;i<rank-1;i++)rear= rear->next;//삭제할 노드의 뒤까지 반복
ListNode* tmp = rear->next; printf("데이터 [%d]를 삭제합니다.\n",tmp->data);
//삭제할 노드는 저장한 노드의 다음 노드이다. 그 노드를 임시로 저장한다.
rear->next = tmp->next; free(tmp);
// (삭제할 노드-1)의 다음 노드는 (삭제할 노드의 + 1)
return head;
}
void print(ListNode *head){
ListNode* prt = head->next; //순회용 노드 생성
while(prt != NULL){
printf("%d ", prt->data);
prt = prt->next;
}free(prt);
printf("\n");
}
int main(){
/*노드를 메모리 동적 할당으로 생성하기*/
ListNode* head = (ListNode*)malloc(sizeof(ListNode)); //헤드 노드 생성
ListNode* end = (ListNode*)malloc(sizeof(ListNode)); //엔드 노드 생성
end = NULL;// end->next = end;
head->next = end;
while(curr != NULL){
printf("%d\n", curr->data);
curr = curr->next;
}
}