C언어 - 연결리스트

연결리스트(linked list)

지금까지는 다량의 데이터를 '배열'에 저장했었다.

배열을 사용하면 쉽고 빠르게 구현이 가능하지만, 크기가 고정되기때문에 크기를 늘이거나 줄이는 동적인 활동을 하지 못하는 단점이 있다.

예를 들어, 만약 a[3]에 데이터를 삽입하려면 a[3]부터 모든 데이터를 뒤로 밀어서 빈 공간을 만들어야한다.

이렇듯, 기존의 데이터들을 이동시켜야한다.

연결 리스트(linked list)는 이런 단점을 극복할 수 있다.

---

연결리스트는 각각의 원소가 포인터를 사용해서 다음 원소의 위치를 가르킨다. 즉, 포인터를 사용해서 자료들을 연결한다.

 

이런식으로 A박스에 있는 원소가 포인터로 B를 가르키고 B에 있는 원소가 포인터로 C를 가르킨다.

그래서 데이터의 삭제와 삽입이 쉽다 데이터를 연결하는 줄만 수정하면 되기 때문이다.

데이터를 추가 할 때도 C가 이어주는 새로운 박스 D를 생성하면 된다.

하지만, 배열보다 구현이 어렵고 오류가 날 가능성이 높다.(처음 배울때 논리가 잘 이해가 안감)

---

연결 리스트의 구조

위에서 봤던 박스를 노드(node)라고 하고, 노드안에는 우리들이 저장하고 싶은 데이터가 들어가는 데이터필드, 다음 노드의 주소가 들어가는 링크필드로 이루어져 있다.

간단한 연결리스트의 구조를 보면 이렇다.

---

자기 참조 구조체(self-referential structure)

struct NODE{
    int num;
    struct NODE *link;
};

위의 코드는 구조체 NODE를 정의하고 있다. 여기서 num은 데이터 필드이고, 자기 구조체 자신을 가르키는 포인터변수 link를 선언했다.

자기 참조 구조체는 포인터를 이용해서 다른 구조체와 연결될 수 있다.

---

자기 참조 구조체를 이용하여 간단한 연결리스트를 만들어보자

typedef struct info{
    int num;
    struct info *link;
} INFO;

구조체를 정의한다. 구조체는 num과 link라는 자기참조 포인터를 갖는다.

아까 말했듯이, num은 데이터필드가 되고, link는 링크 필드가 된다.

 

INFO *p1 = NULL;
INFO *p2 = NULL;

p1 = (INFO *)malloc(sizeof(INFO));
p2 = (INFO *)malloc(sizeof(INFO));

그리고 방금전의 구조체를 가르키는 포인터 p1, p2를 생성한다. p1에 malloc으로 동적메모리 할당을 해주고, p2에도 동적메모리 할당을 해준다. (malloc은 반환을 포인터값으로 해줌)

 

    p1->num = 10;
    p2->num = 20;

    p1->link = p2;
    p2->link = NULL;

p1이 가르키는 구조체의 멤버인 num에 10을 할당, p2가 가르키는 구조체 num에 20을 할당.

그리고 p1가 가르키는 구조체의 link에 p2의 주소를 할당한다.

여기서 p1이 가르키는 구조체의 link는 p2를 가르키게 된다.

 

 

그림으로 보면 이렇다.(연결리스트는 처음 이해할 때 그림으로 이해하는게 훨씬 쉽다.)

 

    printf("p1->num : %d\n", p1->num);
    printf("p2->num : %d\n", p2->num);
    printf("p2->num : %d\n", p1->link->num);

그리고 값을 출력을 해보자. p1->num은 p1을 가르키는 구조체에서 num을 출력하고 10 , p2->num은 p2가 가르키는 구조체에서 num을 출력한다 20 . p1->link->num은 연결리스트의 특징을 볼 수 있는데, p1이 가르키는 구조체의 멤버인 link가 가르키는 구조체의 num의 출력한다. 즉, p1->link->num은 p2->num과 같다! (이해가 어렵지만 천천히 음미하면 이해가 된다..)

 

p1이 가르키고있는 구조체에서 link는 p2를 가르키고 있기 때문이다.

---

전체 코드를 보면

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

typedef struct info{
    int num;
    struct info *link;
} INFO;

int main(void)
{
    INFO *p1 = NULL;
    INFO *p2 = NULL;

    p1 = (INFO *)malloc(sizeof(INFO));
    p2 = (INFO *)malloc(sizeof(INFO));

    p1->num = 10;
    p2->num = 20;

    p1->link = p2;
    p2->link = NULL;

    printf("p1->num : %d\n", p1->num);
    printf("p2->num : %d\n", p2->num);
    printf("p2->num : %d\n", p1->link->num);

    free(p1);
    free(p2);
    return 0;
}

마지막에 free로 메모리를 풀어주면 끝.

여기까지가 연결리스트의 기초이다.