[연결리스트] #3. 연결리스트의 생성

연결리스트(Linked list)

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

노드의 포인터가 다음이나 이전의 노드와의 연결을 담당한다.

 

GOOD	원하는 만큼 노드를 동적으로 추가/삭제할 수 있다.
BAD	메모리공간에 정렬 되어있지 않아, 배열의 인덱스처럼 특정 노드에 바로 접근할 수 없다.

연결리스트의 종류

	이전 노드의 주소 저장 여부	방향성
단일연결리스트	X	Head -> Tail
이중연결리스트	O	Head <-> Tail

연결리스트 생성

 

연결리스트 생성(1)

1.연결리스트 구조체를 생성한다.(head)
2.헤드(head)노드를 동적할당으로 생성 후 NULL과 연결한다.
3.Node1이라는 새로운 노드를 동적할당한다.
4.Node1을 head와 NULL사이에 연결한다.(node1의 꼬리를 head의 꼬리로 연결)
5.Node1의 값을 업데이트한다.

 

연결리스트 생성(2)

head와 NULL사이에 연결된 node1의 후위에 연결 할 node2를 동적할당한다.
node2의 방향포인터와 값을 업데이트한다.

 

연결리스트 순회 및 해제

 

연결리스트 순회 및 해제

다음 노드의 방향이 NULL일때 까지 반복한 후 메모리를 해제한다.

전체 코드

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

/*연결 리스트를 구현할 구조체*/
typedef struct NODE{
    int data;
    struct NODE* next;//자가 참조 구조체
    /*다음 노드의 주소를 저장할 자기참조 구조체포인터*/
}node;

int main(){
    /*노드를 메모리 동적 할당으로 생성하기*/
    node* head = (node*)malloc(sizeof(node)); //헤드 노드 생성
    head->next = NULL;
    node* node1 = (node*)malloc(sizeof(node)); //node1 이라는 새로운 노드를 새로 할당
    

    /*머리노드와 node1을 연결하기*/
    node1->next = head->next;//node1의 꼬리를 (기존)헤드의 꼬리로 연결
    node1->data = 10;//node1의 데이터 업데이드
    head->next = node1;//헤드의 꼬리를 node1으로 업데이트

    /*node1와 node2을 연결하기*/
    node* node2 = (node*)malloc(sizeof(node)); //node2 이라는 새로운 노드를 새로 할당

    node2->next = node1->next;//node1의 꼬리를 (기존)헤드의 꼬리로 연결
    node2->data = 20;//node1의 데이터 업데이드
    head->next = node2;//헤드의 꼬리를 node1으로 업데이트

    node* curr = head->next; //순회용 노드 생성
	while(curr != NULL){
		printf("%d\n", curr->data);
		curr = curr->next;
	}

    free(head);
	free(node1);
	free(node2);
	return 0;
}

 

순서도

1.연결리스트 구조체 생성하기
2.헤드(head)노드를 동적할당으로 생성 후 NULL과 연결
3.Node1이라는 새로운 노드를 생성
4.Node1을 head와 NULL사이에 연결(node1의 꼬리를 head의 꼬리로 연결)
5.Node1의 값을 업데이트
6.순회용 노드 생성
7.다음 노드의 방향이 NULL이 아닐 때 까지 반복
8.반복 종료 시 메모리 해제

 

노드 순서도