연결리스트(Linked List)

연결리스트란?

데이터와 포인터로 구성된 노드가 연결된 자료구조

연결리스트의 구조

h는 첫번째 노드를 가리키는 포인터로 연결리스트의 이름이라 생각하면 된다. 마지막 노드는 가리키는 대상이 없는데 마지막 노드의 포인터값에는 NULL이 들어간다. 노드안에는 data를 여러 개 넣어도 되고 문자를 넣어도 된다.


노드 추가 과정

1. 노드를 생성한다.
2. 이전 노드의 포인터값을 새 노드의 포인터값에 받아온다.
3. 이전 노드의 포인터값을 새 노드로 변경한다.

주의할 점은 2, 3번의 순서가 바뀌면 새 노드는 다음 노드를 가리킬 수 없어서 연결리스트의 연결이 끊기게 된다.

아래의 예제에서는 마지막에 노드를 추가한다.
마지막 노드의 포인터값이 NULL인 것을 이용하여 반복문을 사용해서 마지막 노드의 위치를 찾을 것이다.
만약 중간에 노드를 추가하고 싶다면 조건문을 변경하면 된다. 첫번째에 추가한다면 반복문은 필요없다.


노드 삭제 과정

1. 연결리스트가 비어있는지 확인한다.
2. 반복문을 사용해 삭제할 노드와 이전노드를 찾는다.
3. 이전 노드의 포인터값을 바꾸고 해당 노드를 삭제한다.

나는 한눈에 들어오기 쉽게 반복문 안에 이전 노드와 삭제할 노드를 넣어서 한번 돌때마다 두개 다 변경했다.
이 방식이 싫으면 조건문을 변경하고 이전 노드의 값만 바꾼 다음 반복문이 종료되면 삭제할 노드를 가리키는 포인터 변수를 만들면 된다. 말을 이상하게 한 것 같은데 아래의 예제를 보면 이해가 갈 것이다.


연결리스트 구현

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
#include<stdio.h>
#include<stdlib.h>
 
typedef struct node{
    int data;
    struct node *next;
}node;
 
void insertNode(node *h, int data){
    node *newNode = (node*)malloc(sizeof(node));
    newNode->data = data;
 
    node *temp = h;
 
    while(temp->next != NULL){
        temp = temp->next;
    }
 
    newNode->next = temp->next;
    temp->next    = newNode;
}
 
void deleteNode(node *h){
    if(h->next == NULL){
        printf("List is Empty!\n");
        return;
    }
 
    node *pre;
    node *temp = h->next;
 
    while(temp->next != NULL){
        pre  = temp;
        temp = temp->next;
    }
 
    pre->next = NULL;
    free(temp);
}
 
void printList(node *h){
    if(h->next == NULL){
        printf("List is Empty!\n");
        return;
    }
 
    node *temp = h->next;
 
    printf("List = [ ");
 
    while(temp != NULL){
        printf("%d ", temp->data);
 
        temp = temp->next;
    }
 
    printf("]\n");
}
 
int main(){
    node *h = (node*)malloc(sizeof(node));
    h->next = NULL;
 
    insertNode(h, 25);
    insertNode(h, 30);
    insertNode(h, 35);
    insertNode(h, 40);
    printList(h);
}
 
cs