[자료구조] 연결리스트 PART.1

1. 연결 자료구조(Linked Data Structure)

• 자료의 논리적인 순서와 물리적인 순서가 일치하지 않는 자료구조
• 각 원소에 저장된 다음 원소의 주소에 의해 순서가 연결되는 방식
• 물리적인 순서를 맞추기 위한 오버헤드가 발생하지 않음
• 여러 개의 작은 공간을 연결하여 하나의 전체 자료구조를 표현
• 크기 변경이 유연하고 더 효율적으로 메모리 사용
• 리스트를 연결 자료구조로 표현한 구조
• 연결하는 방식에 따라 단순 연결 리스트와 원형 연결 리스트, 이중 연결 리스트, 이중 원형 연결 리스트가 있음

 

2. 연결 리스트의 구성

1) 노드

• 연결 자료구조에서 하나의 원소를 표현하기 위한 단위 구조

(1) 노드의 구조

노드의 구조
데이터 필드	링크 필드

2) 데이터 필드(data field)

• 원소의 값을 저장
• 저장할 원소의 형태에 따라서 하나 이상의 필드로 구성

3) 링크 필드(link field)

• 다음 노드의 주소를 저장
• 포인터 변수를 사용하여 주솟값을 저장

4) 예제

끝말잇기를 할 때 다음과 같이 논리적인 그림을 그릴 수 있다.

 

Data	Link	Data	Link	Data	Link
아기	->	기차	->	차량	NULL

 

Link에는 다음 Data의 주소가 들어 있어서 연결하는 것이다. 연결 구조를 가지지 않으려면 주소 부분에 NULL을 넣어주면 된다.

 

요일을 선형리스트로 나타내면 다음과 같다.

 

	[0]	[1]	[2]	[3]	[4]	[5]	[6]
week	일	월	화	수	목	금	토

 

week라는 이름으로 1차원 배열로 이루어져 있다.

 

연결리스트로 나타내면 다음과 같다.

 

Data

Link

Data

Link

Data

Link

Data

Link

Data

Link

Data

Link

Data

Link

Data

Link

->

일

->

월

->

화

->

수

->

목

->

금

->

토

NULL

 

첫 번째 Link에는 이름이 들어간다. 즉, week의 링크가 되는 것이다.

 

(1) C언어 구조체로 정의

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

typedef struct NODE{
	char *dat;
	struct NODE *link;
} NODE;

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

	NODE *node1 = (NODE *)calloc(1, sizeof(NODE));	// 첫 번째 노드 생성
	week -> link = node1;	// 머리 노드 다음은 첫 번째 노드
	node1 -> dat = "일";	// 첫 번째 노드에 "일" 저장

	NODE *node2 = (NODE *)calloc(1, sizeof(NODE));	// 두 번째 노드 생성
	node1 -> link = node2;	// 첫 번째 노드 다음은 두 번째 노드
	node2 -> dat = "월";	// 두 번째 노드에 "화" 저장

	NODE *node3 = (NODE *)calloc(1, sizeof(NODE));	// 세 번째 노드 생성
	node2 -> link = node3;	// 두 번째 노드 다음은 세 번째 노드
	node3 -> dat = "화";	// 세 번째 노드에 "화" 저장
	node3 -> link = NULL;	// 세 번째 노드 다음 노드가 없음(NULL)
    
	NODE *curr = week -> link; // 연결 리스트 순회용 포인터에서 첫 번째 노드의 주소 저장
    
	while(curr != NULL)		// 포인터가 NULL이 아닐 때 계속 반복
	{
		printf("%s\n", curr -> dat);	// 현재 노드의 데이터출력
		curr = curr -> link;		// 포인터에 다음 노드의 주소 저장
	}
    
	free(node3);	// 노드 메모리 해제
	free(node2);	// 노드 메모리 해제
	free(node1);	// 노드 메모리 해제
	free(week);	// 머리 노드 메모리 해제
    
	return 0;
}

 

3. 연결리스트 삽입

 

1) 연결리스트로 나타낸 구조에 삽입 (중간노드)

 

Data	Link	Data	Link	Data	Link	Data	Link
	->	10	->	20	->	40	NULL

 

위 연결리스트가 있을 때 20과 40 사이에 30을 삽입 하는 경우를 예로 본다.

 

2) 순서

1. 삽입할 새 노드를 만들 공백 노드를 메모리에서 가져와서 포인터 변수 new가 가리킨다.
2. new의 데이터 필드에 30을 저장
3. 20 노드의 링크 필드에 new의 값(new가 가리키고 있는 새 노드의 주소)을 저장
4. new의 앞 노드, 즉 20 노드의 링크 필드 값을 new의 링크 필드에 저장

3) C언어 실습

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

typedef struct NODE {
	int data;
	struct NODE* link;
} NODE;

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

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

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

	NODE* node4 = (NODE*)calloc(40, sizeof(NODE));	// 네 번째 노드 생성
	node2->link = node4;	// 두 번째 노드 다음은 네 번째 노드
	node4->data = 40;	// 네 번째 노드에 40 저장
	node4->link = NULL;	// 네 번째 노드 다음 노드가 없음(NULL)

	NODE* curr = head->link; // 연결 리스트 순회용 포인터에서 첫 번째 노드의 주소 저장
	puts("- 삽입 전 -");

		while (curr != NULL)		// 포인터가 NULL이 아닐 때 계속 반복
		{
			printf("%d\n", curr->data);	// 현재 노드의 데이터출력
			curr = curr->link;		// 포인터에 다음 노드의 주소 저장
		}

	// 삽입 시작
	NODE *NEW = (NODE*)calloc(40, sizeof(NODE));	// 포인터 선언(순서 1)
	NEW -> data = 30;	// new의 데이터 필드에 30 저장 (순서 2)
	NEW -> link = node2 -> link;
	
	// new의 앞 노드, 즉 20 노드의 링크 필드 값을 new의 링크 필드에 저장 (순서 3)

	node2 -> link = NEW;
	// 20 노드의 링크 필드에 NEW의 값(new가 가리키고 있는 새 노드의 주소)을 저장 (순서 4)

	puts("- 삽입 후 -");
		NODE * curr1 = head->link;

	while (curr1 != NULL)		// 포인터가 NULL이 아닐 때 계속 반복
	{
		printf("%d\n", curr1 -> data);	// 현재 노드의 데이터출력
		curr1 = curr1->link;		// 포인터에 다음 노드의 주소 저장
	}

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

	return 0;
}