배열 리스트랑 연결 리스트랑 약간 합친듯한 느낌인데 요소를 하나의 메모리 공간에 배치하고 요소간에 연결을 절대 주소가 아닌 상대 주소로 연결하는거임. 이러면 배열 리스트처럼 모든 요소가 같은 메모리 공간에 있게 되므로 노드 하나 생성하고 삭제할때 오버헤드 신경 쓸 필요가 없고(대신 충분히 많은 데이터를 받을 수 있도록 먼저 큰 크기의 메모리가 할당되어야 하겠지만) 중간에 있는 요소의 삽입 및 삭제 오버헤드가 기존 배열 리스트는 O(n)인데 이건 일정함. 이미 존재하는 자료구조일지도 모르겠는데 배열 리스트에서 다음 요소를 가리키는 상대적인 주소값이 추가로 들어간 정도?


장점은 배열 리스트의 순차 접근 속도와 비슷할정도로 빠르고 연결 리스트의 삽입 및 삭제 속도만큼 빠르다는 건데 단점은 미리 큰 크기의 메모리를 할당받아야 하고 알고리즘의 복잡도는 리스트치고는 과함, 임의 요소 접근? 당연히 안된다. 이건 연결 리스트가 공유하는 기본적인 특징들이기에 어쩔 수 없지만.


아직 이론상으로 가능하다는 것만 증명했고 테스트용 코드는 아직 짜는 중이긴 한데 일단 증명 자체는 간단함. 상대 주소 방식과 절대 주소 방식의 상호 변환이 가능하다는 것이 증명임. 


먼저 절대 주소 방식에서 상대 주소 방식으로 변환하려면 목적지 대상체의 주소값에 출발지 대상체의 주소값을 빼면 됨. 예를 들어 123이 4번지에 있고 456이 7번지에 있을때 456이 첫번째 요소라면 절대값으로 나타내면 4번지로 이동하면 되고 상대값으로 나타내면 7-4번지로 이동하면 됨. 반대의 경우라면 4-7이니까 음수가 되는데 전자는 3칸만큼 앞으로 이동하고 후자는 음수이므로 뒤로 이동해야함. 상대 주소 방식에서 절대 주소 방식으로 변환하는건 조금 설명이 어렵지만 결국 메모리는 절대 주소로만 접근이 가능하기 때문에 현재 위치에서 상대 주소를 더하면 끝이다.


이 리스트 요소 중간에 데이터를 삽입하려면 뒤쪽에 아직 요소가 배정되지 않은 공간을 찾고 그곳에 데이터를 기록한다. 그리고 주소값을 업데이트해주면 됨. 삭제는 훨씬 단순한데 삭제할 요소의 다음 요소의 위치를 얻은 후에 이전 요소가 가리키는 다음 요소의 위치를 업데이트 해줌. 삭제할 요소가 바로 메모리에서 지워지고 접근이 불가능하게 되는게 아니라 그대로 남아있지만 접근할 수 있는 경로가 사라졌기 때문에 사실상 삭제된 것과 비슷한 효과를 가진다. 이 과정에서 메모리 동적 할당은 일어나지 않아서 요소의 삽입과 삭제가 많을수록 일반적인 연결 리스트보다는 성능이 높을수도 있음. 단 어디까지나 동적 할당 비용만으로 계산한거라 메모리가 실제 물리 메모리에 어떻게 배치되는지는 알 수 없기도 하고(순차적으로 물리 메모리에 배치되지 않을수도 있기 때문에 캐시 히트의 정확도가 떨어진다고 판단했음. 더 자세한 내용 알면 보충 설명좀) 최악의 경우라면 메모리 파편화도 고려해야 하기 때문에 항상 연결 리스트보다 우수하다고 보기는 어렵다는게 내 주관적인 견해임. (다만 블록 단위로 메모리를 할당받기에 메모리 파편화는 극단적인 예시일뿐) 그리고 결정적으로 알고리즘이 복잡해짐.


설명이 너무 장황할 수도 있는데 10분정도로 짧게 쓸려했지만 점점 내용 추가하면서 복잡해진 거임.