연결 리스트(Linked List)

Mkim4·2023년 7월 11일

Linked List(연결 리스트)란?

연속된 노드(Node)의 연결체, 즉 체인처럼 연결된 데이터 상자들

연결리스트에서 Node 란 무엇인가?

Node란 연결리스트에서 사용되는 하나의 데이터 덩어리이며,
데이터 & 링크 이 2가지의 필드를 담고있는 구조이다.

노드(Node)의 구조는?

1. 데이터(data): 노드가 담고 있는 데이터/값(문자열,숫자,오브젝트 등)
2. next: 링크/포인터 역할, 다음 노드의 주소를 저장
*양방향 연결 리스트인 경우, prev 포인터(이전 노드의 주소) 추가

연결리스트(Linked List)의 구조는?

연결리스트의 첫번째 시작지점에 있는 노드를 head,
마지막에 있는 노드를 tail이라고 부름

배열 vs 연결리스트

배열

배열의 인덱스를 활용한 원소 탐색을 효율적으로 빠르게 실행할 수 있다.
1. random access 가능 ex) 배열의 n번째 원소 방문시 O(1)(상수) 시간으로 가능, arr(3)
2. 원소 삽입 & 삭제 일반적으로 O(n) 시간 소요

연결 리스트

이어진 메모리 공간이 아닌, 불특정한 공간에 노드가 존재하기 때문에 포인터(주소)를 참조하는 필드를 통해서 연결을 시켜줘야함
노드는 O(n)만큼의 선형시간 소요
1. random access 불가능 ex) 리스트의 n번째 노드 방문시 O(n) 시간 소요, head 노드부터 n번째 노드까지 순회
1-1 ramdom access(임의접근)을 할 수 있으며 이진 탐색을 할 수 있으나 불가능하므로 이진 탐색도 하지 못함.
2. 배열보다 빨라질 수 있는 노드 삽입 & 삭제
3. 배열처럼 숫자를 추가하기 위해서 크기를 조절하고 기존의 값을 모두 옮기지 않아도 된다.

연결리스트의 종류는?

Singly Linked List(단일 연결 리스트)
Doubly Linked List(이중 연결 리스트)

다음노드를 가르키는 포인터 뿐만 아니라, 이전 노드를 가르키는 포인터도 가지고 있다. 앞,뒤로 탐색하는 것이 빠르다는 장점이 있지만 노드마다 2개의 포인터를 관리해줘야하기 때문에 데이터의 구조와 흐름이 오히려 복잡해질 수도 있다.
Circular Linked List(원형 연결 리스트)

tail 노드의 포인터가 head 노드를 가르키게 됨.

연결리스트 구현방법?

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

//연결 리스트의 기본 단위가 되는 node 구조체를 정의합니다.
typedef struct node
{
    //node 안에서 정수형 값이 저장되는 변수를 name으로 지정합니다.
    int number; 

    //다음 node의 주소를 가리키는 포인터를  *next로 지정합니다.
    struct node *next;
}
node;

int main(void)
{
    // list라는 이름의 node 포인터를 정의합니다. 연결 리스트의 가장 첫 번째 node를 가리킬 것입니다. 
    // 이 포인터는 현재 아무 것도 가리키고 있지 않기 때문에 NULL 로 초기화합니다.
    node *list = NULL;

    // 새로운 node를 위해 메모리를 할당하고 포인터 *n으로 가리킵니다.
    node *n = malloc(sizeof(node));
    if (n == NULL)
    {
        return 1;
    }

    // n의 number 필드에 1의 값을 저장합니다. “n->number”는 “(*n).numer”와 동일한 의미입니다. 
    // 즉, n이 가리키는 node의 number 필드를 의미하는 것입니다. 
    // 간단하게 화살표 표시 ‘->’로 쓸 수 있습니다. n의 number의 값을 1로 저장합니다.
    n->number = 1;

    // n 다음에 정의된 node가 없으므로 NULL로 초기화합니다.
    n->next = NULL;

    // 이제 첫번째 node를 정의했기 떄문에 list 포인터를 n 포인터로 바꿔 줍니다.
    list = n;

    // 이제 list에 다른 node를 더 연결하기 위해 n에 새로운 메모리를 다시 할당합니다.
    n = malloc(sizeof(node));
    if (n == NULL)
    {
        return 1;
    }

    // n의 number와 next의 값을 각각 저장합니다.
    n->number = 2;
    n->next = NULL;

    // list가 가리키는 것은 첫 번째 node입니다. 
    //이 node의 다음 node를 n 포인터로 지정합니다.
    list->next = n;

    // 다시 한 번 n 포인터에 새로운 메모리를 할당하고 number과 next의 값을 저장합니다.
    n = malloc(sizeof(node));
    if (n == NULL)
    {
        return 1;
    }

    n->number = 3;
    n->next = NULL;

    // 현재 list는 첫번째 node를 가리키고, 이는 두번째 node와 연결되어 있습니다. 
    // 따라서 세 번째 node를 더 연결하기 위해 첫 번째 node (list)의 
    // 다음 node(list->next)의 다음 node(list->next->next)를 n 포인터로 지정합니다.
    list->next->next = n;

    // 이제 list에 연결된 node를 처음부터 방문하면서 각 number 값을 출력합니다. 
    // 마지막 node의 next에는 NULL이 저장되어 있을 것이기 때문에 이 것이 for 루프의 종료 조건이 됩니다.
    for (node *tmp = list; tmp != NULL; tmp = tmp->next)
    {
        printf("%i\n", tmp->number);
    }

    // 메모리를 해제해주기 위해 list에 연결된 node들을 처음부터 방문하면서 free 해줍니다.
    while (list != NULL)
    {
        node *tmp = list->next;
        free(list);
        list = tmp;
    }
}