[ 선형 자료구조 ] 배열 & 리스트

1. 배열

 1) 개념

  배열은 연관된 데이터를 그룹핑해 관리하는 방식의 자료구조이다. 연속적인 메모리 블록에 데이터를 저장하며, 각 항목을 요소(element)라 한다. 배열은 생성될 때 크기가 고정되며, 해당 위치를 결정하는 인덱스를 가진다.

 

2) 배열의 특징

(1) 장점

1. 각 항목이 고정적인 인덱스를 가지며, 이를 통해서 각 항목의 요소로의 접근이 O(1)의 빠른 시간복잡도를 가진다. 따라서 잦은 접근이 필요한 데이터를 저장하기에 알맞다.
2. 배열의 경우 데이터의 크기가 고정적이고 잦은 접근이 필요한 경우, 혹은 인덱스가 중요한 경우 이점을 가진다.

 

(1) 단점

1. 생성과 함께 사이즈가 고정되기 때문에 요소의 추가/삭제가 자유롭지 못하다.
2. 항목의 데이터를 삭제해도 인덱스 값은 고정되며 메모리상에서 지속적으로 자리를 차지한다. 즉, 메모리가 낭비된다.
3. 요소의 추가/삭제를 위해선 새롭게 배열을 생성하고 기존의 배열의 요소들을 복사해가며 추가해야하기 때문에 시간 및 메모리 소모가 크다.(이때 사용되는 것이 doubling등이다.)
4. 연속된 메모리에 저장되므로 데이터가 커질수록 메모리 확보에 어려움이 있을 수 있다

 

 

2. 리스트

1) 개념

  리스트는 배열의 고정적 인덱스를 포기하고 데이터를 입출력에 따라 메모리 상에서 요소의 위치를 바꿔 빈틈없이 데이터를 적재한다. 리스트는 각각의 요소가 고정적인 인덱스를 갖지않는 대신 요소간 순서를 인덱스로 나타내며, 이러한 순서가 존재하는 데이터의 집합이 리스트이다.

 

2) 리스트의 특징

(1) 장점

1. 요소의 삽입/삭제가 효율적이다
2. 메모리상에서 데이터의 입/출력에 맞추어 요소의 위치를 변화시킴으로써 배열에 비해 메모리를 효율적으로 사용한다.(메모리 재사용)
3. 담고 있는 데이터 크기의 변화가 가능하다.
4. 중복된 데이터 또한 허용된다.
5. 크기가 변화하는 데이터를 담기에 적합하다. (ex. 문자열, 행렬 등)
6. 스택, 큐와 같은 자료구조를 구현하기 위해 쓰인다.

 

(1) 단점

1. 각 요소에 대한 접근을 위해서 리스트를 순회해야 하므로 비효율적이다.
2. 인덱스에 대한 정보 또한 포함하기 때문에 사용되는 메모리가 배열에 비해 크다.
3. 배열에 비해 복잡한 알고리즘을 통해 구현된다.

 

 

3. 배열 리스트

1) 개념

  배열 리스트는 배열을 통해 리스트를 구현한 것이다. 배열의 장점을 따온 만큼 인덱스를 통한 접근이 빠르나 데이터의 추가 삭제는 느리다.

 

2) 리스트의 특징

(1) 장점

1. 배열이 꽉 차면 기존 배열의 2배의 크기를 가지는 배열을 생성후 기존 데이터를 복사(doubling)해 크기에 신경을 쓰지 않고 데이터의 추가/삭제가 가능하다. 
2. 인덱스를 통해 요소에 빠르게 접근 가능하다.
3. 다른 종류의 데이터 타입을 갖는 요소를 저장 가능하다.

 

(1) 단점

1.  배열 리스트 자체는 고정된 크기를 갖으며, 배열이 꽉찰 경우 새롭게 배열을 생성해 재할당한다. 이 과정 비교적 많은 시간이 소모된다.
2. 요소의 추가/삭제가 느리다. (대상 이후의 모든 요소의 위치 조정이 필요)

 

 

3. JS의 배열

 자바스크립트의 경우엔 array가 object를 바탕으로 구현되며 크기가 고정된 C에서와는 다르게 요소의 추가/제거에 따라 동적으로 변경된다. 즉, 자바스크립트에서 array는 length 프로퍼티, 순회와 변형에 대한 메소드를 가지는 특별한 객체 유형이라고 볼 수 있다. 이는 배열 리스트와 가장 유사함을 보이지만 배열 리스트라 할 순 없다.