[c언어] 링크드 리스트(Linked list)의 구현 2

공부/- 링크드_리스트 2016. 7. 5. 11:15

링크드 리스트 자료구조에서 구현해야할 부분은 자료의 삽입, 삭제, 프린트입니다.

지난번에는 자료의 입력과 프린트만 구현했었는데, 이번엔

자료를 지우기, 자료를 특정 위치에 넣기, 자료의 순서를 반대로 하기 함수를 추가하도록 하는

코드를 올려봅니다.


그리고... 지난번에 소개한 글처럼 head node를 global값으로 사용한 방식이므로, 

아래 링크 : 링크드 리스트의 3가지 표현 방법 을 보시면, global값에서 지역 변수 등으로 사용하는 방법이 소개되니 참고하세요.

http://hamji.tistory.com/130


Null 포인터에 접근하지 않도록 하는 오류 방지 코드가 없이 기능만 구현하였기에, 참고 바랍니다.

안정성 있는 코드가 되려면, 오류 방지도 생각을 해야겠지요.


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
#include <stdio.h>
#include <stdlib.h>
 
typedef struct _Node {
    int data;
    struct _Node *next;
}Node;
 
Node *head;
 
void insert_node(int data, int n);
void delete_node(int n);
void insert_front(int data);
void insert_rear(int data);
void print_node(void);
void reverse_node(void);
 
void insert_node(int data, int n) {
    Node *node = malloc(sizeof(Node));
    node->data = data;
    node->next = NULL;
    
    if (n == 1) { // 맨앞에 넣기
        node->next = head;
        head = node;
        return;
    }
    Node *cur = head;
    
    for (int i = 0; i < n - 2; i++) {
        cur = cur->next;
    }
    node->next = cur->next;
    cur->next = node;
    return;
}
// 특정 위치에 값을 넣기 
void delete_node(int n){
    Node * cur = head;
 
    if (n == 1) {
        head = cur->next;
        free(cur);
        return;
    }
 
    for (int i = 0; i < n - 2; i++) {
        cur = cur->next;    
    }
    Node *temp = cur->next; 
    cur->next = cur->next->next;
    free(temp);
}
 // 맨 앞에 자료를 넣기
void insert_front(int data) {
    int n = 1;
    insert_node(data, n);
}
 // 맨 뒤에 자료를 넣기
void insert_rear(int data) {
    Node *node = malloc(sizeof(Node));
    node->next = NULL;
    node->data = data;
 
    Node *cur = head;
    while (cur->next != NULL) {
        cur = cur->next;
    }
    cur->next = node;
}
 
void print_node(void) {
    Node*cur = head;
 
    for (int i = 0; cur != NULL; i++) {
        printf("[%2d]->", cur->data);
        cur = cur->next;
    }
    printf("\n");
}
 // 자료의 순서를 반대로 하기
void reverse_node(void) {
    Node *current, *prev, *next;
    current = head;
    prev = NULL;
    
    while (current != NULL) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    head = prev;
}
 
void main(void) {
 
    insert_node(1, 1);
    insert_node(2, 2);
    insert_node(3, 3);
    insert_node(4, 4);
    print_node();
 
    insert_node(5, 3);
    insert_node(6, 2);
    insert_node(7, 1);
    print_node();
    
    insert_rear(11);
    insert_rear(12);
    insert_rear(13);
    insert_rear(14);
    print_node();
 
    delete_node(1);
    delete_node(3);
    delete_node(5);
    print_node();
 
    reverse_node();
    print_node();
}
 
cs


저작자표시 비영리 변경금지
Posted by 고무함지
,

[C 언어] 링크드 리스트 Node삽입 (Linked list node insert at nth node)

공부/- 링크드_리스트 2016. 6. 1. 09:31

이번에는 단일 링크드 리스트(Single Linked List)에서... 특정 위치에 Node를 삽입하여 

저장하는 코드입니다.


head -> 1_번node -> 2_번Node -> 3_번Node -> NULL(자료의 끝)


위와 같이 Node들이 연결되어 있다면,


2번에 새로운 new_node를 삽입하는 함수를 만들었습니다.


void InsertNode(int data, int n);

data는 넣을 자료값, n은 몇번째 node에 넣을지 알려줍니다.

주의 사항은, Node를 1번부터 시작한다고 약속한 점이고,

추가로... 신규 new_node를 2번에 넣는다면, 기존 2번Node는 뒤로 밀리고,

새로운 new_node가 2번Node가 되는 형태로 작성하였으니...


아래의 for(i=0 ; i<n-2 ; i++) 내용에서 n-2로 위치를 지정한 것을 참고하세요.


또한 원하는 node로 이동하는 것이나, Node를 모두 탐색하는 것은

둘 다 현재_node = 현재_node->next; 의 방식을 사용하는 점이 동일합니다.



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
// insert a node at nth position
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
 
typedef struct Node {
    int data;
    struct Node * next;
}Node_T;
 
