링크드리스트에 관한 포스팅에 들어가기전에 대부분의 자료구조에서 사용되는 자기참조구조체에 관해서 알아보도록 하자.
자기참조구초제(Self-referential structure)는 링크드리스트 뿐만 아니라 여러 자료구조에서(이를테면 그래프의 표현이나, 트리등의 자료구조를 작성할 때) 사용한다.
아주 중요한 개념이라고 할 수 있는데 실질적으로 작성해보면 어렵지 않다.
자기참조구조체를 사용하는 자료구조에서는 대부분 하나의 데이터 단위를 자기참조구조체로 관리하게 되는데 기본적으로 자기가 관리하는 데이터 정보와 자신의 타입의 레퍼런스를 가지고 있다. 모양을 보면 다음과 같다.
1 2 3 4 5 | struct [struct_name] { [datatype] datatype_name; [struct_name *] pointer_name; }; | cs |
여기서 이런 공부를 처음 시작하는 사람들이 자주 혼동하는 개념이 있다.
이게 다 이름을 저 모양으로 지어놔서 그렇다. ㅡㅡ..
자기참조구조체면 마치 나 스스로를 참조할 것 같아 보이지만 참조의 대상이 나라는 구조체가 아니라 나와 같은 타입이다. 즉, 나와 같은 타입의 다른 구조체를 가르킨다고 보면 된다.( 물론 구현에 따라 자기 스스로를 가르킬... 수도 있다.)
여기서 자기참조구조체는 참조하는 대상이 한개일 수도 있지만 여러개일 수 있다. 이것도 어떤 자료구조를 구현할지에 따라서 달라진다. 예를들면 double linked list 를 구현하게 될경우 레퍼런스를 두개 사용해야하고, 자식의 갯수가 n개인 n-진트리를 작성하게 될 경우 레퍼런스가 n개가 될 것이다.
double linked list의 자기참조 구조체를 잠깐 살펴보면 아래와 같다.
1 2 3 4 5 | struct linked_node { int value; struct linked_node * prev; struct linked_node * next; }; | cs |
서론이 너무 길었던 것 같다. 다음번 포스트는 정말로 링크드리스트에 관하여 다루겠다.
'Computer Science > 자료구조' 카테고리의 다른 글
| 자료구조 포스팅에 앞서서... (0) | 2016.10.12 |
|---|---|
| 자료구조 연재 시작 (0) | 2016.10.12 |