열혈 자료구조 - 4-1. 연결 리스트의 개념적인 이해

연결 리스트

- 배열 기반 리스트의 단점인 길이(크기)가 고정되어 있다는 점을 커버할 수 있음

- 그리고 배열 기반 리스트의 장점인 순차 접근도 가능

- 필요할 때마다 할당해서 사용하고 할당한 것을 순차적으로 연결

- 가장 처음 부분의 주소값만을 가지고 순차적으로 접근 가능한 것이 연결 리스트

- 연결 리스트를 구성할 때 필요한 부분 : 어떻게 연결할 것인가? 어떻게 순차적으로 접근할 것인가?

 

노드

typedef struct _node 
{
    int data;			// 실제 노드가 가지고 있는 데이터
    struct _node* next;		// 다음 노드를 가르키는 포인터(연결을 담당)
} Node;

Node

Node의 연결

연결 리스트 분석

- 초기화

    -> head : 첫번째 노드(무조건 필요)

    -> tail : 가장 마지막 노드(생략 가능)

    -> cur : 순차접근을 위한 노드

Node * head = NULL;    // NULL 포인터 초기화
Node * tail = NULL;
Node * cur = NULL;

Node * newNode = NULL;

- 삽입 : 노드를 꼬리에 추가

    -> next 부분의 역슬래시 표시는 NULL을 의미

while(1)
{
    printf("자연수 입력: ");
    scanf("%d", &readData);
    if(readData < 1)    break;
    
    newNode = (Node*)malloc(sizeof(Node));		// 동적 할당
    newNode->data = readData;				// 노드의 데이터부분에 저장
    newNode->next = NULL;				// 다음을 가르키는 노드를 우선 NULL로 초기화
    ///////////////////// 1단계 ////////////////////////////////
    
    if(head == NULL)    head = newNode;
    else                tail->next = newNode;
    ///////////////////// 2단계 ////////////////////////////////
    
    tail = newNode;
    ///////////////////// 3단계 ////////////////////////////////
}

첫 데이터 삽입

다음 데이터 삽입

- 조회 : 순차적으로 접근

if(head == NULL) 
{
    printf("저장된 자연수가 존재하지 않습니다. \n");
}
else 
{
	cur = head; 
	printf("%d  ", cur->data);   // 첫 번째 데이터 출력

	while(cur->next != NULL)    // 두 번째 이후의 데이터 출력
	{
	    cur = cur->next;			// 이동하고
	    printf("%d  ", cur->data);		// 조회하고
	}
}

 

- 삭제 : 노드 2개를 사용하여 삭제 과정을 진행

if(head == NULL) 
{
    return 0;    // 해제할 노드가 존재하지 않는다.
}
else 
{
	Node * delNode = head;
	Node * delNextNode = head->next;

	printf("%d을(를) 삭제합니다. \n", head->data);
	free(delNode);    // 첫 번째 노드의 삭제

	while(delNextNode != NULL)    // 두 번째 이후의 노드 삭제 위한 반복문
	{
	    delNode = delNextNode;
	    delNextNode = delNextNode->next;
    
	    printf("%d을(를) 삭제합니다. \n", delNode->data);
	    free(delNode);    // 두 번째 이후의 노드 삭제
	}
}