[자료구조 기초]C언어 연결리스트 How to linked list in c

연결리스트 (linked list) 란?

 

각 노드가 데이터와 포인터를 가지고 한줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조입니다.

데이터를 담고있는 노드들이 연결되어있는데 노드의 포인터가 다음or이전의 노드와 연결되어있다.

 

 

 

Linked list

 

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

 

Node구조체에서 struct NODE *next; 이부분은 다음노드(or이전노드)의 메모리 주소(포인터) 를 저장해야한다.

즉 자기 자신이 아닌 다른 노드의 메모리 주소를 저장하고있다. 이점이 매우 중요하고 핵심이다.

위 예제에서는 int 형 data를 하나만 넣었지만 String int char등 여러개의 데이터가 구조체 멤버에 들어갈수있다.

 

 

단일 연결리스트의 노드 종류

 

ㅁ

º head node :  단일 연결리스트의 기준점이며 헤드 노드(head node)라고 부른다. 헤드 노드는 첫번째 노드를 가리키며

데이터를 저장하지 않는다.

º 노드(node)  : 단일 연결리스트에서 데이터가 저장되는 실제 노드이다.

 

#include <stdio.h>
#include <stdlib.h>    // malloc, free 함수가 선언된 헤더 파일

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


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

    NODE *node1 = (NODE*)malloc(sizeof( NODE));   // 첫 번째 노드 생성
    head->next = node1;                                 // 머리 노드 다음은 첫 번째 노드
    node1->data = 10;                                   // 첫 번째 노드에 10 저장

     NODE *node2 = (NODE*)malloc(sizeof( NODE));   // 두 번째 노드 생성
    
    node1->next = node2;                                // 첫 번째 노드 다음은 두 번째 노드
    node2->data = 20;                                   // 두 번째 노드에 20 저장

    node2->next = NULL;                                 // 두 번째 노드 다음은 노드가 없음(NULL)

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

    free(node2);    // 노드 메모리 해제
    free(node1);    // 노드 메모리 해제
    free(head);     // 머리 노드 메모리 해제

    return 0;
}

 

<실행결과>

 

 

<예제2>

#include <stdio.h>
#include <stdlib.h>

//start = head
struct node{
	struct node* next;
	int age;
	
};

int	main(){
	
	struct node* start = (struct node*) malloc(sizeof(struct node));
	
	struct node* node1 = (struct node*) malloc(sizeof(struct node));
	start -> next = node1;
	
	node1 -> age = 100;
	
	struct node* node2 = (struct node*) malloc(sizeof(struct node));
	node1 -> next = node2;
	node2 -> age = 200;
	
	struct node* node3 = (struct node*)malloc(sizeof(struct node));
	node2 -> next = node3;
	node3 -> age = 400;
	
	node3 -> next = NULL;
	
	struct node* ptr = start->next;
	
	
	
	while(ptr != NULL){
		printf("%d\n",ptr->age);
		ptr=ptr->next;
	}
	
	return 0;
	
}