C언어로 연결리스트(Linked List) 구현하기

연결 리스트

저번 시간에 구현했던 그냥 '리스트'와는 달리,

연결 리스트는 동적으로 크기가 변할 수 있고, 삭제나 삽입 시에 데이터를 이동할 필요가 없다.

 

why?

이것이 연결리스트의 기본 구조이다.

데이터가 담긴 상자를 노드(node)라고 부른다.

노드와 노드를 연결하는 선을 포인터(pointer)로 구현한다.

 

연결 리스트에서는 노드를 연결시켜주는 줄만 바꾸면, 삽입 / 삭제가 간편하다.

만약 b와 c사이에 새로운 데이터를 삽입한다고 가정한다면,

그림과 같이 b가 n을 가리키도록, 그리고 n이 c를 가리키도록 줄을 수정해주면 된다.

 

만약 c를 삭제한다고 가정한다면, 

이렇게 줄을 연결하면 된다.

---

연결 리스트의 구조

우리는 상자를 node라고 불렀다.

node는 2가지 영역으로 나뉘는데,

하나는 데이터가 담기는 데이터 필드(data field),

또 다른 하나는 다음 노드의 주소가 담긴 링크 필드(link field)이다.

링크필드를 이용해서 다음 노드로 이동할 수 있다.

 

연결 리스트를 사용하려면, 가장 첫번째의 노드를 알아야

사용가능하다.

첫번째의 노드를 가르키는 포인터를 '헤드 포인터'(head pointer)라고 한다.

 

그리고 마지막 노드의 링크 필드는 NULL로 설정되는데,

연결 리스트의 마지막이다. 라는 것을 의미한다.

 

각 노드들은 필요할 때마다 malloc함수를 사용하여 생성한다.

---

연결 리스트의 종류

연결 리스트는 3가지 종류가 있다.

1. 단순 연결 리스트

2. 원형 연결 리스트

3. 이중 연결 리스트

 

지금은 일단 단순 연결 리스트만 알아보는걸로 하자.

---

단순 연결 리스트

첫 노드를 가리키는 head pointer 그리고 마지막 노드의 링크 필드 값은 NULL이 된다.

---

단순 연결 리스트의 구현

단순 연결 리스트의 구현을 하기 위해선,

3가지 질문이 있다.

 

1. 노드는 어떻게 정의? - 자기 참조 구조체

2. 노드는 어떻게 생성? - malloc

3. 노드는 어떻게 삭제? - free

 

노드의 정의

노드는 자기 참조 구조체를 이용한다.

자기 참조 구조체란, 자기 자신을 가르키는 포인터를 포함하는 구조체이다.

#include <stdio.h>
#include <stdlib.h>

typedef int element;

typedef struct Node{
    element data;
    struct Node *link; //자기 참조 구조체
} Node;

노드를 정의하였다.

data에는 데이터가 들어간다.

link는 구조체 Node를 가르키는(자기 자신) 포인터로 정의된다.

---

공백 리스트 생성

이제 텅 비어있는 아무것도 없는 리스트를 생성해보자.

Node *head = NULL;

 Node구조체를 가르킬, 헤드 포인터를 선언했다.

가르킬 노드가 아직 없기때문에, 값이 NULL이다.

---

노드의 생성

head = (Node *)malloc(sizeof(Node));

구조체 Node의 크기만큼, Node형으로 동적 할당을 해준다.

malloc함수는 '주소값'을 반환한다.

그러면 head포인터는 노드를 가르키게 된다.(첫번째 노드)

 

현재 모습은 이렇다.

노드는 생성되었고, 헤드포인터가 첫 노드를 가리키지만,

노드안에 데이터는 없음. 인정?ㅋ

 

여기서 이제 노드안에 데이터를 넣어보자

head->data = 10;
head->link = NULL;

넘모 쉽다.

 

이해가능?

---

노드의 연결

같은 방식으로 노드를 하나 더 생성하고,

노드끼리 연결 해보자

Node *p = NULL;
p = (Node *)malloc(sizeof(Node));
p->data = 20;
p->link = NULL;

노드 생성 후, 데이터까지 넣었다.

 

이런 모습인데, 이젠 이 두 노드를 포인터를 이용해서 연결해야 한다.

 

head->link = p;

이렇게 하면, head가 가리키는 link가 포인터 p(주소)를 가리키게 된다.

 

최종적으로 이런 간단한 연결리스트가 된다.

노드를 더 늘리고싶다면 이 과정을 반복하면 된다!

---

단순 연결 리스트의 연산을 구현해보자

