- 본 포스트는 주로 윤성우님의 <열혈 자료구조>를 공부하며 작성된 글입니다.
- 필자의 복습을 위한 요약이 주 목적이며 따라서 생략된 부분이 많을 수 있습니다.
- 오타나 잘못된 내용이 발견될 시 답글로 남겨주시면 감사하겠습니다.
- 이하 내용은 C언어를 바탕으로 하고 있으며, 구조체(Struct)문법에 대한 이해를 필요로 합니다.
동적할당
연결리스트를 다루기 위해선, 동적할당(Dynamic Allocation)개념을 알고 있어야 한다.
순차리스트는 리스트 자료구조를 배열 기반으로 만든 자료구조이다. 배열의 장점은 Index를 이용해 값을 쉽고 빠르게 접근가능하다는 점이었다. Index값만 알고 있다면 배열의 탐색 빅오는 이라는 성능을 보여준다.
하지만 배열의 치명적인 단점은 선언시 크기가 결정되어야 한다는 점이다. 또한 런타임동안 결정된 배열의 크기를 바꿀 수 없다.
이를 보완하기 위한 기술이 동적할당이다.
동적할당은 프로그램 작성 단계에서 필요한 메모리 공간의 크기가 정해지지 않았을 경우 사용한다. 따라서 컴파일타임이 아니라, 런타임에 필요한 메모리공간을 정한다.
동적할당을 사용하면 런타임동안 힙(Heap) 메모리 공간을 OS로부터 할당받는다.
이 힙공간은 스택과 OS가 가상메모리관리 기법을 이용하기 때문에 더 폭 넓게 사용할 수 있는 장점이 있다.
#include <stdlib.h>
int main() {
int n = 0;
...
char* arr = (char*)malloc(sizeof(char)*n); //동적할당
...
free(arr); //동적 할당받은 메모리 해제
return 0;
}위 예제에서 동적할당받을 메모리의 크기를 결정하는 변수n은 런타임 시간에 결정되어도 된다! 이런 특성덕분에 동적할당이라고 불리는 것이다.
OS에게 메모리를 요청할때는 보통 malloc()함수를 이용한다. 이후 메모리 사용이 끝나면 반드시 free()함수로 해당 공간의 사용이 끝났음을 OS에게 알려야 한다.
이것이 Java와 C의 차이점중 하나인데, 자바는 가비지컬렉터가 어떤 메모리 공간의 주소가 Identifier를 잃어버리면 해당 공간을 자동으로 해제해버린다.
하지만 C에서는 프로그래머가 직접 free()함수를 통해 공간 사용을 해제해야 한다. 그렇지 않다면 런타임 동안 메모리 누수(Memory Leak)가 발생할 가능성이 있다.
malloc()함수는 할당받은 공간의 첫번째 주소를 반환한다. 즉 포인터를 반환하는데, 이 포인터의 타입이 void*이기 때문에, 사용자가 직접 어떤 타입으로 사용할 것인지 형변환(casting)해줘야 한다.
그렇지 않다면 해당 포인터에 메모리공간에서 사용할 자료형의 크기가 정보로 담겨있지 않아서 포인터 연산을 사용할 수 없다.
연결리스트(LinkedList)
앞서 순차리스트의 단점을 극복하기 위해 동적할당받은 메모리공간을 사용하는 아이디어를 제안했다.
그런데 동적할당의 문제는... OS가 제공하는 메모리공간의 위치를 예상할 수 없다는 것이다. 즉, 마구잡이로 생긴 공간들을 관리하기 어렵다.
핵심은 이렇게 동적할당 받아 제각기 존재하는 공간들을 순차적으로 관리하는 것이다. 순차적으로 관리하면 리스트 자료구조의 특성인, 값의 순서를 유지하는 특성을 살릴 수 있다.
이는 코드레벨에서 어떻게 구현할 수 있을까? 한번 고민해 보는 것도 좋은 공부이다.
typedef struct _node
{
int data;
struct _node* next; //다음 노드의 주소
} Node;위의 노드 구조체에서는, 한 노드가 다른 노드의 주소를 포인터 변수로 담고 있다. 이런식으로 위 그림이 가능해지는 것이다.
이제 우리는 가장 첫번째 노드의 주소를 head로, 가장 마지막 노드의 주소를 tail로 명명해 따로 관리할 것이다.
여기서 위 그림처럼 연결된 리스트가 유지되기 위해서는 각 노드가 가진 포인터와 노드 주소간 단사함수(일대일 함수)가 유지되어야 한다는 점도 알 수 있다.
예를 들어 어떤 두 개 이상의 노드의 포인터 변수가 같은 노드의 주소를 가리키는 식으로 연결리스트를 구성한다면?
상상만해도 이를 관리하기는 매우 힘들 것 같다. 관두자
