배열이 빠른 무작위 접근을 지원하는데 왜 연결 리스트를 사용합니까?

연결 리스트는 노드에 대한 참조가 주어지면 다른 요소를 이동할 필요 없이 상수 시간에 삽입 또는 삭제를 허용하며, 이는 배열이 중간에서 할 수 없는 작업입니다. 시퀀스가 자주 변경되고 위치별 무작위 접근이 필요하지 않을 때 유용합니다.

크기 조정 시 모든 것을 복사한다면 배열 추가가 왜 상수 시간으로 간주됩니까?

용량이 일반적으로 두 배로 늘어나기 때문에 크기 조정은 드물게 발생하며, 따라서 n번의 추가에 걸친 총 복사 작업은 n에 비례합니다. 모든 추가에 걸쳐 분산되면 개별 크기 조정이 O(n)이더라도 추가당 상각된 상수 비용이 됩니다.

배열과 연결 리스트

배열과 연결 리스트는 요소의 정렬된 시퀀스를 저장하는 두 가지 기본적인 방법입니다. 배열은 연속된 메모리에 요소를 배치하여 상수 시간 인덱스 접근을 가능하게 하는 반면, 연결 리스트는 포인터를 통해 요소를 연결하여 삽입 및 삭제 비용이 저렴합니다.

PaperMind(으)로 주제 찾기곧 제공Find papers & topics

Tools & resources

슬라이드 다운로드

Learn & explore

동영상곧 제공

Definition

배열은 위치로 인덱싱되는 연속된 메모리 위치에 요소를 저장하여 상수 시간 무작위 접근을 허용합니다. 연결 리스트는 각 노드가 다음(그리고 이전) 노드에 대한 참조를 포함하는 별도의 노드에 요소를 저장하여 노드 참조가 주어지면 상수 시간 삽입 또는 제거를 허용합니다.

Scope

이 주제는 선형, 시퀀스 기반 구조와 그 위에 구축된 추상 데이터 유형(정적 및 동적 배열, 단일 및 이중 연결 리스트, 스택 및 큐 ADT)을 다룹니다. 접근, 삽입 및 삭제 비용을 비교하고, 동적 배열 크기 조정 및 상각 분석을 다루며, 캐시 지역성(cache locality)과 같은 메모리 레이아웃의 결과를 설명합니다. 해시 테이블 및 검색 트리에서 다루는 연관 및 계층 구조는 제외합니다.

Core questions

연속적인(배열) 저장 방식이 포인터로 연결된(리스트) 저장 방식보다 성능이 우수한 경우는 언제입니까?
동적 배열은 가끔 발생하는 크기 조정에도 불구하고 어떻게 상각된 상수 시간 추가를 달성합니까?
삽입, 삭제 및 접근에 대한 배열과 연결 리스트의 비용 상충 관계는 무엇입니까?
이러한 구조 위에 스택과 큐는 어떻게 구현됩니까?
메모리 레이아웃이 캐시 동작을 통해 실제 성능에 어떻게 영향을 미칩니까?

Key concepts

연속 메모리
인덱스 접근
동적 배열 크기 조정
단일 및 이중 연결 리스트
스택 (LIFO)
큐 (FIFO)
상각 비용
캐시 지역성

Key theories

무작위 접근 대 순차적 연결: 배열은 O(1) 인덱스 접근을 지원하지만 중간에 O(n) 삽입 또는 삭제가 발생할 수 있는 반면, 연결 리스트는 노드가 주어지면 O(1) 스플라이싱을 지원하지만 위치별 접근은 O(n)입니다. 올바른 선택은 작업 혼합에 따라 달라집니다.
동적 배열의 상각된 성장: 가득 찼을 때 용량을 두 배로 늘리는 동적 배열은 가끔 O(n) 복사를 수행하지만, 집계 또는 잠재적 방법을 통해 모든 작업 시퀀스에 걸쳐 추가당 O(1)로 상각됩니다.

Clinical relevance

배열과 리스트는 거의 모든 프로그램의 기반입니다. 동적 배열은 대부분의 언어에서 기본 리스트/벡터 유형을 구현하고, 큐는 스케줄링 및 너비 우선 탐색의 기반이 되며, 스택은 함수 호출 관리 및 표현식 평가의 기반이 됩니다. 배열 대 리스트의 장단점은 성능에 영향을 미치는 일상적인 실용적 설계 결정입니다.

History

배열은 최초의 프로그래밍 언어에 존재했던 가장 초기의 데이터 구조 중 하나이며, 연결 리스트는 1950년대 후반 기호 및 리스트 처리(특히 Newell, Shaw 및 Simon의 IPL과 이후 Lisp에서)를 위해 도입되었습니다. Knuth의 『컴퓨터 프로그래밍의 예술(The Art of Computer Programming)』에서의 체계적인 다룸은 이들의 정식 분석을 확립했습니다.

Key figures

Donald Knuth
Robert Sedgewick

Seminal works

knuth1997vol1
cormen2009

Frequently asked questions

배열이 빠른 무작위 접근을 지원하는데 왜 연결 리스트를 사용합니까?: 연결 리스트는 노드에 대한 참조가 주어지면 다른 요소를 이동할 필요 없이 상수 시간에 삽입 또는 삭제를 허용하며, 이는 배열이 중간에서 할 수 없는 작업입니다. 시퀀스가 자주 변경되고 위치별 무작위 접근이 필요하지 않을 때 유용합니다.
크기 조정 시 모든 것을 복사한다면 배열 추가가 왜 상수 시간으로 간주됩니까?: 용량이 일반적으로 두 배로 늘어나기 때문에 크기 조정은 드물게 발생하며, 따라서 n번의 추가에 걸친 총 복사 작업은 n에 비례합니다. 모든 추가에 걸쳐 분산되면 개별 크기 조정이 O(n)이더라도 추가당 상각된 상수 비용이 됩니다.