[arrays] 배열 / 배열 목록에서 링크 된 목록을 사용하는시기

Program / 글쓴이

나는 많은 목록과 배열을 사용하지만 배열 목록을 연결된 목록보다 쉽게 ​​사용할 수는없는 시나리오를 아직 보지 못했습니다. 나는 누군가가 링크 된 목록이 눈에 띄게 더 나은 예를 줄 수 있기를 바랐습니다.

답변

다음과 같은 경우 연결된 목록이 배열보다 선호됩니다.

  1. 목록에서 일정한 시간에 삽입 / 삭제해야합니다 (예 : 시간 예측 성이 절대적으로 중요한 실시간 컴퓨팅에서)

  2. 목록에 몇 개의 항목이 있는지 알 수 없습니다. 배열을 사용하면 배열이 너무 커지면 메모리를 다시 선언하고 복사해야 할 수 있습니다

  3. 당신은 어떤 요소에 무작위로 액세스 할 필요가 없습니다

  4. 목록 중간에 항목을 삽입 할 수 있기를 원합니다 (예 : 우선 순위 대기열)

다음과 같은 경우 배열이 바람직합니다.

  1. 요소에 인덱스 / 랜덤 액세스가 필요합니다

  2. 어레이에 올바른 양의 메모리를 할당 할 수 있도록 어레이의 요소 수를 미리 알고 있습니다.

  3. 모든 요소를 ​​순서대로 반복 할 때 속도가 필요합니다. 배열에서 포인터 수학을 사용하여 각 요소에 액세스 할 수 있지만 링크 된 목록의 각 요소에 대한 포인터를 기반으로 노드를 찾아야하므로 페이지 오류가 발생하여 성능이 저하 될 수 있습니다.

  4. 기억은 관심사입니다. 채워진 배열은 연결된 목록보다 적은 메모리를 사용합니다. 배열의 각 요소는 단지 데이터입니다. 각 링크 된 목록 노드에는 데이터와 링크 된 목록의 다른 요소에 대한 하나 이상의 포인터가 필요합니다.

.Net의 배열 목록과 같은 배열 목록은 배열의 이점을 제공하지만 동적으로 자원을 할당하여 목록 크기에 대해 너무 걱정할 필요가 없으며 아무 노력이나 노력없이 인덱스에서 항목을 삭제할 수 있습니다 셔플 링 요소. 성능 측면에서 배열 목록은 원시 배열보다 느립니다.

답변

배열에는 O (1) 임의 액세스 권한이 있지만 항목을 추가하거나 제거하는 데 실제로 비용이 많이 듭니다.

연결된 목록은 항목을 추가하거나 제거하고 반복하는 데 실제로 저렴하지만 임의 액세스는 O (n)입니다.

답변

Algorithm           ArrayList   LinkedList
seek front            O(1)         O(1)
seek back             O(1)         O(1)
seek to index         O(1)         O(N)
insert at front       O(N)         O(1)
insert at back        O(1)         O(1)
insert after an item  O(N)         O(1)

ArrayLists는 한 번만 읽을 수있는 많은 또는 어 펜더에는 좋지만 추가 또는 제거는 앞면 또는 가운데에는 좋지 않습니다.

답변

다른 답변에 추가하기 위해 대부분의 배열 목록 구현은 목록 끝에 추가 용량을 예약하여 O (1) 시간 내에 목록 끝에 새 요소를 추가 할 수 있습니다. 배열 목록의 용량이 초과되면 더 큰 새 배열이 내부적으로 할당되고 모든 이전 요소가 복사됩니다. 일반적으로 새 배열은 기존 배열의 두 배 크기입니다. 이것은 평균적으로 으로 이러한 구현에서 배열 목록의 끝에 새로운 요소를 추가하는 것이 O (1) 연산 . 따라서 사전에 요소 수를 모르더라도 마지막에 요소를 추가하는 한 배열 목록은 요소를 추가하기 위해 연결된 목록보다 여전히 빠를 수 있습니다. 분명히 배열 목록의 임의의 위치에 새 요소를 삽입하는 것은 여전히 ​​O (n) 작업입니다.

