링크 된 목록의 간단한 순서

Question

주문 시퀀스에 의한 정렬로 인해 링크 된 목록과 실질적으로 동일한 배열을 만들 수있는 순서 시퀀스 (정수 특성)가있는 이중 연결 목록을 만들려고합니다.

given: a <-> b <-> c 

a.index > b.index 
b.index > c.index 

이 색인은 효율적으로 임의의 수의 삽입을 처리해야합니다.

이것을 수행하는 알고리즘이 있습니까? 목록이 커지고 인덱스 시퀀스가 ​​압축 된 경우 문제가 발생합니다. 이 상황에서 목록은 빈 공간을 다시 찾기 위해 스캔되어야합니다. 나는 이것이 어떻게 성취되어야하는지 잘 모르겠습니다. 이상적으로 자동 차용 일종의 자동 차용이 빠르거나 드물기 때문입니다.

모든 왼쪽 또는 오른쪽 indecies를 1로 변경하여 삽입 할 공간을 확보하는 간단한 해결책은 O (n)입니다.

대부분의 구현에서 숫자가 0에 가까워 질수록 부동 소수점의 신뢰도가 떨어지는 경향이 있으므로 정수를 사용하는 것을 선호합니다.

Answer 1

이것은 내가 가장 좋아하는 문제 중 하나입니다. 문헌에서 "온라인 목록 라벨링"또는 "목록 라벨링"이라고 불립니다. 여기에 위키 피 디아에서 조금 있습니다 : https://en.wikipedia.org/wiki/Order-maintenance_problem#List-labeling

아마 가장 간단한 알고리즘은 여기에 처음으로 : https://www.cs.cmu.edu/~sleator/papers/maintaining-order.pdf입니다.

amortized O (log N) 시간에 삽입을 처리하고 N 개 항목을 관리하려면 N^2 개를 수용 할만큼 충분히 큰 정수를 사용해야합니다. 64 비트 정수는 거의 모든 실제적인 경우에 충분합니다.

Answer 2

내가 감은 것은 롤 자체 솔루션이었습니다. 알고리즘이 다음 노드를 삽입하기 전에 메모리에 전체 목록을 갖고 싶어했기 때문입니다. 그리고 그것은 좋지 않습니다.

제 아이디어는 알고리즘에 대한 아이디어 중 일부를 빌리는 것입니다. 내가 한 일은 ID를 int로 만들고 정렬 명령을 길게 만드는 것이 었습니다. 그런 다음 알고리즘은 게으르며 어디서나 사용할 수 있습니다. 어딘가에 약간의 작은 덩어리에서 공간이 부족하면 덩어리에서 위아래로 스캔을 시작하고 n 개의 항목이 스캔되면 그들 사이에 n^2 패딩을 공유해야하는 균등 한 간격을 설정하려고 시도합니다.

이론적으로 이것은 목록이 완벽하게 채워질 것이며, ID가 int이고 정렬 순서가 길기 때문에 n^2 패딩을 수행 할 수없는 시나리오는 결코 존재하지 않는다는 것을 의미합니다 . 작동 수에 대한 상한선을 말할 수는 없지만 1/다항식 주파수에서 다항식 작업을 수행하면 좋을 것입니다.