[백엔드 기술면접] 배열, 링크드리스트를 비교하여 설명해주실 수 있을까요?

May 31, 2023 1 분 소요

서론

배열과 링크드리스트에 대해서 알아보고 두 자료구조의 특징 및 차이점을 비교해보고 추가로 시간복잡도( O(n) )와 통상적으로 쓰이는 사례도 알아봅시다.

배열은 정적 자료구조라고 불립니다. 그래서 배열을 만들기 위해서는 미리 크기를 정해놓게 되는데 이 때 해당 크기만큼의 연속된 메모리 주소를 할당 받게 된다.

연속된 메모리 주소를 할당 받고 있기 때문에 데이터가 인덱스(index)라는 것을 갖게 된다.
예시로 array[0] 같은 식으로 배열에 접근할 때 대괄호 [] 안에 숫자가 index이다.(javascript 기준)

index를 갖게 된다는 것은 임의 접근이 가능하다는 장점이 있다. 그래서 접근과 탐색이 용이하다

하지만 크기를 미리 정해놓았기 때문에 수정하는 것이 불가능하다. 또한 이미 크기를 정해 놓은 터라 해당 배열의 크기 이상의 데이터를 저장할 수 없다는 단점이 있다.

링크드 리스트, 또는 연결 리스트는 동적 자료구조라고 불립니다. 그러므로 크기를 정할 필요가 없다. 또한 배열처럼 연속된 메모리 주소를 할당 받지 않는다.

대신 노드(Node)라는게 존재하며, 그 노드 안에 데이터가 있고, 다음 데이터를 가리키는 주소를 가지고 있다.

연결리스트는 위에서 말한 것처럼 크기를 정해 놓지 않았기 때문에 크기의 제한이 없다. 그로인해 데이터 추가, 삭제가 자유롭다는 장점이 있다.

반면에 배열처럼 연속적인 메모리 주소를 할당 받지 않았기 때문에 임의로 접근하는 것이 불가능하다. 그 말은 즉슨 데이터를 탐색할 때 순차적으로 접근해야 한다는 것이다.

배열과 링크드리스트

배열은 접근과 탐색이 용이하다고 했는데, index를 가지고 있기 때문이다. 탐색은 O(1)의 시간복잡도를 가진다.
삽입의 경우 맨 뒤라고 하면 O(1)의 시간 복잡도를 가지지만 맨 뒤가 아닌 나머지는 O(n)이다.

링크드 리스트는 추가, 삭제가 용이하다고 했는데, 삽입은 맨 앞일 경우 O(1)의 시간 복잡도, 맨 앞이 아닌 나머지는 O(n)이다.
그리고 배열과 반대로 탐색은 O(n)의 시간복잡도를 가진다.

배열은 고정된 크기를 가지고 빠른 접근이 필요한 경우에 유용하며, 링크드 리스트는 동적인 크기 조절과 삽입/삭제가 빈번한 경우에 유용합니다. 각각의 데이터 구조는 장단점을 가지고 있으므로 사용하는 상황에 맞게 선택해야 합니다.