나는이 기사를 가로 질러왔다 : Should you ever use Linked List. 그것은 사용 가능한 메모리 및 RAM 구조의 기술적 진보를 감안할 때 배열을 사용하면 링크 된 목록보다 더 낫다고 말합니다.링크드 목록은 아직 관련이 있습니까?
또한 오래된 질문 When to use a linked list over an array/array list?
기사의 인수가 정말 잡고 목록이 쓸모 없게 또는/링크 한되어 있습니까있다 LinkedList의를 사용하는 것은 여전히 인수가있는 경우 배열보다 더 나은 것이 시나리오 일 것입니다 무슨 사실입니까?
넌센스 (예를 들어 어떤 지점에 대한 Explainations 도움이 될 것입니다). O (n)은 결코 일정 시간을 이길 수 없습니다. 저장된 반복자를 사용하여 삽입 작업을 수행하는 데 필요한 목록을 사용하면 연결된 목록이 사용됩니다. 그것들은 기본적인 구조이고 사라지지 않을 것입니다.
나는 다른 방법으로 논점을 돌리고 싶다 : 요즘 링크드리스트는 더 받아 들여진다. 386에서는 성능에주의를 기울여야하지만 지금은 Python으로 프로그램을 작성하고 속도를 높이기 위해 노력합니다. VM을 사용하는 언어로 작성된 (또는 해석 된) 코드의 양으로부터 많은 사람들이 데이터 구조 선택시 캐시 실패에 대해 걱정할 수준이 아니라고 생각합니다.
우리는 너무 자주 우리의 데이터 구조를 구현에 필요한 될 수있는 몇 가지 추가 지침에 대해 걱정할 필요가 없습니다, 지금은 빠른 CPU를 가지고있다. 우리는 우리가 가진 용도를보고, 우리가 가지고있는 요구 사항을 연구하고, 점근 적 성능을 토대로 구조를 고를 수 있습니다. 이것은 또한 코드를보다 관리하기 쉽게 만든다. 6 개월 후에 n = 100 목록이 빠르다는 것을 알게되면 코드를 변경할 필요가 없다. 프로파일 링은 힘든 작업이므로 우리는 CPU 추측의 날에 벡터에서 추측하기보다는 원하는 알고리즘 속성으로 구조를 선택하는 것이 매우 편안해야합니다.
선형 시간 복잡성을 가진 어떤 것들은 n의 많은 흥미로운 값에 대해 일정한 시간 복잡성으로 몇 가지를 이겼습니다. 또한 배열은 연결된 목록 선형 시간을 취하는 O (1)의 일부 연산을 지원하고 다른 배열은 점근 적으로 두 경우 모두 동일하다는 점에 유의하십시오. 한정된 삽입 시간에 관해서 : 내가들은 바에 따르면, 당신은 모든 것의 크기를 묶어 놓은 다음 그것에 충분한 메모리를 미리 할당합니다. 빠른 실시간 동적 메모리 할당은 매우 어렵습니다. 그리고 캐시 효율성에 대해 걱정하는 사람들은 어쨌든 (성능에 민감한 코드를 위해) 통역사를 사용하지 않습니다 ... – delnan
... "알고리즘 적으로 더 좋음"(깔끔한 코드/의사 코드를 나타냄)은 주관적이고 문제에 크게 의존합니다. 그것은 연결된 목록에 자리가 없다는 것을 말하는 것이 아니라 확실히 그렇습니다. 나는 그 진리를 파는 방법에 불만이 있습니다. 그들이 말했듯이, 메시지를 쏘지 마십시오 ;-) – delnan
@delnan, OK 그것은 약간의 논쟁 거리였습니다. 나는 이제 그것을 중립으로 만들었습니다. 나는 당신의 요점에 동의합니다. "algorithmicly nicer"는 객관적으로 빠른 성능을 제공한다는 것을 의미합니다 (예 : 프로파일 링 기본값으로 확장되는 코드를 작성하는 것은 그 자체로 미적 임). –
기술 발전에도 불구하고 어레이의 삽입/제거가 여전히 일정 시간 내에 수행 될 수 없습니다. 그래서 아니야. –
예, 인수가 유지됩니다. 그러나 연결된 목록에는 여전히 용도가 있습니다. – Joni
리눅스 커널은 링크드리스트 **를 광범위하게 ** 사용하며, 다른 많은 소프트웨어도 그렇습니다. 그래, 맞아. –