액세스가 순차적 인 경우에도 배열 목록의 요소에 액세스하는 것이 연결된 목록보다 빠릅니다. 배열 요소가 연속 메모리에 저장되어 쉽게 캐시 될 수 있기 때문입니다. 연결된 목록 노드는 여러 다른 페이지에 분산 될 수 있습니다.

임의의 위치에 항목을 삽입하거나 삭제할 것임을 알고있는 경우에는 링크 된 목록 만 사용하는 것이 좋습니다. 배열 목록은 다른 모든 것보다 빠릅니다.

답변

중간에 항목을 삽입해야하고 배열의 크기를 조정하고 주변을 이동하지 않으려는 경우 목록의 장점이 나타납니다.

일반적으로 그렇지 않다는 것이 맞습니다. 나는 그런 몇 가지 매우 구체적인 사례를 보았지만 너무 많지는 않았습니다.

답변

그것은 모두 반복하는 동안 어떤 유형의 작업을 수행 하느냐에 달려 있으며, 모든 데이터 구조는 시간과 메모리 사이에서 균형을 유지하며 필요에 따라 올바른 DS를 선택해야합니다. 따라서 LinkedList가 배열보다 빠르거나 그 반대 인 경우도 있습니다. 데이터 구조에 대한 세 가지 기본 조작을 고려하십시오.

  • 수색

배열은 인덱스 기반 데이터 구조이므로 array.get (index)는 O (1) 시간이 걸리며 linkedlist는 인덱스 DS가 아니므로 index <= n, n은 링크 된 목록의 크기입니다. 따라서 요소에 임의로 액세스 할 때 배열이 링크 된 목록보다 빠릅니다.

Q.이 뒤에 아름다움은 무엇입니까?

배열은 연속적인 메모리 블록이므로, 처음 액세스 할 때 캐시에 큰 청크가로드 될 것이므로 배열의 나머지 요소에 액세스하는 것이 상대적으로 빠릅니다. 캐시 누락은 캐시에있는 작업을 나타내므로 메모리에 비해 훨씬 빠르게 실행됩니다. 기본적으로 배열에서 순차적 요소 액세스가 캐시에있을 가능성을 최대화합니다. 링크 된 목록이 반드시 연속적인 메모리 블록에있는 것은 아니지만 목록에 순차적으로 나타나는 항목이 실제로 메모리의 서로 가까이에 정렬되어 있다는 보장은 없습니다.

  • 삽입

배열과 비교하여 LinkedList (Java에서) 삽입이 O (1) 연산이므로 LinkedList에서 쉽고 빠릅니다. 배열이 가득 찬 경우를 고려하십시오. 배열이 가득 차면 배열을 가득 채우면 내용을 새 배열에 복사해야합니다. 최악의 경우 O (n)의 ArrayList에 요소를 배치하는 반면, ArrayList는 배열의 끝을 제외한 다른 위치에 무언가를 삽입하면 색인을 업데이트해야합니다. 연결 된 목록의 경우 크기를 조정할 필요가 없으므로 단지 포인터를 업데이트하십시오.

  • 삭제

삽입과 같이 작동하며 배열보다 LinkedList에서 더 좋습니다.

답변

이것들은 Collection에서 가장 일반적으로 사용되는 구현입니다.

배열 목록 :

  • 일반적으로 끝에 삽입 / 삭제 O (1) 최악의 경우 O (n)

  • 중간에 삽입 / 삭제 O (n)

  • 모든 위치를 검색 O (1)

연결 목록 :

  • 임의의 위치에 삽입 / 삭제 O (1) (요소에 대한 참조가있는 경우 참고)

  • 중간 O (n)에서 검색

  • 첫 번째 또는 마지막 요소 검색 O (1)

벡터 : 사용하지 마십시오. ArrayList와 유사하지만 모든 메소드가 동기화 된 이전 구현입니다. 멀티 스레딩 환경에서 공유 목록에 대한 올바른 접근 방식이 아닙니다.

해시 맵

O (1)의 키로 삽입 / 삭제 / 검색

TreeSet
삽입 / 삭제 / O (log N)에 포함


O (1)의 해시 셋 삽입 / 제거 / 포함 / 크기