[Backend 개발자 면접 준비] 배열(Array) 과 연결리스트(Linked List)

자료를 관리 할때 배열이나 리스트를 자주 사용하게 된다.

자주 사용하는 만큼 배열과 리스트의 특징과 차이에 대해 알아보고자 한다.

 

배열(Array) 이란?

배열은 정적 자료구조이며, 배열을 만들기 위해서는 미리 크기를 정해 놓아야 한다.

그렇게 되면 해당 크기만큼의 연속된 메모리 주소를 할당 받게 된다.

 

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

 

index를 갖게 된다는 것은 즉 임의 접근이 가능하다는 장점이 있어 접근과 탐색에 용이합니다.

 

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

 

위와 같은 배열이 있다고 가정을 해보자.

여기서 주목할 점은 메모리가 연속적이며, Index 가 존재 한다는 점이다.

 

위와 같은 배열에서 추가로 데이터를 삽입하고자 할때 이미 배열이 포화된 상태라 추가 데이터 삽입이 불가하다.

 

index 2 자리에 새로운 값을 삽입 하고자 할때를 보자.

 

기존데이터들을 한칸씩 뒤로 이동한 다음에 해당 값을 넣는다.

데이터 삭제도 동일한 방법으로 진행하되, 데이터를 지운후 기존 데이터를 앞으로 한칸씩 이동하면된다.

 

연결리스트란(Linked List)?

링크드 리스트 혹은 연결 리스트는 동적 자료구조이므로 크기를 정할 필요가 없다. 또한 배열처럼 연속된 메모리 주소를 할당 받지 않는다.

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

 

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

 

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

 

 

 

위에 그림과 같이 링크드 리스트는 주소가 불연속적으로 저장이 되어 있다.

 

여기서 데이터를 삭제 할때는 삭제데이터가 가르키는 데이터와 삭제데이터를 가르키는 데이터를 서로 연결 한뒤 삭제데이터와 연결된 부분을 모두 끊어주면 된다.

 

 

이와 같은 구조에서 중간에 값을 삽입 할때를 보자.

 

새로운 값을 연결하고 기존에 연결된 부분을 끊어 주면 된다.

 

 

Array vs Linked List

• Array는 연속된 메모리 공간에 존재하고 Linked List는 메모리 상에서 떨어져 있는 데이터들이 앞의 데이터와 뒤의 데이터를 기억하는 형태로 존재한다.
• Array에 저장되어 있는 데이터를 조회할 때는 O(1)로 가능하지만 Linked List는 O(N)이 소요된다.
• Array에 데이터 추가 및 삭제할 때는 O(N)이 소요되지만 Linked List는 O(1)로 가능하다.
• 추가적으로 Array는 컴파일 과정에서 메모리가 할당되는 정적 메모리 할당인 반면 Linked List는 런타임 환경에서 메모리가 할당되는 동적 메모리 할당이다.
• 또한 배열은 Stack 영역에 메모리 할당이 되고, Linked List는 Heap 영역에 할당이 된다.

 

 

Reference Link

https://blacklobster.tistory.com/8

https://kimmeh1.tistory.com/473