들어가면서 .NET 환경에서 기본적으로 제공하는 Linked List<>및 Linked List Node<>는 reference 타입입니다.NET과 같은 자동 메모리 관리 기술이 적용된 프로그래밍 언어에서는 접속 목록 사용이 Garbage Collector(이하 GC)의 성능 저하로 이어질 수 있습니다.
따라서 접속목록의 특성인 빠른 삽입(추가와 다름)과 삭제를 유지하면서 레퍼런스 참조를 최소화할 수 있는 특수한 Linked List를 원했습니다.목표 설정 및 아이디어 구상 할당 목록을 레퍼런스 참조에 의존하지 않고 작성하기 위해서는 반드시 배열이 역할을 대신해야 합니다.
원본 할당 목록에 노드는 힙 영역이라고 하는 메모리 전체 범위에서 원하는 구간에 속합니다.힙존 전체를 하나의 배열로 보고 각각의 노드가 배열의 index를 참조한다고 생각을 해보겠습니다.
이를 보다 압축된 배열 공간으로 이끌게 되면 레퍼런스가 사라질 것입니다.즉, 힙 전체에 흩어져 있는 노드를 하나의 배열 공간에 극도로 높은 밀도로 압축시키자는 아이디어입니다.
이와 같이 배열에 노드를 고밀도로 압축시키면 데이터 접근 성능이 향상될 수 있습니다.지역성에 의해 친밀한 주변 데이터를 캐싱하기 위해서입니다.
하지만 배열 공간을 만드는 것에는 사소한 단점이 존재합니다.Item(노드)이 remove되고 나면 그 공간은 잉여공간으로 남는다는 것입니다.
일반 List의 경우 데이터가 연속적으로 저장되어 있어야 하기 때문에 잉여공간이 생길 경우 배열원소의 압축을 진행합니다.그래서 List의 Remove At 성능이 좋지 않은 편입니다.
이러한 문제를 해결하기 위해서 각각의 잉여공간을 단순 연결 목록으로 가상 구현하고 잉여공간 단순 연결 목록의 head를 가리키는 변수를 추가합니다.이것이 「가상 실장」인 이유는 원형 리스트에서 실장되는 Array 안에서 단순한 접속 리스트를 실장하기 때문입니다.즉, 원형 리스트로 작성된 Array에서 단방향으로 참조하는 여유공간 연결 리스트입니다.
특수한 조건에 맞도록 원형 연결 목록 안에 단순 연결 목록을 안는 형태가 됩니다.
구상된 아이디어를 바탕으로 실제 구현하는 데 필요한 최소한의 변수들을 정리하면 다음과 같습니다.동작이 특별한 접속 목록이 작동하는 모습을 단계적으로 그려봤습니다.
- 초기화
2. 데이터 최초 삽입
3. 노드 제거
4. 데이터삽입 (노드제거 후)
5. (헤드가 가르치던) 노드 제거
6. 모든 노드가 제거되었을 경우 (clear)위의 그림과 같이 동작하도록 구현해 주세요.
연결목록을 표현하는 이미지와 비슷한데, 차이점은 각각의 노드가 힙존 어딘가에 위치하는 것이 아니라 배열에 고밀도로 압축되어 저장된다는 것입니다.
상기의 화상으로부터 가시성 향상을 위해서 DATA(노드) 사이에 거리를 두고 있습니다만, 실제는 배열이기 때문에, 노드간에는 약간의 잉여 공간도 없습니다.
구현 및 사용** SuperComic Lib.Collections 프로젝트에 실험적으로 추가되었습니다. **의 사용법은 Linked List와 동일합니다.
위의 코드를 참고하면 노드간의 참조가 없는 것을 확인할 수 있습니다.유일하게 Array로 참조되어 있습니다.
아이템 수(노드의 수)가 증가함에 따라 레퍼런스 수가 3배씩 증가하는 Linked List 에 비해 구현된 할당 목록은 레퍼런스가 항상 하나로 유지되기 때문에 가볍습니다.
구현된 C# 소스 코드는 나의 Githubrepo에서 확인하실 수 있습니다.디렉토리 위치: 0 SuperComicLibs/developing/3 SuperComicLib.Collections/src/Linked/주요 SuperComicLib를 모습니다. Contribute to ekfvoddl 3536 / 0 SuperComicLibs development by creating an account on GitHub.github.com