[TIL] 자료구조 - 스택과 큐

배열에는 순서가 있어서 첫 부분을 제거하거나 추가하고자 한다면, 요소들을 하나씩 뒤로 옮겨야 하고 이 시간 복잡도는 O(n)이 된다. 이는 스택과 큐 과정에서 비효율적이라 판단을 하기 때문에 스택과 큐에서는 기본적인 배열을 사용하지 않는다.

 

연결 리스트는 배열 맨 앞을 가리키는 head 포인터를 사용하는데 이로인해 리스트의 첫 부분을 제거하거나 추가하는 과정의 시간 복잡도가 상수이고 보다 효율적인 알고리즘인 연결 리스트는 스택과 큐를 하는데 사용이 된다.

 

일반적으로 배열은 연결 리스트보다 빠르고 메모리도 덜 차지하지만 크기가 정해져 있다는 특징이 있다.