연결리스트(Linked List) 알아보기

연결리스트(linked list)

노드(node) 단위로 구성

각 노드가 다음 노드의 주소를 가리켜 서로 연결된 형태로 데이터를 관리하는 선형 자료 구조

배열과 달리 동적으로 메모리 할당 -> data element들이 비연속적인 메모리 위치에 저장

각 노드는 데이터 필드와 링크(포인터) 필드로 이루어져 있습니다. 

데이터 필드: 노드에 저장되는 실제 데이터

링크 필드: 다음 노드를 가리키는 포인터

위 그림의 Data가 데이터 필드, Next가 링크 필드입니다.

 

연결리스트는 이 두 요소를 이용해 여러 개의 노드를 연결해 리스트를 만드는데요.

첫 번째 노드를 가리키는 포인터를 헤드(head), 마지막 노드를 테일(tail)이라고 합니다.

 

연결리스트의 노드를 구조체로 정의하면 다음과 같습니다.

typedef struct Node {
    int data;           // 데이터 필드
    struct Node* next;  // 다음 노드를 가리키는 포인터
} Node;

이 구조체를 이용해 기본적인 연결리스트의 노드 생성, 추가, 리스트 출력, 메모리 해제를 알아볼게요!

---🐢

노드 생성

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));

    newNode->data = data;
    newNode->next = NULL;

    return newNode;
}

위 함수는 데이터를 인자로 받아 새 노드를 생성하고, 노드에 대한 포인터를 반환합니다.

 

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

newNode: Node 구조체에 대한 포인터

malloc 함수를 사용해 Node 크기만큼의 메모리를 동적 할당

 

newNode->data = data;

newNode의 데이터 필드에 data 값 저장

 

newNode->next = NULL;

newNode의 링크 필드(next)를 NULL로 초기화

: 현재 노드가 리스트의 마지막 노드(연결 X)

--🐢-

노드 추가

void appendNode(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
    }
    else {
        Node* temp = *head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
}

Node** head

head 포인터에 대한 이중 포인터

: head 포인터를 직접 수정하기 위해

(main함수) Node* head = NULL; appendNode(&head, data);

 

Node* newNode = createNode(data);

먼저 새 노드를 만듦

 

if (*head == NULL) { *head = newNode; }

리스트가 비어있으면 포인터가 가리키는 값을 새로 생성된 노드의 주소로 설정

 

Node* temp = *head;

헤드가 가리키는 노드로 포인터 초기화

 

while (temp->next != NULL) { temp = temp->next; }

리스트 마지막 노드까지 링크 필드를 따라 계속 노드 이동

 

temp->next = newNode;

마지막 노드의 링크 필드를 newNode로 설정

-🐢--

리스트 출력

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

Node* temp = head;

temp 포인터를 선언하고 head로 초기화

: head 포인터 자체를 변경하지 않기 위해

 

while (temp != NULL)

리스트의 모든 노드를 방문할 때까지

 

printf("%d -> ", temp->data);

데이터 필드 출력

 

temp = temp->next;

다음 노드로 이동

 

printf("NULL\n");

리스트의 끝 표시

🐢---

메모리 해제

void freeList(Node* head) {
    Node* temp;
    while (head != NULL) {
        temp = head;
        head = head->next;
        free(temp);
    }
}

🤔: 왜 temp 포인터를 사용하나요? 바로 head를 사용해 free 하면 안 되나요?

🐢: head를 바로 사용하면 head를 이동한 후 현재 노드의 주소를 잃어버리게 되기 때문에, free 함수를 호출할 수 없어요! 모든 노드를 순차적으로 해제하는 게 중요하답니다!