Array와 Dynamic Array, Linked List

선형 자료구조인 배열(Array)와 연결 리스트(Linked List)는 데이터를 나열한다. 그러나 동일한 operation에 대해 내부적으로 수행되는 작업이 달라, 시간 복잡도 면에서 서로 반대의 장단점들이 존재한다.

Array(배열)

데이터를 논리적 순서에 따라 순차적으로 다룬다. 일반적으로 (메모리에서의)물리적 주소 또한 순차적이다. 또한 인덱스를 가지고 있어서, 무작위 접근(random access)이 매우 빠르다. 그러나 크기가 고정되어 있기 때문에 배열의 크기를 늘리는 연산이 필요한 경우가 있고, 데이터 삽입/삭제 시 그 다음 인덱스부터의 데이터를 모두 한 칸씩 뒤로 밀거나 앞으로 당겨오는 연산을 해야 하기 때문에 데이터 삽입과 삭제 시 느린 속도를 보인다.

Dynamic Array(동적 배열)

동적 배열은 크기가 고정되지 않은 배열을 의미하며, 일반 배열의 '크기가 고정되어 있다'는 문제를 제거한다. C++ STL의 vector, Python의 list 등이 동적 배열의 구현체다. 배열의 번외품처럼 보이지만, 꽤 많은 곳에서 유용하게 사용된다.

Linked List

데이터를 주소의 참조에 따라 순차적으로 다룬다. 배열에서 요소 하나가 값 + 인덱스로 이루어져 있다면, Linked List에서 요소 하나는 값 + next의 주소, 또는 값 + prev의 주소 + next의 주소로 이루어진다. 전자를 단순 연결리스트, 후자를 이중, 또는 양방향(doubly) 연결리스트라고 부른다. Linked List는 배열과 다르게 무작위 접근이 불가능하기 때문에, 특정 노드에 대한 임의 접근은 링크를 계속해서 따라가야 가능하기 때문에 배열보다 느리고, 반대로 데이터를 삽입/삭제할 때에는 앞/뒤 노드의 주소만 끼워넣을 노드의 주소로 바꿔주면 되기 때문에 배열보다 빠르다.