링크드 리스트(연결 리스트), 그리고 배열과의 차이점

링크드 리스트는 일련의 데이터들을 연결시켜 각 데이터에 대한 접근과 추가, 삭제 및 여러 연산을 가능케하는 리스트를 말한다.

 

그것의 기능적 측면이 배열과 매우 유사하기 때문에 두 자료구조의 차이를 묻는 기술면접 질문들이 종종 나온다고 한다.

 

링크드 리스트와 배열의 차이? -> 메모리상에 데이터를 저장하는 방식이 다르다!

 

링크드 리스트와 배열의 가장 큰 차이점은 그 둘이 리스트 안에 담길 데이터를 메모리 상에서 어떻게 저장하는지에 있다.

 

배열은 데이터들을 메모리 상에 연속적으로 저장한다. 즉, 예를들면 메모리상에서 1 ~ 10까지의 영역을 맡아놓고 그 영역 내에서 데이터를 저장한다.

 

반면에, 링크드 리스트는 데이터를 공간적으로 붙여놓는 것이 아닌 각 데이터에 다음 데이터의 주소에 대한 정보를 갖게 함으로써 데이터들을 연결시킨다. 

 

 

링크드 리스트와 배열의 장단점

 

이러한 링크드 리스트와 배열의 차이점에서 두 자료구조의 장단점이 명확하게 드러난다.

 

 

데이터에 대한 접근 - 배열 우위

 

먼저, 배열은 인덱스를 이용해 데이터에 접근하기 때문에 배열의 크기와 관계없이 O(1)시간 내에 빠르게 데이터에 접근할 수 있다.

 

반면에, 링크드 리스트는 원하는 데이터에 접근하기 위해선 반드시 순차적으로 첫 번째 값부터 다음 값들을 타고 가야하기 때문에 데이터에 접근하는데 있어서 O(n)의 시간이 걸린다.

 

 

데이터 삽입 및 삭제 - 링크드 리스트 우위

 

그러나 데이터를 새로 삽입하거나 특정 데이터를 삭제하는 경우에는 링크드 리스트가 유리하다는 평가를 받는다.

 

배열의 경우, 이미 꽉 찬 배열에 데이터를 삽입 시 새로운 더 긴 배열을 만들고 이전값들과 새로운 값들을 모두 새로 복사해와야하므로 최악의 경우 O(n)만큼의 시간이 걸린다.

 

하지만 링크드 리스트는 그러한 과정 없이, 맨 뒤의 값에 다음 값의 주소정보를 추가해주기만 하면 된다.

 

삭제의 경우도 마찬가지이다.

 

배열은 특정 데이터를 삭제 시 그 뒤의 데이터들을 모두 앞으로 한칸 씩 땡겨와야 하지만, 링크드 리스트는 삭제된 데이터에 대하여 이전 값의 주소 정보를 변경해주기만 하면 된다.

 

* 사실, 링크드 리스트 역시 삽입과 삭제를 하기 위해선 삽입할 위치, 삭제할 데이터의 위치 등을 먼저 탐색한 후 동작을 수행하기 때문에 O(n)만큼의 시간이 걸리긴 한다. 링크드 리스트의 우위성은 그것의 처리 과정이 배열보다 더 간단함에 있다. 

 

 

메모리상의 공간적 낭비 - 링크드 리스트 우위

 

공간적 측면에서도 링크드 리스트는 우위를 갖는다.

 

배열이 동적배열이라고 가정했을 때, 배열이 꽉 찼을 때마다 두 배의 길이로 늘어난다는 특성상 할당되어있는 모든 메모리가 사용되는 경우는 그렇지 않은 경우보다 훨씬 적을 것이다.

 

다시 말해, 동적배열은 메모리를 낭비할 가능성이 존재한다.

 

하지만, 링크드 리스트는 비어 있는 메모리에 꼭 맞는 각각의 데이터들을 따로따로 저장해주기 때문에 메모리를 낭비할 가능성이 적어진다. 

 

---

결론

 

데이터에 대한 접근의 빈도가 높을 경우에는 배열이, 새로운 데이터를 삽입하거나 삭제해야할 일이 잦을 때는 링크드 리스트가 더 효율적인 자료구조가될 것이다.