정의메모리의 불연속적인 위치에 각각의 데이터와 함께 다음 데이터의 주소를 저장하는 자료구조 연결 리스트에는 단순하게 하나의 노드에 데이터와 함께 다음 데이터의 주소만 포함하는 단일 연결 리스트, 다음 데이터의 주소와 이전 데이터의 주소까지 포함하는 이중 연결 리스트, 그리고 리스트 끝과 처음이 연결되어 있는 원형 연결 리스트가 있다. 특징임의의 위치에 있는 노드의 데이터를 확인/변경하는 데 O(N)의 시간이 걸린다처음 노드에서부터 확인/변경할 노드까지 순차적으로 접근해야 한다임의의 위치에 노드를 추가 / 제거하는 데 O(1)의 시간이 걸린다단, 임의의 위치에 대한 주소를 알고 있어야 한다 (해당 위치 주소를 모르면 처음 노드부터 O(N)의 시간으로 접근해야 함)단순히 노드가 가리키는 다음 주소(또는 이전..

정의메모리에 데이터들을 연속적으로 배치한 자료구조 특징임의의 위치에 있는 데이터를 확인/변경하는 데 O(1)의 시간이 걸린다배열 끝에 데이터를 추가 / 배열 끝의 데이터를 삭제하는 데 O(1)의 시간이 걸린다임의의 위치에 데이터를 추가 / 삭제하는 데 O(N)의 시간이 걸린다해당 위치 이후의 데이터들을 전부 한 칸씩 밀어내거나, 당겨와야 한다추가로 소모되는 메모리가 거의 없다캐시 적중률이 높다데이터들이 연속적으로 배치되어 있어 참조 지역성(공간적 지역성)을 잘 활용할 수 있다메모리에 연속적으로 배치해야 하기 때문에 할당에 제약이 있다