큐 연결리스트 vs 배열

큐

일전에도 포스팅 했던 큐 관련이다. 다시 한번 개념을 잡고 가자면 먼저 넣은 데이터가 먼저 나오는 선입선출의 선형 자료구조이다. (FIFO, LILO 순서를 따름.)

연결리스트 (Linked List)

데이터의 양과 상관없이 크기가 동적으로 조절되고, 인덱스 대신 이전 데이터, 다음 데이터의 위치를 기억하는 구조를 이용한다. 따라서 리스트 중간에 데이터 삽입과 삭제 시 연결된 링크를 이어주거나 끊으면 된다. 하지만 데이터에 접근할 때 연결되어 있는 양 끝에서부터 순차적으로 접근해야하기 때문에 배열보다 느리다.

배열 (Array)

인덱스를 통해 배열 내 데이터에 접근을 빠르게 할 수 있다. 다만, 선언할 때 크기가 고정되어 배열에 들어 있는 데이터양에 따라 크기 조정이 필요하다. 데이터를 중간에 삽입하거나, 삭제할 경우 해당 데이터 뒤에 있는 요소들의 위치를 모두 이동시켜야 하는 비효율적 상황이 발생한다.

결론

모든 원소의 값을 사용하거나 중간에 데이터를 삽입 및 삭제를 할 때는 연결리스트
특정 원소의 값을 검색하는 것이 목적이라면 배열을 사용하는 것이 좋다.

문제는 목적지에 얼마나 빨리 가느냐가 아니라 그 목적지가 어디냐는 것이다. -메이벨 뉴컴버