반응형
Linked List의 종류
1. Singly Linked List
2. Doubly Linked List
3. Circular Singly Linked List
4. Circular Doubly Linked List (실무에서 많이 씀)
linked list를 쓸때 키 포인트가 뭐냐?
동적 메모리는 이름이 없다! 그래서 항상 포인터가 잡고 있어야 한다
그래서 내가 가리키고 있는 포인터에서 얘를 움직여도 되는가? 라는 부분을 항상 염두해 두어야 한다
움직일 순 있지만, 항상 첫번째 부분을 가리키고 있어야 한다. 그래야 뒤에 있는 곳도 가리킬 수 있다. (그림은 필기 참고)
자기 참조 구조체
구조체 안에 구조체를 넣을 수 있나? (o)
그게 자바에서 has-a 관계이다
(그림 참고)
지금부터 용도를 확실히 해라! 포인터를 명확하게 해야 한다!
ㆍ Linked List에서 쓰이는 포인터들
1. *head : 첫 번째 노드만 가리키는 포인터
2. *nov : 항상 새로운 노드만 가리키는 포인터
3. *del : 삭제할 노드만 가리키는 포인터
4. *cur : 위 3가지 용도 외에 모든 곳에 쓰는 포인터
#1. head pointer는 첫 번째 노드를 가리킬 때와 첫 번째 노드를 삭제할 때만 움직인다.
#2. nov(novel) pointer는 항상 새로운 노드를 가리킬 때 사용하겠다!
#3. del(delete) pointer는 노드를 삭제할 때만 사용한다. 삭제 전용 포인터를 따로 쓰자!
#4. cur(cursor) pointer는 위 3가지 용도 외에 모든 곳에 쓰면 된다. 일명 잡일 담당 포인터!
이외에는 *head 포인터가 아닌 다른 포인터를 이용하자!
각각의 포인터의 의미에 맞게끔 코딩할 것!
핵심은 원래 의미 외에는 사용하지 마라!
linked list는 삽입 삭제가 용이한 자료구조; 삽입 삭제하는 방법을 잘 알고 있어야 한다!
1. 추가
마지막에 추가할 때는 항상 지금 있는 게 몇개인지 검색해야 한다!
조건식을 잘 써야한다
// 뒷부분부터 연결
new1->next = cur->next;
== new1->next = NULL;
Program 02.01 반복문을 사용하지 않고 Linked List 추가
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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 | #define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> typedef struct card { // self-referential structure char name[10]; int num; struct card *next; // use which points out next node } CARD; void main() { // must be use to its respective purpose CARD *head, *cur, *new1, *del; // all pointers point out NULL head = cur = new1 = del = NULL; if ((head = new1 = (CARD *)calloc(1, sizeof(CARD))) == NULL) { puts("failed to memory allocation!"); exit(-1); } // input the first data printf("Input name, num : "); scanf("%s %d", new1->name, &new1->num); new1->next = NULL; if ((new1 = (CARD *)calloc(1, sizeof(CARD))) == NULL) { puts("failed to memory allocation!"); exit(-1); } // input the second data printf("Input name, num : "); scanf("%s %d", new1->name, &new1->num); new1->next = NULL; // connect (use cursor pointer) cur = head; // grasp last node with cur while (cur->next != NULL) { cur = cur->next; // move to next node } // step 1. connect from rear part new1->next = cur->next; // ㄴ == new1->next = NULL; // step 2. connect front part cur->next = new1; // printouts cur = head; while (cur != NULL) { printf("%s\t%d \n", cur->name, cur->num); cur = cur->next; } } | cs |
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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 | #define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct card { // 자기 참조 구조체 char name[10]; int num; struct card *next; // 다음 노드를 가리키는 용도 } CARD; void main() { int pos; // 각각의 용도에 맞게 포인터를 사용해야 한다 CARD *head, *cur, *new1, *del; // 모든 포인터는 NULL을 가리키도록 습관을 들여라! head = cur = new1 = del = NULL; // 첫번째 노드 추가 if ((head = new1 = cur = (CARD *)calloc(1, sizeof(CARD))) == NULL) { puts("failed to memory allocation!"); exit(-1); } // 첫번째 노드 데이터 입력 printf("Input name, num : "); scanf("%s %d", new1->name, &new1->num); new1->next = NULL; // 두번째 노드 추가 if ((new1 = cur = (CARD *)calloc(1, sizeof(CARD))) == NULL) { puts("failed to memory allocation!"); exit(-1); } // 두번째 노드 데이터 입력 printf("Input name, num : "); scanf("%s %d", new1->name, &new1->num); new1->next = NULL; // 커서 포인터로 연결 cur = head; // 커서 포인터로 마지막 노드 탐색 while (cur->next != NULL) { cur = cur->next; // 다음 노드로 이동 } // 첫번째 노드와 두번째 노드 연결 : 1. 뒷부분부터 new1->next = cur->next; // == new1->next = NULL; // 첫번째 노드와 두번째 노드 연결 : 2. 앞부분 연결 cur->next = new1; // 세번째 노드 추가 if ((new1 = cur = (CARD *)calloc(1, sizeof(CARD))) == NULL) { puts("failed to memory allocation!"); exit(-1); } // 세번째 노드의 데이터 strcpy(new1->name, "CoRock"); new1->num = 20; new1->next = NULL; // 커서 포인터로 연결 cur = head; // 커서 포인터로 마지막 노드 탐색 while (cur->next != NULL) { cur = cur->next; // 다음 노드로 이동 } // 두번째 노드와 세번째 노드 연결 : 1. 뒷부분부터 연결 new1->next = cur->next; // 두번째 노드와 세번째 노드 연결 : 2. 앞부분 연결 cur->next = new1; // 전체 출력 cur = head; while (cur != NULL) { printf("%s\t%d \n", cur->name, cur->num); cur = cur->next; } // 원하는 위치에 노드 삽입 while (1) { printf("몇 번째에 노드를 삽입할 거니? : "); scanf("%d", &pos); if (pos == 1) { // 탐색할 필요가 없다 if ((new1 = cur = (CARD *)calloc(1, sizeof(CARD))) == NULL) { puts("failed to memory allocation!"); exit(-1); } // 노드의 데이터 입력 및 연결 printf("Input name, num : "); scanf("%s %d", new1->name, &new1->num); new1->next = head; head = new1; // 커서 포인터로 마지막 노드 탐색 while (cur->next != NULL) { cur = cur->next; // 다음 노드로 이동 } // 전체 출력 cur = head; while (cur != NULL) { printf("%s\t%d \n", cur->name, cur->num); cur = cur->next; } break; } else if (pos >= 2 && pos <= 4) { int i; // 위치부터 찾자 cur = head; // 커서 포인터가 원하는 위치의 앞 노드를 가리키도록 for (i = 1; i < pos - 1; i++) { cur = cur->next; // 다음 노드로 이동 } if ((new1 = (CARD *)calloc(1, sizeof(CARD))) == NULL) { puts("failed to memory allocation!"); exit(-1); } // 추가한 노드의 데이터 입력 printf("Input name, num : "); scanf("%s %d", new1->name, &new1->num); // 1. 뒤에서부터 연결 new1->next = cur->next; // 2. 앞부분 연결 cur->next = new1; // 탐색 while (cur->next != NULL) { cur = cur->next; // 다음 노드로 이동 } // 전체 출력 cur = head; while (cur != NULL) { printf("%s\t%d\n", cur->name, cur->num); cur = cur->next; } break; } else { puts("잘못된 번호를 입력하였습니다. 다시 입력하세요."); continue; } } } | cs |
반응형