연결 리스트를 리스트답게 사용하려면 5가지의 기능이 필요하다.

• insert_first : 리스트의 시작 부분에 삽입
• insert : 리스트 중간에 삽입
• delete_first : 리스트의 시작 부분 삭제
• delete : 리스트의 중간 부분 삭제
• print_list : 리스트 출력

---

리스트의 시작 부분에 삽입(insert_first)

Node *insert_first(Node *head, element value)
{
    Node *p = (Node *)malloc(sizeof(Node)); //노드 하나 생성
    p->data = value;
    p->link = head;
    head = p;
    
    return head;
}

추가할 노드를 하나 생성한다.

생성한 노드에 데이터를 넣고.

생성한 노드의 링크를 원래 head포인터가 가리키던 노드를 가리키게 한다.

head포인터가 처음 노드를 가리켰으니, head포인터가 가리키는 노드를 생성한 노드로 바꾼다.

---

리스트의 중간에 삽입(insert)

//prev뒤에 새로운 노드를 삽입한다.
Node *insert(Node *head, Node *prev, element value)
{
    Node *p = (Node *)malloc(sizeof(Node));
    p->data = value;
    p->link = prev->link;
    prev->link = p;

    return head;
}

추가할 노드를 하나 생성.

생성한 노드에 데이터 입력.

생성한 노드의 링크가 이전 노드가 가리키던 노드를 가리키도록.

그리고 이전 노드가 새로 삽입할 노드를 가르키도록 한다.

---

리스트의 시작 부분 삭제(delete_first)

Node *delete_first(Node *head)
{
    Node *removed = NULL;
    if(head == NULL)
        return NULL;
    removed = head;
    head = removed->link;
    free(removed);
    
    return head;
}

head가 NULL을 가리킨다면, 텅 빈 리스트.

원래 head포인터가 가리키던 노드(맨 처음 노드)를 removed포인터(삭제될 노드)가 가리키게 한다.

그리고 head포인터가 removed포인터의 링크를 가리키게 하면 된다.

그리고 free(removed)로 할당 해제해주면, 삭제 끝!

좀 어렵긴 한데, 그림 그려서 해보면 이해쉬움.

---

리스트의 중간 부분 삭제(delete)

//prev가 가리키는 노드 다음 노드를 삭제한다.
Node *delete(Node *head, Node *prev)
{
    Node *removed;
    removed = prev->link;
    prev->link = removed->link;
    free(removed);
    
    return head;
}

prev가 가리키던 노드의 링크를 removed가 가리키게 하고,

prev가 가리키던 링크는 removed의 링크를 가리킨다.

그리고 free(removed)로 해제.

 

글로만 보니, 어렵게 느껴지지?

그림으로 ㄱㄱ

이렇게.

---

출력 함수(print_list)

void print_list(Node *head)
{
        for(Node *p = head; p != NULL; p = p->link){
            printf("%d->", p->data);
        }
        printf("NULL\n");
}

p가 NULL을 가리킬 때 까지, 데이터를 출력한다.

---

전체 코드 / 확인

#include <stdio.h>
#include <stdlib.h>

typedef int element;
typedef struct Node {
    element data;
    struct Node *link;
} Node;

Node *insert_first(Node *head, element value)
{
    Node *p = (Node *)malloc(sizeof(Node)); //노드 하나 생성
    p->data = value;
    p->link = head;
    head = p;

    return head;
}

//prev뒤에 새로운 노드를 삽입한다.
Node *insert(Node *head, Node *prev, element value)
{
    Node *p = (Node *)malloc(sizeof(Node));
    p->data = value;
    p->link = prev->link;
    prev->link = p;

    return head;
}

Node *delete_first(Node *head)
{
    Node *removed = NULL;
    if(head == NULL)
        return NULL;
    removed = head;
    head = removed->link;
    free(removed);

    return head;
}

//prev가 가리키는 노드 다음 노드를 삭제한다.
Node *delete(Node *head, Node *prev)
{
    Node *removed;
    removed = prev->link;
    prev->link = removed->link;
    free(removed);

    return head;
}

void print_list(Node *head)
{
        for(Node *p = head; p != NULL; p = p->link){
            printf("%d->", p->data);
        }
        printf("NULL\n");
}

int main(void)
{
    Node *head = NULL;

    head = insert_first(head, 1);
    print_list(head);
    head = insert_first(head, 2);
    print_list(head);
    head = insert_first(head, 3);
    print_list(head);

    head = insert(head, head->link, 4); //3번째에 삽입
    print_list(head);

    head = delete_first(head);
    print_list(head);

    return 0;
}