대부분의 경우 사람들이 연결 목록을 사용하려고 시도하는 것은 나에게 좋지 않은 (또는 매우 가난한) 선택처럼 보입니다. 연결된 목록이 데이터 구조의 좋은 선택인지 아닌지에 대한 상황을 탐색하는 것이 유용 할 수 있습니다.
이상적으로는 데이터 구조를 선택하는 데 사용할 기준과 특정 상황에서 가장 잘 작동 할 수있는 데이터 구조에 대한 답변이 설명됩니다.
편집 : 나는 숫자뿐만 아니라 답변의 질에 매우 감동했습니다. 나는 하나만 받아 들일 수 있지만 조금 더 나은 것이 없었다면 받아 들일 가치가 있었을 것이라고 말해야 할 두세 가지가 더 있습니다. 단 한 쌍 (특히 내가 받아들이기로 한)만이 연결 목록이 실질적인 이점을 제공하는 상황을 지적했습니다. 나는 Steve Jessop이 하나가 아니라 세 가지 다른 답변을 내놓은 것에 대해 일종의 명예로운 언급을 할 가치가 있다고 생각합니다. 물론 답변이 아닌 댓글로만 게시 되었음에도 불구하고 Neil의 블로그 항목도 읽을만한 가치가 있다고 생각합니다. 유익 할뿐만 아니라 재미도 있습니다.
답변
동시 데이터 구조에 유용 할 수 있습니다. (이제 아래에 비 동시 실제 사용 샘플이 있습니다 . @Neil 이 FORTRAN을 언급하지 않았다면 존재하지 않을 것 입니다. 😉
예를 들어 ConcurrentDictionary<TKey, TValue>.NET 4.0 RC에서는 연결 목록을 사용하여 해시 된 항목을 동일한 버킷에 연결합니다.
의 기본 데이터 구조 ConcurrentStack<T>도 링크 된 목록입니다.
ConcurrentStack<T>새로운 스레드 풀 의 기반 역할을하는 데이터 구조 중 하나입니다 (기본적으로 스택으로 구현 된 로컬 “큐”포함). (다른 주요지지 구조는 ConcurrentQueue<T>입니다.)
새로운 Thread Pool은 새로운 Task Parallel Library 의 작업 스케줄링을위한 기반을 제공합니다
.
따라서 그것들은 확실히 유용 할 수 있습니다. 연결 목록은 현재 적어도 하나의 훌륭한 신기술의 주요 지원 구조 중 하나입니다.
(단일 링크 된 목록은 주요 작업을 단일 CAS (+ 재시도) 로 수행 할 수 있기 때문에 이러한 경우에 잠금 없는 ( 잠금없는 것은 아님) 매력적인 선택이됩니다 . 최신 GC-d 환경에서) Java 및 .NET- ABA 문제 는 쉽게 피할 수 있습니다. 새로 생성 된 노드에 추가 한 항목을 랩핑하고 해당 노드를 재사용하지 마십시오. GC가 작업을 수행하도록합니다. ABA 문제에 대한 페이지는 잠금 구현도 제공합니다. 무료 스택-실제로 항목을 보유하는 (GC-ed) 노드가있는 .Net (& Java)에서 작동합니다.)
편집 : @Neil : 실제로 FORTRAN에 대해 언급 한 내용은 .NET에서 가장 많이 사용되고 남용되는 데이터 구조 인 일반 .NET generic에서 동일한 종류의 연결 목록을 찾을 수 있음을 상기시켜주었습니다 Dictionary<TKey, TValue>.
하나는 아니지만 많은 연결 목록이 배열에 저장됩니다.
- 삽입 / 삭제시 많은 작은 할당 (해제)을 피합니다.
- 배열이 순차적으로 채워지기 때문에 해시 테이블의 초기로드는 매우 빠릅니다 (CPU 캐시로 매우 잘 재생 됨).
- 체이닝 해시 테이블은 메모리 측면에서 비싸다는 것은 말할 것도없고이 “트릭”은 x64에서 “포인터 크기”를 절반으로 줄입니다.
기본적으로 많은 연결 목록이 배열에 저장됩니다. (사용 된 각 버킷에 대해 하나씩) 재사용 가능한 노드의 무료 목록은 그들 사이에 “결합”됩니다 (삭제가있는 경우). 배열은 시작 / 재해시시 할당되고 체인 노드는 그 안에 보관됩니다. 삭제를 따르는 자유 포인터 (배열에 대한 인덱스 )도 있습니다 . 😉 그래서-믿거 나 말거나-FORTRAN 기술은 여전히 살아 있습니다. (… 그리고 가장 일반적으로 사용되는 .NET 데이터 구조 중 하나보다 다른 곳은 없습니다 ;-).
답변
링크 된 목록은 임의의 (컴파일시 알 수없는) 길이의 목록에서 많은 삽입 및 제거를 수행해야하지만 너무 많이 검색하지 않아야 할 때 매우 유용합니다.
목록 분할 및 결합 (양방향 연결)은 매우 효율적입니다.
또한 연결 목록을 결합 할 수도 있습니다. 예를 들어 트리 구조는 수평 연결 목록 (형제)을 함께 연결하는 “수직”연결 목록 (상위 / 하위 관계)으로 구현 될 수 있습니다.
이러한 목적으로 배열 기반 목록을 사용하면 심각한 제한이 있습니다.
- 새 항목을 추가하면 어레이를 재 할당해야합니다 (또는 향후 확장을 허용하고 재 할당 횟수를 줄이는 데 필요한 것보다 더 많은 공간을 할당해야 함).
- 항목을 제거하면 공간이 낭비되거나 재 할당이 필요합니다.
- 끝을 제외한 모든 곳에 항목을 삽입하는 것은 많은 데이터를 한 위치 위로 복사 (재 할당 및)하는 것을 포함합니다.
답변
연결된 목록은 매우 유연합니다. 하나의 포인터를 수정하면 배열 목록에서 동일한 작업이 매우 비효율적 인 경우 대규모 변경을 수행 할 수 있습니다.
답변
배열은 연결된 목록이 일반적으로 비교되는 데이터 구조입니다.
일반적으로 연결된 목록은 목록 자체를 많이 수정해야 할 때 유용하지만 배열은 직접 요소 액세스의 목록보다 성능이 좋습니다.
다음은 상대 작업 비용 (n = 목록 / 배열 길이)과 비교하여 목록 및 배열에서 수행 할 수있는 작업 목록입니다.
- 요소 추가 :
- 목록에서는 새 요소와 리디렉션 포인터에 메모리를 할당하기 만하면됩니다. O (1)
- 어레이에서는 어레이를 재배치해야합니다. 의 위에)
- 요소 제거
- 목록에서 포인터를 리디렉션합니다. O (1).
- 배열에서 제거 할 요소가 배열의 첫 번째 또는 마지막 요소가 아닌 경우 배열을 재배치하는 데 O (n) 시간을 소비합니다. 그렇지 않으면 단순히 포인터를 배열의 시작으로 재배치하거나 배열 길이를 줄일 수 있습니다.
- 알려진 위치에서 요소 가져 오기 :
- 목록에서 첫 번째 요소에서 특정 위치의 요소로 목록을 걸어야합니다. 최악의 경우 : O (n)
- 배열에서 요소에 즉시 액세스 할 수 있습니다. O (1)
이것은이 두 가지 인기 있고 기본적인 데이터 구조에 대한 매우 낮은 수준의 비교이며 목록 자체를 많이 수정해야하는 상황에서 목록이 더 잘 수행된다는 것을 알 수 있습니다 (요소 제거 또는 추가). 반면에 배열의 요소에 직접 액세스해야하는 경우 배열이 목록보다 성능이 좋습니다.
메모리 할당의 관점에서 볼 때 모든 요소를 나란히 둘 필요가 없기 때문에 목록이 더 좋습니다. 반면에 다음 (또는 이전) 요소에 대한 포인터를 저장하는 데는 (약간) 오버 헤드가 있습니다.
이러한 차이점을 아는 것은 개발자가 구현에서 목록과 배열 중에서 선택하는 데 중요합니다.
이것은 목록과 배열의 비교입니다. 여기에보고 된 문제에 대한 좋은 해결책이 있습니다 (예 : SkipLists, Dynamic Arrays 등). 이 답변에서는 모든 프로그래머가 알아야 할 기본 데이터 구조를 고려했습니다.
답변
단일 연결 목록은 셀 할당 자 또는 개체 풀의 사용 가능한 목록에 적합합니다.
- 스택 만 필요하므로 단일 연결 목록이면 충분합니다.
- 모든 것이 이미 노드로 나뉩니다. 셀이 포인터를 포함 할만큼 충분히 큰 경우 침입 목록 노드에 대한 할당 오버 헤드가 없습니다.
- 벡터 또는 데크는 블록 당 포인터 하나의 오버 헤드를 부과합니다. 이는 처음 힙을 만들 때 모든 셀이 무료이므로 선행 비용이 발생한다는 점을 고려할 때 중요합니다. 최악의 경우 셀당 메모리 요구 사항이 두 배가됩니다.
답변
이중 연결 목록은 요소 (Java의 LinkedHashMap)에 대한 순서도 정의하는 해시 맵의 순서를 정의하는 데 적합합니다.
- 관련 벡터 또는 데크보다 더 많은 메모리 오버 헤드 (1 대신 포인터 2 개), 삽입 / 제거 성능이 향상됩니다.
- 어쨌든 해시 항목을위한 노드가 필요하므로 할당 오버 헤드가 없습니다.
- 참조 위치는 벡터 또는 포인터 데크와 비교할 때 추가 문제가 아닙니다. 각 객체를 어느 쪽이든 메모리로 가져와야하기 때문입니다.
물론 LRU 캐시가 더 정교하고 조정 가능한 것에 비해 처음에는 좋은 아이디어인지에 대해 논쟁 할 수 있지만, 하나를 갖게된다면 꽤 괜찮은 구현입니다. 모든 읽기 액세스에서 벡터 또는 deque에서 중간에서 삭제 및 끝에서 추가를 수행하고 싶지는 않지만 일반적으로 노드를 꼬리로 이동하는 것이 좋습니다.
답변
연결된 목록은 데이터가 저장되는 위치를 제어 할 수 없지만 어떻게 든 한 개체에서 다음 개체로 이동해야하는 경우 자연스러운 선택 중 하나입니다.
예를 들어 C ++에서 메모리 추적을 구현할 때 (새로 만들기 / 삭제 대체) 어떤 포인터가 해제되었는지 추적하는 제어 데이터 구조가 필요하며,이를 완전히 구현해야합니다. 대안은 각 데이터 청크의 시작 부분에 연결 목록을 할당하고 추가하는 것입니다.
delete가 호출 될 때 목록에서 자신이 어디에 있는지 항상 즉시 알기 때문에 O (1)의 메모리를 쉽게 포기할 수 있습니다. 또한 방금 malloc 된 새 청크를 추가하는 것은 O (1)에 있습니다. 이 경우 목록을 걷는 것은 거의 필요하지 않으므로 O (n) 비용은 여기서 문제가되지 않습니다 (구조물을 걷는 것은 O (n)입니다).