Node_T * head;
 
void InsertNode(int data, int n);
void PrintNodes(void);
 
// n should be from 1... (not 0)
// head -> 1_node -> 2_node -> 3_node ->...
// if Node is inserted 2 node...
// head -> 1_node -> new_node -> 2_node -> 3_node ->
void InsertNode(int data, int n)
{
    int i;
    Node_T * new_node = (Node_T*)malloc(sizeof(Node_T));
    new_node->data = data;
    new_node->next = NULL;
    if (n == 1)
    {
        new_node->next = head;
        head = new_node;
        return;
    }
 
    // travel from head to 'n'th node
    Node_T * temp2 = head;
    // stop before 'n'th node.
    // and insert node start 1. so... n-2
    for (i = 0; i < n-2; i++) 
    {
        temp2 = temp2->next;
    }
    new_node->next = temp2->next;
    temp2->next = new_node;
 
}
 
void PrintNodes(void)
{
    // travel from head to last node
    Node_T * temp = head;
    
    while (temp != NULL)
    {
        printf("%d, ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}
 
void main(void)
{
    head = NULL;
 
    InsertNode(6, 1);
    InsertNode(8, 2);
    InsertNode(2, 1);
    InsertNode(4, 2);
    InsertNode(1, 3);
    PrintNodes();
    printf("Good bye");
}
 
cs




이 코드에서 추가로 n번째 자료를 지우는 부분도 추가합니다.


지우는 함수도 Insert 함수와 유사합니다.



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
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
 
typedef struct Node {
    int data;
    struct Node * next;
}Node_T;
 
Node_T * head;
 
void InsertNode(int data, int n);
void DeleteNode(int n);
void PrintNodes(void);
 
// n should be from 1... (not 0)
// head -> 1_node -> 2_node -> 3_node ->...
// if Node is inserted 2 node...
// head -> 1_node -> new_node -> 2_node -> 3_node ->
void InsertNode(int data, int n)
{
    int i;
    Node_T * new_node = (Node_T*)malloc(sizeof(Node_T));
    new_node->data = data;
    new_node->next = NULL;
    if (n == 1)
    {
        new_node->next = head;
        head = new_node;
        return;
    }
 
    // travel from head to 'n'th node
    Node_T * temp2 = head;
    // stop before 'n'th node.
    // and insert node start 1. so... n-2
    for (i = 0; i < n-2; i++) 
    {
        temp2 = temp2->next;
    }
    new_node->next = temp2->next;
    temp2->next = new_node;
 
}
 
void DeleteNode(int n)
{
    int i;
    Node_T *temp1 = head;
    if (n == 1)
    {
        head = temp1->next;
        free(temp1);
        return;
    }
    
    for (i = 0; i < n - 2; i++)
        temp1 = temp1->next;
        
    Node_T * del_node = temp1->next;
    temp1->next = del_node->next;
    free(del_node);
    
//    delete_node = NULL;  
    // 주의 delete_node가 가르키는 malloc된 공간을 free해야하며
    // delete_node 포인터 자체는... NULL로 하면 안된다.
    
}
 
void PrintNodes(void)
{
    // travel from head to last node
    Node_T * temp = head;
    
    while (temp != NULL)
    {
        printf("%d, ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}
 
void main(void)
{
    head = NULL;
 
    InsertNode(6, 1);
    InsertNode(8, 2);
    InsertNode(2, 1);
    InsertNode(4, 2);
    InsertNode(1, 3);
    PrintNodes();
    DeleteNode(1);
    DeleteNode(2);
    PrintNodes();
    printf("Good bye");
}
 
cs


저작자표시 비영리 변경금지
Posted by 고무함지
,

[c 언어] 링크드 리스트의 3가지 표현법(Linked List)

공부/- 링크드_리스트 2016. 5. 31. 18:34



C언어를 배우면서... 가장 어려운 것이 포인터이고...


그리고, 이 포인터를 쓰는... 링크드 리스트(Linked List)도 역시나 어렵습니다.


저도 공부하면서... 가장 실수를 많이 한 것이 링크드 리스트인데...




공부해보니 특히나... head 노드 변수를 어느 위치에서 선언하느냐에 따라 


구현 방식의 차이가 있더군요.


이러한 방식은 아래 3가지로 구분할 수 있습니다.




1. 전역 변수로 head를 선언한다.


2. main의 로컬 변수로 head를 선언, 

  링크드 리스트 생성 함수에서, return형으로 Node의 Point를 사용하는 경우


3. main의 로컬 변수로 head를 선언, 

  링크드 리스트 생성 함수에서, return형 없이, Head Node의 주소를 입력 받는 방법



그럼 예제로 설명드리겠습니다. 이 예제는 single linked list로 구현했고, Insert Node를 하면

가장 앞에 새로운 값이 저장되도록 작성되어 있습니다.



< 사진 출처 = https://wiki.cs.auckland.ac.nz/compsci105ss/index.php/Linked_Lists >



1. 전역 변수로 head를 선언한다.


먼저, 아래 Node_T * head; 를 보면... main함수 외부에 전역 변수로 선언되어 있습니다.

그러므로, 이 코드에 있는 어떠한 함수에서도 바로 head에 접근이 가능합니다.


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
#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <stdlib.h>
// linked list 
// case 1 : use global variable for Head
 
typedef struct Node {
    int data;
    struct Node * next;
}Node_T;
 
Node_T * head;
 
void InsertNodeAtHead(int value    );
void PrintNode(void);
 
void InsertNodeAtHead(int value    )
{
    Node_T * temp = (Node_T*)malloc(sizeof(Node_T));
    temp->data = value;
    temp->next = NULL;
 
    if (head != NULL)
        temp->next = head;
    
    head = temp;
}
 
void PrintNode(void)
{
    Node_T * temp = head;
    printf("List :");
    while (temp != NULL)
    {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}
 
int main(void)
{
    int n, x, i;
    head = NULL;
    printf("How many numbers?");
    scanf("%d", &n);
    for (i = 0; i < n; i++)
    {
        printf("enter number:");
        scanf("%d", &x);
        InsertNodeAtHead(x);
    }
    PrintNode();
    printf("Good Bye!");
 
}
 
cs





2. main의 로컬 변수로 head를 선언, 

  링크드 리스트 생성 함수에서, return형으로 Node의 Point를 사용하는 경우



두번째로는... Node_T * head가 main함수 안쪽으로 가서

main함수의 지역변수로 사용되었습니다.


그러므로 다른 함수에서 head를 받기 위해 parameter로 전달을 해야합니다.

그리고 다시 return으로 head를 받아와야 합니다.


Node_T * InsertNodeAtHead(Node_T * head, int value)


head = InsertNodeAtHead(head, x);



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
#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <stdlib.h>
// linked list 
// case 2 : use local variable for Head
 
typedef struct Node {
    int data;
    struct Node * next;
}Node_T;
 
Node_T * InsertNodeAtHead(Node_T * head, int value);
void PrintNode(Node_T *node);
 
Node_T * InsertNodeAtHead(Node_T * head, int value)
{
    Node_T * temp = (Node_T*)malloc(sizeof(Node_T));
    temp->data = value;
    temp->next = NULL;
 
    if (head != NULL)
        temp->next = head;
 
    head = temp;
    return head;
}
 
void PrintNode(Node_T * node)
{
    Node_T * temp = node;
 
    while (temp != NULL)
    {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}
 
int main(void)
{
    int n, x, i;
 
    Node_T * head;  // Head node is local variable
 
    head = NULL;
    printf("How many numbers?");
    scanf("%d", &n);
    for (i = 0; i < n; i++)
    {
        printf("enter number:");
        scanf("%d", &x);
        head = InsertNodeAtHead(head, x);
    }
    PrintNode(head);
    printf("Good Bye!");
 
}
cs


3. main의 로컬 변수로 head를 선언, 

  링크드 리스트 생성 함수에서, return형 없이, Head Node의 주소를 입력 받는 방법


마지막으로... 두번째에서 확인한 파라미터로 head를 전달하고, return으로 head를 다시

받는 형태를 좀더 간략히 하기 위해, 파라미터로 전달시 head의 주소로 전달하여

InsertNodeAtHead()함수에서 바로 head를 접근할 수 있도록 합니다.


void InsertNodeAtHead(Node_T ** head, int value);


// 포인터의 포인터이므로, &head로 주소 연산자를 하나 붙여줍니다.

InsertNodeAtHead(&head, x);



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
#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <stdlib.h>
// linked list 
// case 3 : use local variable for Head, 
// and don't use parameter for Insert
 
typedef struct Node {
    int data;
    struct Node * next;
}Node_T;
 
void InsertNodeAtHead(Node_T ** head, int value);
void PrintNode(Node_T *node);
 
void InsertNodeAtHead(Node_T ** head, int value)
{
    Node_T * temp = (Node_T*)malloc(sizeof(Node_T));
    temp->data = value;
    temp->next = NULL;
 
    if (head != NULL)
        temp->next = *head;
 
    *head = temp;
}
 
void PrintNode(Node_T * node)
{
    Node_T * temp = node;
 
    while (temp != NULL)
    {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}
 
int main(void)
{
    int n, x, i;
 
    Node_T * head;// Head node is local variable
 
    head = NULL;
    printf("How many numbers?");
    scanf("%d", &n);
    for (i = 0; i < n; i++)
    {
        printf("enter number:");
        scanf("%d", &x);
        InsertNodeAtHead(&head, x);
    }
    PrintNode(head);
    printf("Good Bye!");
}
 
cs



코드 참고 : <mycodeschool : https://www.youtube.com/channel/UClEEsT7DkdVO_fkrBw0OTrA >



저작자표시 비영리 변경금지
Posted by 고무함지
,

티스토리툴바