[열혈자료구조] 4강. 연결 리스트(Linked List) 2 - (1)

* 본 글은 [윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서] 를 바탕으로 작성하였습니다.

 

앞선 포스팅에서는 열혈자료구조 3장에서 다루었던 추상 자료형(ADT)과 배열로 정의한 리스트의 구현을 정리하였다. 4강부터는 배열이 아닌, "연결"을 기반으로 한 리스트의 새로운 정의에 대해 다룬다.

 

리스트를 배열로 정의하는 것의 단점은, 앞선 포스팅의 코드를 보면 알 수 있겠지만 최대 길이가 정해져 있다는 것이다. 즉 정적으로 100개의 메모리를 할당했으므로, 100개가 넘는 자료를 저장할 수 없다. 이에 따라 메모리를 동적으로 구성하여 리스트를 정의해야 한다. 이를 위해, 노드를 연결하여 리스트를 만드는 방식을 사용하자.

 

노드의 정의

노드(Node)는 데이터를 저장할 수 있으며 다른 노드와 연결이 가능한 개체이다. 마지막 데이터는 의미 없는 주소인 Null에 연결된다.

이러한 노드를 구조체로 아래와 같이 정의할 수 있다. 즉 노드에는 (1) 데이터 (2) 다음 노드의 주소 두 가지가 저장된다

typedef struct _node
{
	int data;
	struct _node * next;
} Node;

 

이제 이러한 노드를 통해 연결 리스트를 정의하자. 리스트의 첫 번째 노드를 head, 마지막 노드를 tail이라고 한다면, 리스트의 첫 선언은 아래와 같은 상황으로 생각할 수 있다. head와 tail 안에 든 포인터는 Null을 가리키고 있다.

코드에서는 head와 tail, 그리고 데이터를 조회하는 노드 cur를 모두 Null로 초기화한다.

Node * head = NULL;
Node * tail = NULL;
Node * cur = NULL;

 

자연수 무한히 입력받기

 

연결 리스트를 이용하여 구현한 자연수를 계속 입력 받다가 0 이하 정수가 들어오면 멈추는 프로그램은 아래와 같다.

	while(1)
	{
		printf("new positive integer data: ");
		scanf("%d", &readData);
		if(readData < 1)
			break;


		newNode = (Node*)malloc(sizeof(Node));
		newNode->data = readData;
		newNode->next = NULL;

		if(head == NULL)
			head = newNode;
		else
			tail->next = newNode;

		tail = newNode;
	}

 

자연수 하나를 입력받을 때마다 새로운 노드 하나를 메모리에 할당하여 입력받은 수를 저장하고, 이어지는 다음 노드로 NULL을 가리킨다. 헤드가 NULL을 가리키고 있다면, head가 newNode를 가리키게 되며, tail도 newNode를 가리키게 된다. 즉 "2" 라는 수를 입력 받았을 때, 아래와 같이 구조가 변한다.

 

여기서 2는 데이터를 갖고 있는 처음이자 마지막 노드이기 때문에, head와 tail은 모두 이 노드를 가리킨다. 하나의 데이터 5가 더 들어온다고 해 보자. 그러면 head의 포인터는 NULL이 아닌 2 노드를 가리키고 있었기 때문에 head의 연결은 변하지 않고, tail의 포인터가 5 노드로 바뀐다. 5 노드가 Null을 가리키고 있는 것을 아래와 같이 사선으로 표현하였다.

 

2, 5, 8, 11... 등의 수를 추가하면 아래와 같이 구조가 변한다. head의 포인터는 항상 2 노드를 가리키며, tail은 추가되는 새로운 노드를 가리킨다.

 

데이터 조회

 

연결 리스트에서의 데이터 조회는 cur라고 하는 "데이터 조회용 노드" 를 사용한다. 만약 head가 NULL을 가리키고 있다면, 저장된 수가 없는 것고, head가 가리키는 노드가 있다면 cur이 가리키는 노드가 해당 노드부터 하나씩 다음 노드를 가리켜 가며 노드에 있는 데이터 값을 읽는다.

이를 코드로 나타내면 아래와 같다. 마지막 노드에 도착하면, 노드가 가리키고 있는 곳이 NULL이 되므로 이때 중단하면 된다.

if(head == NULL) 
	{
		printf("No positive integers are saved in the list. \n");
	}
	else 
	{
		cur = head; 
		printf("%d  ", cur->data); 
		
		while(cur->next != NULL)
		{
			cur = cur->next;
			printf("%d  ", cur->data);
		}
	}

 

데이터 삭제

 

데이터 삭제는 cur로 데이터를 출력하는 것과 유사하게, 삭제를 위한 새로운 node를 정의하여 head에서부터 출발하여 한 칸씩 옮겨 가는 알고리즘을 사용할 것이다. 단, 이 때는 cur와 달리 두 개의 node (delNode, delNextNode) 가 같이 움직일 것이다. 코드부터 먼저 확인하자.

if(head == NULL) 
	{
		return 0;
	}
	else 
	{
		Node * delNode = head;
		Node * delNextNode = head->next;

		printf("deleting %d. \n", head->data);
		free(delNode);
		
		while(delNextNode != NULL)
		{
			delNode = delNextNode;
			delNextNode = delNextNode->next;

			printf("deleting %d. \n", delNode->data);
			free(delNode);
		}
	}

	return 0;

 

먼저 delNode의 포인터를 head와 일치시키고, delNextNode의 포인터는 head->next와 일치시킨다. 그림으로 나타내면 아래와 같다.

 

이렇게 두 개의 노드를 잡아서 삭제를 하는 이유는, delNode가 가리키는 노드를 그냥 삭제해 버리면 삭제될 노드가 가리키는 다음 노드의 주소도 사라져 접근이 불가능해지기 때문이다. 따라서, delNextNode의 기능은, 2 노드에 저장되어 있는 5 노드의 주소를 미리 옮겨놓는 기능이라 할 수 있다. 

delNode = delNextNode;
delNextNode = delNextNode->next;

 

2 노드가 삭제되면, 반복문에서 위 코드가 실행된다. 즉 delNode와 delNextNode가 한 칸씩 옆으로 이동하는 것이다.

여기서부터는 다시 delNode가 가리키는 노드를 삭제하고, 한 칸 이동하는 과정이 반복되며, 마지막 노드가 삭제될 때까지 반복된다.

---

 

다음 포스팅에서는 단순 연결리스트의 ADT를 정의하고, 정렬 기능과 노드 삽입 기능을 구현하는 방법을 정리하고자 한다.