[자료구조][C] Linked List(연결 리스트)

1. Linked List란?

Linked list(연결 리스트)는 메모리 공간에서 특정 위치를 불연속적으로 점유하는 데이터 element의 선형 집합이다.
array와 달리 데이터들의 메모리 공간이 연속적이지 않기 때문에 한 노드 안에 데이터와 함께 다음 데이터의 주소를 저장해야 한다.
array에 비해 데이터의 추가 및 삭제가 매우 편리하고, 메모리의 연속적 공간을 할당하지 않아도 된다는 장점이 있다.

2. 구조체 및 기본 함수 구현

Node 구조체

typedef struct Node{
	int data;
	struct Node* next;
} Node;

typedef struct {
	Node* head;
} LinkedList; 

먼저 linked list 안의 각 노드를 나타내는 struct Node와 linked list를 구현할 struct LinkedList를 선언, 정의한다.

연결리스트를 생성하는 함수

void makeLinkedList(LinkedList* list)
{
	list->head = NULL;
}

그리고 LinkedList를 만드는 함수를 만들었다.
인자로 LinkedList* 형식의 list를 받아서, list의 head(맨 처음 노드)를 NULL로 초기화해준다.

맨 뒤에 값을 추가하는 함수

void append(LinkedList* list, int data)
{
    Node* newNode = (Node*)malloc(sizeof(Node));
    
    newNode->data = data;
    newNode->next = NULL;

    if (list->head == NULL) {
        list->head = newNode;
        return;
    }

    Node* temp = list->head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
}

LinkedList의 끝에 값을 추가하는 함수를 만들었다.
새 노드 newNode를 만들고, malloc으로 메모리를 할당해준다.
newNode에 값을 넣고, 다음 노드의 주소값에는 NULL을 할당한다.(이 노드가 제일 끝 노드이기 때문)
만약 list가 초기화되어 있지 않다면 newNode를 head로 설정한다.
마지막 while 문에서는 list의 끝을 찾아 그 끝에 있던 노드와 newNode를 연결해준다.

연결리스트를 출력하는 함수

void display(LinkedList* list) {
    Node* temp = list->head;
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

Linked list의 모든 노드를 출력하는 함수도 만들었다.
temp가 NULL이 아닐 때까지 노드를 이동해가며 출력한다.

3. main 함수에서 삽입, 삭제 구현

값 삽입

int main(void)
{
    LinkedList list;
    makeLinkedList(&list);

    append(&list, 1);
    append(&list, 2);
    append(&list, 3);
    append(&list, 4);
    append(&list, 5);

    Node* newNode;
    newNode = (Node*)malloc(sizeof(*newNode));
    newNode->data = 6;
    newNode->next = list.head;
    list.head = newNode;
}

main 함수에서 linked list를 하나 만들고, 1부터 5까지 값을 순서대로 추가했다.
이때 1 노드 앞에 6이라는 값을 가진 노드를 삽입하고자 한다.
먼저 newNode를 만들고, malloc으로 메모리 할당을 했다.
그리고 newNode에 6이라는 값을 추가하고, newNode와 list.head(1 노드)를 연결했다.
마지막으로 head를 newNode로 바꾸면 6 노드가 1 노드 앞에 삽입된다.
새로 만든 노드를 리스트 중간에 삽입하려면 newNode의 전 노드와 newNode를 연결,
newNode와 newNode의 다음 노드를 연결하면 된다.

값 삭제

int main(void)
{
    LinkedList list;
    makeLinkedList(&list);

    append(&list, 1);
    append(&list, 2);
    append(&list, 3);
    append(&list, 4);
    append(&list, 5);

    Node* beforeNode = list.head->next;
    Node* deleteNode = beforeNode->next;
    beforeNode->next = beforeNode->next->next;
    free(deleteNode);
}

위와 같은 linked list에서 3 노드를 삭제하고자 한다.
먼저, beforeNode를 만들어 3 노드의 이전 노드를 할당한다.
deleteNode는 지울 노드인 3 노드를 할당하고,
beforeNode와 deleteNode의 다음 노드를 연결한다.
그리고 deleteNode의 메모리를 해제해주면 3 노드가 삭제된다.