c언어 - 단일연결리스트

단일 연결 리스트

연결 리스트는 데이터가 담긴 노드(메모리 공간)를 서로 연결해놓은 상태를 말합니다. 단일 연결 리스트는 다른 노드를 가리키는 포인터가 하나씩만 있어서 단일 연결 리스트라고 합니다. 따라서 한 쪽 방향으로만 이동할 수 있습니다.

단일 연결 리스트의 구조체는 다음 노드의 주소를 저장하는 next 포인터를 멤버로 가지고 있습니다.

1 2 3 4

struct NODE {             // 연결 리스트의 노드 구조체     struct NODE *next;    // 다음 노드의 주소를 저장할 포인터     int data;             // 데이터를 저장할 멤버 }; Colored by Color Scripter

cs

단일 연결 리스트의 머리 노드

머리 노드(head node)는 단일 연결 리스트의 시작점이며 헤드(head)라고도 부릅니다. 특히 머리 노드는 연결 리스트의 첫 번째 노드를 가리키는 용도이므로 데이터를 저장하지 않습니다.

struct NODE *head = malloc(sizeof(struct NODE));    // 머리 노드 생성
                                                    // 머리 노드는 데이터를 저장하지 않음

free(head);    // 리스트를 사용한 뒤 동적 메모리 해제

단일 연결 리스트의 노드 추가

단일 연결 리스트에 노드를 추가하려면 먼저 새 노드를 생성(메모리 할당)합니다. 그리고 새 노드의 다음 노드에 기준 노드의 다음 노드를 지정한 뒤 기준 노드의 다음 노드에 새 노드를 지정하면 됩니다.

void addFirst(struct NODE *target, int data)    // 기준 노드 뒤에 노드를 추가하는 함수
{
    struct NODE *newNode = malloc(sizeof(struct NODE));    // 새 노드 생성
    newNode->next = target->next;    // 새 노드의 다음 노드에 기준 노드의 다음 노드를 지정
    newNode->data = data;            // 데이터 저장

    target->next = newNode;    // 기준 노드의 다음 노드에 새 노드를 지정
}

단일 연결 리스트의 노드 삭제

단일 연결 리스트는 기준 노드의 다음 노드를 삭제합니다. 따라서 기준 노드의 다음 노드에 삭제할 노드의 다음 노드를 지정하여 노드를 끌어옵니다. 노드간 연결을 정리했다면 삭제할 노드를 free 함수로 해제해줍니다.

void removeFirst(struct NODE *target)    // 기준 노드의 다음 노드를 삭제하는 함수
{
    struct NODE *removeNode = target->next;    // 기준 노드의 다음 노드 주소를 저장
    target->next = removeNode->next;    // 기준 노드의 다음 노드에 삭제할 노드의 다음 노드를 지정

    free(removeNode);    // 노드 메모리 해제
}

단일 연결 리스트의 순회

연결 리스트를 순회하려면 첫 번째 노드(head->next)부터 시작해서 현재 노드 curr에 curr->next를 계속 넣어주는 식으로 만듭니다. 이때 curr이 NULL이면 리스트의 끝이므로 반복을 끝내면 됩니다.

struct NODE *curr = head->next;    // 연결 리스트 순회용 포인터에 첫 번째 노드의 주소 저장
while (curr != NULL)               // 포인터가 NULL이 아닐 때 계속 반복
{
    printf("%d\n", curr->data);    // 현재 노드의 데이터 출력
    curr = curr->next;             // 포인터에 다음 노드의 주소 저장
}

공부 : c언어 코딩도장