[자료구조] # 1. 배열(Array)과 리스트(List)의 차이

은근 많이 나오는 질문인데, 그냥 무지성 파이썬 입문하다보면 이 두 개념의 차이에 대해 잘 모를 수도 있다.

 

일단... 질문은 저렇게 러프하게 나오지만 정확히는 정적배열과 연결리스트의 차이를 염두한 질문 같다.

배열도 넓은 범위에서는 "선형 리스트" 에 속하기 때문이다. 아마 Java를 쓰시는 분들이라면 ArrayList vs LinkedList에 대한 질문임을 캐치하셨을 것이다.

 

일단 정적배열이라 함은.. 배열을 선언할 때, 그 크기를 미리 정해두는 것을 시작으로 한다.

int arr[5] = {0,};

 

그럼 이런 배열의 특징이 무엇일까.

• 연속된 메모리 주소에 값이 할당된다.
• 인덱스로 접근하는 탐색 방법이라 조회 속도는 빠른데, 삽입/삭제가 느리다. 
  • 삽입/삭제가 느린 이유는 맨 끝이 아닌 다른 부분의 경우다. 중간에 값이 들어서는 경우, 기존에 있던 값들이 1만큼 뒤로 밀려나게 되므로, N번의 수행이 추가가 된다. 즉, 시간복잡도가 O(N)인데 연결리스트의 경우는 O(1)이라서 상대적으로 Array의 경우가 늦는 것이다.
• 연속된 메모리 주소라는 특성상 Cache Hit Rate가 좋다. 이게 뭐냐면, CPU 프로세서가 빠르게 데이터를 주고 받을 수 있도록 중간에 있는 기억 장치를 캐시라고 하는데  메인 메모리로 원하는 데이터를 찾으러 가기 전에 캐시에 방문한다. 최근에 참조되었거나, 특히 자추 참조되는 애들을 위주로 이 캐시에 데이터 정보가 저장이 된다. 연속된 메모리 주소의 경우는 캐시의 공간 지역성 원리 때문에, Rate가 높게 나온다는 장점이 있다.

 

그 다음은 연결리스트다.

연결리스트는 포인터의 개념이 들어간다.

이런 식으로 하나의 노드 안에 데이터와, 다음 노드를 가리키는 포인터가 들어가있다. 여기서 선형리스트 (배열)과의 탐색에서 차이를 엿볼 수 있다. 선형리스트는 앞서 인덱스로 접근하는 식이라 O(1)의 시간복잡도를 갖는 탐색 성능을 보이지만, 얘는 단지 연결관계만 나타내고 인덱스가 없다. 그러므로, 선형 탐색으로 찾아가야해서 O(N)의 시간복잡도를 가진다.

 

여기서 또 하나 짐작이 가능한 것. 인덱스가 없기에 삽입/삭제가 빠르다.

삽입의 경우는 직전 노드에 포인터 수정을, 그리고 삽입된 노드가 다음 노드를 가리킬 포인터를 구현해놓기만 하면 된다.

삭제 역시 비슷한 방식으로 수정해주면 된다. 그래서 삽입/삭제에 빠르다.

 

이외에도 연결리스트는 종류가 많지만 보통 기술면접에서 묻는다면 단순 연결리스트를 전제하에 선형리스트(배열)랑 비교하는 수준이다.