[DAY 03] Singly Linked List 2
programming/data-structures

[DAY 03] Singly Linked List 2

Linked List의 종류


1. Single Linked List

2. Double Linked List

3. Single 환형 Linked List

4. Double 환형 Linked List (실무에서 많이 씀)




2. 삭제


삭제는




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
169
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
typedef struct card        // 자기 참조 구조체
{
    char name[10];
    int age;
    struct card *next;    // 다음 노드를 가리키는 용도
} CARD;
 
void main()
{
    CARD *head, *cur, *new1, *del;
    int pos = 0, findPos = 0;
    char findName[10];
    int i;
 
    head = cur = new1 = del = NULL;
 
    // 첫 번째 노드 생성 및 데이터 입력
    if ((head = new1 = (CARD *)calloc(1sizeof(CARD))) == NULL) {
        puts("failed to memory allocation!");
        exit(-1);
    }
    printf("Input name, age : ");
    scanf("%s %d", new1->name, &new1->age);
    new1->next = NULL;
 
    // 두 번째 노드 생성 및 데이터 입력
    if ((new1 = (CARD *)calloc(1sizeof(CARD))) == NULL) {
        puts("failed to memory allocation!");
        exit(-1);
    }
    printf("Input name, age : ");
    scanf("%s %d", new1->name, &new1->age);
    new1->next = NULL;
 
    // 첫 번째 노드와 두 번째 노드를 연결하기 위해
    cur = head;
 
    // cursor pointer로 마지막 노드를 잡는다.
    while (cur->next != NULL) {
        cur = cur->next;    // 다음 노드를 이동
    }
 
    new1->next = cur->next;        // step 1. 뒷부분부터 연결 
    cur->next = new1;            // step 2. 앞부분 연결
    
    if ((new1 = (CARD *)calloc(1sizeof(CARD))) == NULL) {
        puts("failed to memory allocation!");
        exit(-1);
    }
    printf("Input name, age : ");
    scanf("%s %d", new1->name, &new1->age);
    new1->next = NULL;
 
    // Search
    cur = head;
 
    while (cur->next != NULL) {
        cur = cur->next;    // 다음 노드를 이동 
    }
 
    new1->next = cur->next;
    cur->next = new1;
 
    // 전체 출력
    cur = head;
 
    while (cur != NULL)    {
        printf("%s\t%d \n", cur->name, cur->age);
        cur = cur->next;
 
        pos++;
    }
 
    // 원하는 위치 입력
    while (findPos < || (pos + 1< findPos) {
        printf("(1 ~ %d)의 값을 입력하세요 : ", pos + 1);
        scanf("%d"&findPos);
    }
 
    // 노드 생성
    if ((new1 = (CARD *)calloc(1sizeof(CARD))) == NULL) {
        puts("failed to memory allocation!");
        exit(-1);
    }
    printf("Input name, age : ");
    scanf("%s %d", new1->name, &new1->age);
    new1->next = NULL;
 
    // 삽입 전 노드 검색
    cur = head;
 
    for (i = 0; i < findPos - 2; i++) {
        cur = cur->next;
    }
 
/*
    while (pos + 1 > 2) {
        cur = cur->next;
        pos--;
    }
*/
 
    // 노드 삽입
    if (findPos == 1) {
        new1->next = head;
        head = new1;
    } else {
        new1->next = cur->next;
        cur->next = new1;
    }
 
    // 전체 출력
    cur = head;
 
    while (cur != NULL) {
        printf("%s\t%d \n", cur->name, cur->age);
        cur = cur->next;
 
        pos++;
    }
 
    // 삭제하고자 하는 이름 입력
    printf("삭제하고 싶은 이름을 입력하세요 : ");
    scanf("%s", findName);
    
    cur = head;
 
    // 삭제하고자 하는 노드가 첫 번째일 경우
    if (strcmp(findName, cur->name) == 0) {
        del = cur;
        head = head->next;
        del->next = NULL;
        free(del);
        puts("삭제가 완료되었습니다!");
    }
    else {
        // 탐색
        while (strcmp(findName, cur->next->name)) {
            cur = cur->next;
 
            // 탐색 실패
            if (cur->next == NULL) {
                puts("찾고자 하는 이름이 없습니다!");
                exit(-1);
            }
        }
 
        del = cur->next;
        cur->next = del->next;
        free(del);
        puts("삭제가 완료되었습니다!");
    }
    
    
    // 전체 출력
    cur = head;
 
    while (cur != NULL) {
        printf("%s\t%d \n", cur->name, cur->age);
        cur = cur->next;
 
        pos++;
    }
}
cs





헤드 포인터가 움직이기 때문에 case를 나눈 것이다.

더미 노드를 만들게 되면 그런 경우가 없다


삭제 전 노드를 찾아서 (알고리즘)



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
169
170
171
172
173
174
175
176
177
178
179
180
181
182
#include <stdio.h>
#include <stdlib.h> 
typedef struct Node
{
    int          data;
    struct Node* next;
}Node;
 
int Insert(struct Node*cur, int position);
int Delete(struct Node*cur, int position);
int SetData(struct Node*cur, int position, int data);
int GetData(struct Node*cur, int position, int* data);
void Printouts(Node *cur);
 
#define ASSERT(exp) if(!(exp)) { puts("Err\n"); }
 
void main(void)
{
    Node* root = (Node*)malloc(sizeof(Node));
    root->next = NULL;
 
    int r, n;
    int i;
 
    // 0번위치에 10개 삽입
    for (i = 0; i < 10; i++) {
        r = Insert(root, 0); ASSERT(r);
        r = SetData(root, 0, i + 1); ASSERT(r);
    }
 
    // 삽입확인
    for (i = 0; i < 10; i++) {
        r = GetData(root, i, &n); ASSERT(r);
        ASSERT(n == 10 - i);
    }
    
    Printouts(root);
 
    //모두삭제
    for (i = 0; i < 10; i++) {
        r = Delete(root, 0); ASSERT(r);
    }
 
    Printouts(root);
 
    //마지막위치에 10개삽입
    for (i = 0; i < 10; i++) {
        r = Insert(root, i); ASSERT(r);
        r = SetData(root, i, i + 1); ASSERT(r);
    }
    
    Printouts(root);
 
    //짝수번째모두삭제
    for (int i = 10 - 1; i >= 0; i -= 2) {
        r = Delete(root, i); ASSERT(r);
    }
 
    Printouts(root);
    
    //짝수번째다시삽입
    for (int i = 1; i < 10; i += 2) {
        r = Insert(root, i); ASSERT(r);
        r = SetData(root, i, i + 1); ASSERT(r);
    }
 
    Printouts(root);
 
 
    //복원확인
    for (int i = 0; i < 10; i++) {
        r = GetData(root, i, &n); ASSERT(r);
        ASSERT(n == i + 1);
    }
    Printouts(root);
    //에러확인(예외처리가 제대로 되었는 지 확인)
    for (int i = 10; i < 20; i++) {
        r = GetData(root, i, &n); ASSERT(!r);
    }
    Printouts(root);
 
    //역순으로삭제
    for (int i = 10 - 1; i >= 0; i--) {
        r = Delete(root, i); ASSERT(r);
    }
    Printouts(root);
 
    ASSERT(root->next == NULL);
    delete root;
    root = NULL; //좋은습관
    
}
 
int Insert(Node *cur, int position)
{
    Node *new1;
    int i;
 
    new1 = NULL;
 
    // 0번 위치에 삽입
    new1 = (Node *)malloc(sizeof(Node));
    new1->next = NULL;
 
    // 현재 몇 개의 노드가 있는지 탐색
    for (i = 0; i < position; i++) {
        if (cur->next == NULL)
            return 0;
 
        cur = cur->next;
    }
 
    new1->next = cur->next;        // step 1. 뒷부분부터 연결 
    cur->next = new1;            // step 2. 앞부분 연결
 
    return 1;
}
 
int Delete(Node*cur, int position)
{
    Node *del;
    int i;
 
    // 현재 몇 개의 노드가 있는지 탐색
    for (i = 0; i < position; i++) {
        if (cur->next == NULL)
            return 0;
 
        cur = cur->next;
    }
 
    del = cur->next;
    cur->next = del->next;
    del->next = NULL;
    free(del);
 
    return 1;
}
 
int SetData(struct Node *cur, int position, int data)
{
    int i;
 
    for (i = 0; i < position; i++) {
        if (cur->next == NULL)
            return 0;
 
        cur = cur->next;
    }
 
    cur->next->data = data;
 
    return 1;
}
 
int GetData(Node *cur, int position, int *data)
{
    do {
        if (cur->next == NULL || cur == NULL)    // 실패
            return 0;
        else
            cur = cur->next;    // 다음으로
    } while (position--);
 
    // 루프를 다 돌고 나면 position = -1 이 되어 있고,
    // cur 목표 node가 되어 있다.
    *data = cur->data;
 
    return 1;
}
 
void Printouts(Node *cur)
{
    puts("DATA\t");
    
    while (cur->next != NULL) {
        printf("%d\t", cur->next->data);
        cur = cur->next;
    }
 
    puts("");
}
cs

사실 이거 day 04 에 한거임