Stack의 구현은 벡터 vector ? 연결리스트 Linkedlist ?

최근 졸업이 예정되면서 면접을 보러다니기 시작하고 있다.

면접에서는 보통 1차적으로 기술면접을 보게되는데, 전공과 업계기술을 얼마나 숙지하고 있는지 질문을 받게된다.

개인적으로 기대되는 프로젝트를 진행중인 회사에서 운좋게 면접기회를 얻게 되었는데 해당 면접에서 면접관님께 받았던 질문중 하나가  글의 제목과 같다.

 

"Stack을 구현할때는 벡터와 연결리스트 중 어떤걸 선택하실건가요?"

 

 

stack, vector, linkedlist 세가지를 모두 파악하고 있어야 답할 수 있어야하는 질문이었다.

앞선 질문에 vector와 linkedlist의 장단점에 대해서는 제대로 답을 했지만 Stack이 연관되자 당시에 쉽게 답을 내지 못했다. 그렇게 어려운 질문을 하신것도 아니었는데, 지금 생각하면 정말 창피한 기억이다. 첫 면접이라는 상황속에서 긴장해 뇌가 정지되버렸던걸까.

 

 Vector

vector의 경우 C++의 배열의 동적할당이다.

기본적으로 배열을 통해 구현되며, 내부적인 size와 capacity가 있어 size가 capacity를 초과하는 insert가 실행되면 내부적인 확장정책으로 더 큰 capacity의 배열을 할당하고 기존 배열의 원소를 옮겨, 기존 배열은 제거한다.

(확장정책의 경우 STL 기준으로 기존사이즈의 1.5배를 할당한다.)

원소의 물리적 저장순서가 논리적 저장순서와 같이 연속적으로 저장된다. 이를 통해 Random Access가 가능해지며 O(1)의 검색속도를 가질 수 있다. 다만 삽입과 삭제 시 뒤의 원소들을 shift해야 하기에 O(n)의 시간복잡도가 소모된다.

 

LinkedList

저장순서에 따라 연관된 연결된 노드의 포인터를 data와 함께 저장한다.

배열과 달리 연속적으로 저장되지않아 O(n)의 검색속도를 가진다.

다만 삽입과 삭제 과정에서 연관된 노드의 포인터만 변경해주면 되기 때문에 O(1)의 시간복잡도를 가진다.

 

위 질문에 대한 옮은 답변은 '연결리스트'였던 것 같다.

연결리스트가 data이외에도 노드의 포인터를 가지고 있어야한다는 점에서 약간의 메모리의 차이는 있겠지만,

중요한건 Stack의 경우 데이터의 입력과 출력이 모두 'Top'에서 진행된다는 점이다.

 

스택에서는 항상 top위치를 기록하고 있기때문에

linkedlist 가 불리한 검색과정을 거칠 필요도 없고 빠른 삽입과 삭제가 가능하다.

vector의 경우 스택내의 push과정에서 O(1) 시간과 최악의 경우 O(n) 시간이 걸릴 수 있다.

(ex: capacity를 초과하여 새 배열을 할당하는 케이스)