O (1) 삽입 및 삭제를 사용하는 이중 연결 목록의 컴팩트 다중 배열 구현

Question

CLRS (Cormen Intro to Algorithms 3ed)의 연습 문제 (10.3-4)에 대해 혼란 스럽습니다. 내 구현 O (1) 시간에 삭제 + 할당 취소를 수행 할 수있는 것 같아요, 두 솔루션은 내가 온라인으로 찾은이 작업에 대한 O (n) 시간이 필요하고 누가 옳은지 알고 싶어요. 여기

은 운동의 텍스트이다 :

예를 들어, 사용하는 스토리지에 이중 연결리스트 성형체의 모든 요소를 ​​유지하는 것이 종종 바람직하다 다중 배열 표현에서 제 m 인덱스 위치 . 페이징 된 가상 메모리 컴퓨팅 환경의 경우입니다. OBOCECT 및 FREE OBJECT 프로 시저를 구현하는 방법을 설명하여 표현이 컴팩트 해지도록하십시오. 목록 자체 외부의 연결된 목록 요소에 대한 포인터가 없다고 가정합니다. (힌트 : 스택 어레이 구현을 사용한다.)

을 "다중 배열 표현"으로, 그들은 다음 사용 이전 및 키 배열 연결리스트 구현 언급하는 인덱스가 작용하여 다음 및 이전을 가리키는 멤버가있는 객체가 아니라 배열에 저장된 포인터로 사용됩니다. 이 특정 구현은 CLRS 10.3 절의 텍스트에서 논의되었지만,이 특정 연습은 요소를 "컴팩트"하게 만드는 추가 조건을 단순히 부과하는 것으로 보이거나 내가 이해하는 것처럼 배열의 시작 부분에 채워진 것처럼 보입니다. "비활성"요소가있는 간격이나 구멍이 없습니다.

a previous thread on the same exercise here이 있었지만 그 스레드에서 내가 뭘 알고 싶은지 알 수 없었습니다.

온라인에서 찾은 두 가지 해결책은 first one here과 second one here, on page 6 of the pdf입니다. 두 솔루션 모두 O (n) 시간을 들여 간격을 메우기 위해 간격 후에 모든 요소를 ​​하나씩 이동한다고합니다. 대신 내 자신의 구현은 단순히 배열의 마지막 "유효"요소를 취하여 요소를 삭제할 때만 발생하는 틈새를 채우기 위해이를 사용합니다. 이것은 "compactness"속성을 유지합니다. 물론, 적절한 이전 및 다음 "포인터"가 업데이트되며 이는 O (1) 시간입니다. 또한 Sec. 간결함을 필요로하지 않는 책의 10.3에는 두 번째 연결된 목록의 시작 부분을 가리키는 "free"라는 변수가 있었으며이 요소에는 쓸 수있는 "유효하지 않은"요소가 모두 있습니다. 내 구현의 경우 삽입이 가능한 가장 빠른 시점에 완료되어야하므로 유효하지 않은 배열 슬롯이라면, 단순히 변수 "free"가 스택의 변수 "top"과 더 비슷하게 작동하게했을뿐입니다. 이것은 왜 그렇게 뚜렷한 것처럼 보였으므로 두 솔루션 모두 O (n)의 "gap 이후의 모든 것을 이동"방법을 요구했는지 확신 할 수 없습니다. 그럼 어느 것이지?

다음은 C 구현입니다. 내가 아는 한 모든 것은 작동하며 O (1) 시간이 걸립니다.

typedef struct { 
    int *key, *prev, *next, head, free, size; 
} List; 

const int nil = -1; 

List *new_list(size_t size){ 
    List *l = malloc(sizeof(List)); 
    l->key = malloc(size*sizeof(int)); 
    l->prev = malloc(size*sizeof(int)); 
    l->next = malloc(size*sizeof(int)); 
    l->head = nil; 
    l->free = 0; 
    l->size = size; 
    return l; 
} 

void destroy_list(List *l){ 
    free(l->key); 
    free(l->prev); 
    free(l->next); 
    free(l); 
} 

int allocate_object(List *l){ 
    if(l->free == l->size){ 
     printf("list overflow\n"); 
     exit(1); 
    } 
    int i = l->free; 
    l->free++; 
    return i; 
} 

void insert(List *l, int k){ 
    int i = allocate_object(l); 
    l->key[i] = k; 
    l->next[i] = l->head; 
    if(l->head != nil){ 
     l->prev[l->head] = i; 
    } 
    l->prev[i] = nil; 
    l->head = i; 
} 

void free_object(List *l, int i){ 
    if(i != l->free-1){ 
     l->next[i] = l->next[l->free-1]; 
     l->prev[i] = l->prev[l->free-1]; 
     l->key[i] = l->key[l->free-1]; 
     if(l->head == l->free-1){ 
      l->head = i; 
     }else{ 
      l->next[l->prev[l->free-1]] = i; 
     } 
     if(l->next[l->free-1] != nil){ 
      l->prev[l->next[l->free-1]] = i; 
     } 
    } 
    l->free--; 
} 

void delete(List *l, int i){ 
    if(l->prev[i] != nil){ 
     l->next[l->prev[i]] = l->next[i]; 
    }else{ 
     l->head = l->next[i]; 
    } 
    if(l->next[i] != nil){ 
     l->prev[l->next[i]] = l->prev[i]; 
    } 
    free_object(l, i); 
} 

Answer 1

올바른 방법입니다.

O (n) "shift-everything-down"솔루션은 문제의 사양을 충족한다는 점에서 정확하지만 사용자의 접근 방식이 런타임 관점에서 바람직합니다.