[자료구조] C언어 연결리스트(Linked list) 생성 / 출력

연결리스트의 기본 구조

 

연결리스트 만들기

 

"월" "화" "수" "목" "금" 등 요일을 데이터값으로 갖는 연결리스트를 만들어보자.

typedef struct node {
 
        char data;
        struct node* next;
 
    } Node;
 
    Node* head = NULL;

 

먼저 구조체로 "노드"의 틀을 만든다.

노드에는 데이터가 들어갈 데이터 변수와 다음 노드를 가리킬 포인터 변수가 있어야 한다.

데이터 변수는 어떠한 자료형이어도 상관없다.

typedef으로 구조체의 별칭을 Node로 정해둔다.

연결리스트의 맨 앞 노드는 head라 부르며 head는 첫번째 노드를 가리키고 있어야 한다.

( = 첫번째 노드의 주소를 가지고 있어야 함.)

위와 같이 head를 선언한 것을 그림으로 그리면 아래와 같다.

 

 

head안에 데이터 값도 없고, 포인터 변수인 next조차 다음 노드를 가리키지 않고 NULL임을 알 수 있다.

여기서 새 노드 node1과 node2를 생성해 서로 연결해주기로 한다.

 

int main() {
    head = (Node*)malloc(sizeof(Node));
    
    Node* node1 = (Node*)malloc(sizeof(Node));
    head->next = node1;
    node1->data = "화";
 
    Node* node2 = (Node*)malloc(sizeof(Node));
    node1->next = node2;
    node2->data = "수";
    node2->next = NULL;
}
 

 

node1을 예시로 코드를 순서대로 살펴보자면 먼저 메모리를 할당하여 head노드와 node1 노드를 생성해준다.

구조체 포인터 연산자 ->를 이용하여 head->next = node1로 head의 포인터 값이 node1을 가르키도록 한다. (연결)

 

 

요일을 데이터 값으로 넣기로 했으니 node1->data에는 "화"를 넣어준다. ( 다음 글에서 첫번째 노드 앞에 새로운 노드를 삽입하는 방법을 설명하기 위해 "월"이 아닌 "화"를 넣음. )

node1의 next에는 아무 값을 넣지 않았으므로 어떤 노드도 가리키고 있지 않다. 이 값이 node2를 가리키게 된다면 node1과 node2는 연결된다.

위와 같은 방법으로 node2도 만들어서 연결하면 아래와 같다.

 

 

 

연결리스트 출력하기

위에서 만든 연결리스트를 출력해보자.

연결리스트를 출력하려면 반복문을 돌 새로운 포인터 변수가 필요하다.

 

Node* tmp = head;
 
while (tmp != NULL) {
 
    printf("%s\n", tmp->data);
    tmp = tmp->next;
 
}

 

tmp라는 새로운 포인터 변수를 선언하고 head의 값을 담는다. head는 첫번째 노드인 node1을 가르키는 포인터 변수이므로 자연스럽게 tmp는 node1을 가르키게 된다.

while문을 돌면서 tmp->data를 출력하게 되므로 각 노드의 data 값을 출력하다가 마지막 값인 NULL이 되면 멈춘다.

쉽게 이해하기 위해 그림과 함께 보자면

 

 

1. Node* tmp = head (node1을 가리킴)
2. tmp->data (node1의 data값 "화" 출력), tmp = tmp->next (node1의 next값이 가리키는 node2를 tmp에 넣어줌)
3. tmp->data (node2의 data값 "수" 출력), tmp = tmp->next (node2의 next값이 가리키는 NULL을 tmp에 넣어줌)
4. tmp값이 NULL이 되어 while문을 종료.

 

 

! 자주 범하는 오류들

출력할 때 자주 범하는 오류들에 대해서 살펴보자.

Node* tmp = head;
 
while (tmp->next != NULL) {
 
    printf("%s\n", tmp->data);
    tmp = tmp->next;
 
}

 

while문 안의 조건이 tmp->next != NULL 이라면 어떻게 될까? 마지막 노드의 next값이 NULL이면 멈춰야 하니 맞지 않을까? 그림을 그려보면 오류가 난다는 것을 알 수 있다.

 

 

while문을 첫번째로 돌 때, tmp->next 값은 node1이 가리키는 값인 node2이므로 NULL이 아니다. 그러므로 정상적으로 while문을 돌아 값을 출력하고 다음 노드로 넘어간다.

하지만 tmp = tmp->next로 node2로 넘어갔을 때, tmp의 next 값은 NULL이기 때문에 node2의 데이터 값이 출력되지 않고 while문이 종료되어버린다.

 

또 다른 실수로는 tmp값에 head가 아닌 head->next를 넣는 것이다.

 

Node* tmp;
tmp = head->next;
 
while (tmp!= NULL) {
 
    printf("%s\n", tmp->data);
    tmp = tmp->next;
 
}

 

head 자체가 node1을 가리키고 있으므로 head의 next 값은 node1의 next값이기 때문에 node2를 가리키게된다.

 

 

그렇다면 tmp는 node2의 값만 출력하고 NULL을 만나 종료하게 된다.

연결리스트는 이해가 가지 않을 때 그림을 그려보는 것이 가시적으로 빠르게 이해할 수 있다.

코드만 봤을 때는 문제가 없을 것 같은 것도 그림을 그려보면 쉽게 오류를 잡아낼 수 있다.

 

 

 

참조 : C로 배우는 쉬운 자료구조 / 이지영 / 한빛아카데미