C와 Linked List [ 크래프톤 정글 34일차 ]

여전히 크래프톤 정글에서 살아남기중. 어제는 포인터에 대해서 공부했는데요. 이걸로 Linked List를 구현할 수 있어요.

이번 주차는 C 언어로 Linked List와 Stack and queue,binary Tree,binary Search Tree 를 구현하는 것인데요. 기본 자료구조를 구현하면서 C언어에 익숙해지는 과정이예요.

Linked List 를 구현하고 배열과는 어떻게 다른지 알아보려해요.

1. 배열과 연결리스트의 차이

배열과 연결리스트는 굉장히 비슷하지만 차이점이 있어요.

항목	배열 (Array)	연결 리스트 (Linked List)
메모리 구조	연속된 공간에 저장	노드가 따로따로 흩어져 있음 (포인터로 연결)
접근 속도	O(1) (인덱스로 바로 접근 가능)	O(n) (처음부터 따라가야 함)
삽입/삭제	느림 (중간에 삽입 시 밀어야 함)	빠름 (포인터만 바꾸면 됨)
메모리 크기	고정 크기 (처음에 정해줘야 함)	유동적 (필요할 때마다 할당 가능)

배열은

• 메모리상에 0x00..0x01..0x02...0x10... 순서로 저장돼요. 그래서 연속된 공간에 저장되어있어요.
• 그래서 인덱스 번호로 찾을 때, O(1)로 굉장히 빠르다는 장점이 있어요.
• 다만 삽입/삭제 연산을 할 때는 메모리를 다시 옮겨줘야 하기 때문에 O(n)의 시간이 걸려요.
• 그리고 런타임환경에서 동적으로 메모리를 할당하기가 어려워요.

연결리스트는

• 메모리 상에 0x00->0x10->0x23414 이런식으로 따로따로 흩어져 있어요.
• 그래서 인덱스 번호로 접근할 수 없고, 처음부터 따라가야 해요.
• 다만 삽입/삭제 연산을 할 때는 포인터만 바꾸면 되기 때문에 빨라요.
• 메모리를 malloc,realloc,calloc,free 등으로 런타임환경에서 유동적으로 변경할 수 있어요.

2. 연결리스트는 어떻게 만들까?

2.1 기본 연결리스트

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

typedef struct _listnode
{
    int item;               // item 이라는 int 자료형 값을 가져요.
    struct _listnode *next; // ListNode 라는 타입을 가진 구조체의 주소를 가져요.
} ListNode;

typedef struct _linkedlist
{
    int size;       // size 라는 값을 가져요.
    ListNode *head; // 별칭 ListNode 타입을 가지는 *head 라는 이름의 주소예요.
} LinkedList; 

listNode 안에 next가 중요한 부분인데요.

저게 바로 '연결'시켜주는 부분이랍니다. next를 가리키면서 다음 노드의 메모리 주소를 가리켜요.

자기자신과 같은 struct를 포인터로 참조할 수 있어요. 이게 바로 노드끼리 연결시켜주는 핵심포인트랍니다.

LinkedList ll;
ll.head = NULL;
ll.size = 0;

실제로 LL ( Linked List )를 사용할 땐 이렇게 초기화 시켜줘야해요.

2.1 삽입과 삭제

int insertNode(LinkedList *ll, int index, int value)
{

    ListNode *pre, *cur;

    if (ll == NULL || index < 0 || index > ll->size + 1)
        return -1;

    if (ll->head == NULL || index == 0)
    {
        cur = ll->head;
        ll->head = malloc(sizeof(ListNode));
        ll->head->item = value;
        ll->head->next = cur;
        ll->size++;
        return 0;
    }

    if ((pre = findNode(ll, index - 1)) != NULL)
    {
        cur = pre->next;
        pre->next = malloc(sizeof(ListNode));
        pre->next->item = value;
        pre->next->next = cur;
        ll->size++;
        return 0;
    }

    return -1;
}

int removeNode(LinkedList *ll, int index)
{

    ListNode *pre, *cur;

    if (ll == NULL || index < 0 || index >= ll->size)
        return -1;

    if (index == 0)
    {
        cur = ll->head->next;
        free(ll->head);
        ll->head = cur;
        ll->size--;

        return 0;
    }

    if ((pre = findNode(ll, index - 1)) != NULL)
    {

        if (pre->next == NULL)
            return -1;

        cur = pre->next;
        pre->next = cur->next;
        free(cur);
        ll->size--;
        return 0;
    }

    return -1;
}

삽입과 삭제를 할 때 index를 명시해주지 않으면 어떤걸 삭제할 지 모르기 때문에 명시해줘야해요.

삽입과 삭제연산은 next 를 변경해주고 free()로 메모리를 해제해 준다는 것을 알 수 있어요.

마무리

연결리스트 이 외에도 원형 연결 리스트나 이중 연결 리스트같은 응용 연결리스트가 있어요.

연결 리스트를 사용해보면서 포인터에 대해 좀 더 이해해보는 시간이 되면 좋을 것 같아요.