배열(Array)과 연결리스트(Linked List) 차이

배열과 링크드리스트에 대한 차이를 기술 면접 준비하면서 정리한 것을 쓴다.

-속도-

(1번 포인트) 데이터에 대한 접근 속도 - 배열 승

배열은 index만 있다면 O(1)에 접근.

연결리스트는 최소 한 번은 리스트를 순회하여야 하므로 O(n)에 접근.

(2번 포인트) 데이터 삽입 속도 - 경우에 따라 다름 (전체적으로 연결리스트 승리)

만약 배열에 공간이 많이 남아있고 맨 끝에 삽입한다면, 삽입 속도 역시 O(1)에 가능.

하지만 이런 경우만 발생하는 경우는 꽤 드물기 때문에 연결리스트의 필요성이 대두됨.

연결리스트는 어느 곳에 삽입하던지 O(n)의 시간에 접근함. (만약, 중간 삽입이 없다면 O(1)에 접근)

배열의 경우 데이터를 중간이나 맨 앞에 삽입할 경우 그 이후의 데이터를 한 칸씩 미뤄야하는 추가과정과 시간이 소요.

하지만 연결리스트는 필요없음.

또한 배열의 경우 데이터 삽입시 모든 공간이 다 차버렸다면, realloc()또는 새로이 할당하여 메모리 공간 확장이 필요.

하지만 연결리스트는 필요없음.

데이터 삽입의 경우 범용적인 측면에서 연결리스트의 승.

(3번 포인트) 데이터 삭제 속도 - 경우에 따라 다름 (전체적으로 연결리스트 승리)

위의 2번 포인터와 똑같음.

단지, 데이터 삭제의 경우 그 위치의 데이터를 삭제 후, 전체적으로 한 칸씩 앞당기면 되지만

연결리스트의 경우 예외조건들의 처리가 꼼꼼히 필요함. 그렇기에 코드의 복잡성 증가. - (하지만 이미 만들어진것 사용해서)

결국은 이 역시 범용적인 측면에서 연결리스트의 승.

(결론)

삽입과 삭제가 번번히 이루어진다면, 연결리스트 사용이 좋음.

이미 만들어진 구조에서 데이터의 접근만 필요하면 배열이 좋음.

결국 배열도 해쉬의 일종이고 가장 기본적인 해쉬 기법이 바로 배열.

그리고 또 하나 알아두어야 할 것!

위의 내용만 보면 전반적으로 리스트의 사용이 훨씬 좋아보인다. 하지만 일반적인 알고리즘 문제를 풀이할 땐

리스트보다 배열이 훨씬 빠르고 좋다. 왜냐하면 대부분의 알고리즘 연습문제들은 그 메모리 공간의 범위를

주어지기 때문에 배열 선언을 그 MAX치로 잡을 수 있다면, 훨씬 더 편리하고 리스트와는 전혀 다른 속도를 보인다.

왜냐하면 리스트의 입력은 추가 과정마다 메모리의 할당이 일어나고 삭제에서는 메모리의 해제가 일어난다.

메모리의 할당과 해제는 O() 시간으로 따지지 않지만, 이런 시스템 콜(System Call)을 사용하는 문구는 시간소요가 꽤 걸린다.

그러니 결국은 배열이든 리스트이든 단순히 이론을 떠나서 자기가 무엇을 하려는지, 그 목적에 따라 선택하는 것이 좋다.