왜 누군가가 배열을 통해 연결된 목록을 사용하고 싶습니까?
연결된리스트를 코딩하는 것은 의심 할 여지없이 배열을 사용하는 것보다 약간 더 많은 작업이며 추가 노력이 필요한 이유가 무엇인지 궁금 할 것입니다.
링크 된 목록에서 새 요소를 삽입하는 것이 쉽지는 않지만 배열의 주요 작업입니다. 연결된 목록을 사용하여 데이터 세트를 저장하는 것과 비교하여 배열에 저장하는 것의 다른 장점이 있습니까?
이 질문의 중복없는 이 질문 이 질문에 일반 데이터 구조와 관련되는 동안 다른 문제는 특정 Java 클래스에 대해 구체적으로 요구하고 있기 때문이다.
답변
- 서로 다른 크기의 데이터를 연결된 목록에 저장하는 것이 더 쉽습니다. 배열은 모든 요소가 정확히 같은 크기라고 가정합니다.
- 앞에서 언급했듯이 연결된 목록이 유기적으로 성장하기가 더 쉽습니다. 어레이의 크기를 미리 알고 있거나 확장이 필요할 때 다시 만들어야합니다.
- 연결된 목록을 섞는 것은 무엇을 가리키는 지 변경하는 문제입니다. 배열 섞기가 더 복잡하거나 메모리가 더 많이 걸립니다.
- 반복이 “foreach”컨텍스트에서 발생하는 한 반복 성능을 잃지 않습니다.
답변
또 다른 좋은 이유는 링크 된 목록이 효율적인 멀티 스레드 구현에 적합하다는 것입니다. 그 이유는 변경 사항이 로컬 인 경향이 있기 때문에 데이터 구조의 현지화 된 부분에서 삽입 및 제거를위한 포인터에만 영향을 미치기 때문입니다. 따라서 동일한 링크 목록에서 많은 스레드가 작동하도록 할 수 있습니다. 또한 CAS 유형 작업을 사용하여 잠금없는 버전을 만들고 무거운 잠금을 완전히 피할 수 있습니다.
연결된 목록을 사용하면 수정자가 발생하는 동안 반복자가 목록을 탐색 할 수도 있습니다. 수정 사항이 충돌하지 않는 낙관적 인 경우 반복자는 경합없이 계속할 수 있습니다.
배열을 사용하면 배열의 크기를 수정하는 모든 변경 사항이 배열의 많은 부분을 잠글 필요가 있으며 실제로 전체 배열에서 전역 잠금을 수행하지 않으면 수정 작업이 중단되지 않습니다.
답변
Wikipedia는 차이점에 대해 매우 좋은 섹션을 가지고 있습니다.
연결된 목록은 배열보다 몇 가지 장점이 있습니다. 요소는 무한대로 링크 된 목록에 삽입 될 수 있지만, 배열은 결국 채워지거나 크기를 조정해야합니다. 마찬가지로 많은 요소가 제거 된 어레이는 낭비로 비워 지거나 더 작아 져야합니다.
반면, 배열은 무작위 액세스를 허용하는 반면, 링크 된 목록은 요소에 대한 순차적 액세스 만 허용합니다. 실제로 연결된 단일 목록은 한 방향으로 만 순회 할 수 있습니다. 이로 인해 링크 목록은 힙 정렬과 같은 색인으로 요소를 빠르게 찾는 것이 유용한 응용 프로그램에 적합하지 않습니다. 참조 및 데이터 캐시의 지역성으로 인해 많은 시스템의 링크 된 목록보다 어레이에 대한 순차적 액세스가 빠릅니다. 연결된 목록은 캐시의 이점을 거의받지 않습니다.
연결된 목록의 또 다른 단점은 참조에 필요한 추가 저장소이며, 종종 문자 나 부울 값과 같은 작은 데이터 항목의 목록에는 실용적이지 않습니다. 또한 새로운 할당 요소마다 메모리를 별도로 할당하는 데 시간이 오래 걸리고 순진한 할당자가 낭비 될 수 있으며 일반적으로 메모리 풀을 사용하여 해결되는 문제입니다.
http://en.wikipedia.org/wiki/Linked_list
답변
나는 다른 것을 추가 할 것이다-목록은 순수한 기능을 할 수있다 데이터 구조 있다.
예를 들어, 동일한 끝 섹션을 공유하는 완전히 다른 목록을 가질 수 있습니다
a = (1 2 3 4, ....)
b = (4 3 2 1 1 2 3 4 ...)
c = (3 4 ...)
즉 :
b = 4 -> 3 -> 2 -> 1 -> a
c = a.next.next
데이터를 복사하지 않고 가리키는 되 a로 b및c .
그들이 불변 변수를 사용하여 함수형 언어에서 인기있는 이유입니다 – prepend와 tail작업은 원래의 데이터를 복사 할 필요없이 자유롭게 발생할 수 있습니다 – 당신은 불변 같은 데이터를 처리 할 때 매우 중요한 기능입니다.
답변
리스트의 중간에 삽입하는 것이 더 쉬울뿐 아니라 배열보다 링크 된리스트의 중간에서 삭제하는 것이 훨씬 쉽습니다.
그러나 솔직히, 나는 연결 목록을 사용한 적이 없다. 빠른 삽입 및 삭제가 필요할 때마다 빠른 조회도 필요했기 때문에 HashSet 또는 Dictionary로 이동했습니다.
답변
두 개의 연결된 목록 (특히 두 개의 이중 연결된 목록)을 병합하는 것이 두 배열을 병합하는 것보다 훨씬 빠릅니다 (병합이 파괴적이라고 가정). 전자는 O (1)을, 후자는 O (n)을 사용합니다.
편집 : 명확히하기 위해 병합 정렬이 아닌 정렬되지 않은 의미에서 “병합”을 의미했습니다. 아마도 “연결하는”것이 더 나은 단어 일 것입니다.
답변
ArrayList 및 LinkedList에 대해 널리 인정되지 않는 인수는 디버깅하는 동안 LinkedLists가 불편 하다는 것입니다 입니다. 유지 보수 개발자가 프로그램을 이해하는 데 소요되는 시간 (예 : 버그 찾기, 증가) 및 IMHO는 때때로 엔터프라이즈 응용 프로그램에서 메모리 향상의 성능 향상 또는 바이트 수의 나노초를 정당화하지 않습니다. 때로는 (물론 응용 프로그램 유형에 따라 다름) 몇 바이트를 낭비하는 것이 좋지만 유지 관리가 용이하거나 이해하기 쉬운 응용 프로그램이 있습니다.
예를 들어, Java 환경에서 Eclipse 디버거를 사용하면 ArrayList를 디버깅하면 매우 이해하기 쉬운 구조가 나타납니다.
arrayList ArrayList<String>
elementData Object[]
[0] Object "Foo"
[1] Object "Foo"
[2] Object "Foo"
[3] Object "Foo"
[4] Object "Foo"
...
반면에, LinkedList의 내용을보고 특정 객체를 찾는 것은 LinkedList 내부를 걸러내는 데 필요한인지 오버 헤드는 말할 것도없고 Expand-The-Tree 클릭 악몽이됩니다.
linkedList LinkedList<String>
header LinkedList$Entry<E>
element E
next LinkedList$Entry<E>
element E "Foo"
next LinkedList$Entry<E>
element E "Foo"
next LinkedList$Entry<E>
element E "Foo"
next LinkedList$Entry<E>
previous LinkedList$Entry<E>
...
previous LinkedList$Entry<E>
previous LinkedList$Entry<E>
previous LinkedList$Entry<E>
