thumnail-min.png

배열이란?

array-min.png

배열은 컴퓨터에서 리스트를 저장하는 데이터 타입 중 하나이다. 아마 따로 자료구조를 공부하지 않았더라도 개발 언어를 사용해봤더라면 알만할만큼, 자주 사용하는 자료 구조이다.

배열은 데이터를 메모리 상에서, 순차적으로 저장하며 메모리를 정적인 크기로 할당받는다. 즉, 배열의 데이터들은 연속적(continuouse)이며 인접(contiguous)해 있어야 한다. 그렇기 때문에 배열은 메모리를 할당받게 되면 데이터에 대한 index를 가지게 되며 이 index를 사용해 배열의 요소를 읽을 수 있다.

앗? 자바스크립트의 배열은 동적인 크기인데? 라고 생각할 수도 있다. 엄밀히 말하면 자바스크립트의 배열은 실제 자료구조에서 이야기하는 배열은 아니고 Hash Map이나 Dictionary, Linked List로 구현되어 있다.

장점

  1. index를 가지고 있기 때문에 데이터에 바로 접근이 가능하다.

    시간 복잡도를 O(1)로 갖게 되며 자료 구조의 크기가 클수록 더욱 효율적이다.

단점

  1. 삽입과 삭제가 오래걸린다.

    배열의 마지막 원소에 삽입, 삭제 작업이 발생할 경우 작업이 간단하게 끝날 수 있지만, 그게 아니라면 배열의 원소 삽입, 삭제 연산 시 모든 원소들을 연속적으로 만들어야 하므로 index를 조정해야 한다.

  2. 배열의 크기는 정적이다.

    배열은 메모리 상에서 순차적으로 데이터를 저장하여야 하기 때문에 고정된 크기를 갖게 되므로 배열의 길이가 데이터의 수와 맞지 않으면 데이터의 낭비 혹은 부족 문제가 발생할 수 있다.

배열 vs 링크드 리스트

배열과 링크드 리스트는 데이터를 나열한 다는 점에서 자주 비교되는 대상이다.

  1. 데이터 접근

    배열은 index만 알고 있다면 메모리의 주소로 바로 접근할 수 있기때문에 O(1)의 시간 복잡도를 가지지만, 링크드 리스트는 연결되어 있는 노드를 탐색하며 접근해야 하기 때문에 O(n)의 시간 복잡도를 가지며 배열에 비해 속도가 느리다.

  2. 데이터 삽입, 제거

    배열은 데이터 삽입, 제거 시 기존의 데이터들의 위치를 이동시키는 경우가 많아 비효율적일 수 있지만, 링크드 리스트는 삽입, 제거하려는 데이터의 이전, 이후 노드의 링크만 연결시키면 되기 때문에 효율적이다.

  3. 메모리 공간 활용

    배열은 고정된 크기의 메모리를 할당받아 크기를 변경할 수 없지만 링크드 리스트는 연결되어 있는 노드에 따라 크기가 동적으로 변하므로 효율적으로 메모리를 사용할 수 있다.

즉, 배열과 링크드 리스트 모두 장단점이 나뉘기 때문에 데이터 삽입, 제거가 빈번하게 발생한다면 링크드 리스트, 이미 만들어져 있는 데이터 구조에서 접근이 많이 발생한다면 배열이 유리하다.