[자료구조] 연결리스트 - 구현

 

1. 연결리스트에서 하나의 노드를 표현하기 위한 구조체를 선언한다.

struct node {
	char *data; // 데이터 필드
	struct node* next; // 링크 필드
};
typedef struct node NODE;
NODE *head = NULL; // 첫 노드의 주소를 저장할 포인터

 

data

next

하나의 노드는 데이터 필드와 링크 필드로 구성된다. 

링크 필드는 다음 노드의 주소를 저장하며, 첫 노드의 주소는 head 라는 포인터 변수에 따로 저장해야 한다.

 

 

2. head 노드를 생성한다.

head = (NODE*)malloc(sizeof(NODE));
head->data = "Tuesday";
head->next = NULL; // 반드시 마지막 노드임을 NULL로 표시

 

head 노드

Tuesday

NULL

 

 

3. 다음 노드를 생성한다.

NODE* q = (NODE*)malloc(sizeof(NODE));
q->data = "Thursday";
q->next = NULL;
head->next = q;

head 노드

Tuesday

q 노드

Thursday

NULL

 

현재 head 노드의 next는 q 노드의 data 부분을 가리키고 있다.

 

 

4. head 앞에 새 노드를 추가한다.

q = (NODE*)malloc(sizeof(NODE));
q->data = "Monday";
q->next = head;
head = q;

head 노드

Monday

head 노드였던 노드

Tuesday

 

Thursday

NULL

 

 

5. 모든 노드를 방문해 data를 출력한다.

	NODE* p = head; // 현재 head에 저장된 값을 p에 저장
	while (p != NULL) {
		printf("$s\n", p->data);
		p = p->next;
    }

 

p는 모든 노드를 방문한다.

현재 p가 가리키는 노드의 data를 NULL이 될 때까지 출력한다.

 

 

[전체코드]

#include <stdio.h>
#include <stdlib.h>
struct node {
	char *data;
	struct node* next;
};
typedef struct node NODE;
NODE *head = NULL;

int main() {
	head = (NODE*)malloc(sizeof(NODE));
	head->data = "Tuesday";
	head->next = NULL;
	
	NODE* q = (NODE*)malloc(sizeof(NODE));
	q->data = "Thursday";
	q->next = NULL;
	head->next = q;

	q = (NODE*)malloc(sizeof(NODE));
	q->data = "Monday";
	q->next = head;
	head = q;

	NODE* p = head; // 현재 head에 저장된 값을 p에 저장
	while (p != NULL) {
		printf("$s\n", p->data);
		p = p->next;
	}
}