Array, List, LinkedList

Array

• 인덱스(index)를 통해 데이터를 찾는 것이 가능한 자료구조

• 장점

  • 데이터 탐색 속도가 빠르다. 인덱스를 이용하므로 O(1)

• 단점

  • 크기가 고정적이다.

  • 삽입/삭제 속도가 느리다. 삽입/삭제 위치 이후의 값들을 모두 밀거나 당겨야 하기 때문

List

• Array의 크기 고정 문제를 해결하기 위해 등장한 자료구조

• Array와 마찬가지로 인덱스 기반으로 동작한다.

• Array와 달리 크기가 고정되어 있지 않다.

LinkedList

• 데이터를 담은 공간, 다음 노드의 주소를 담은 공간으로 구성되는 노드를 갖는다.

• 장점

  • 크기가 고정적이지 않다.

  • 삽입/삭제에 용이하다. 연결만 변경해주면 앞/뒤/중간 어디든 데이터를 쉽게 집어넣고 뺄 수 있다.

• 단점

  • 탐색 속도가 O(N)이다. 앞 노드부터 링크를 타고 가며 이동해야 하기 때문이다.