자료구조는 언어별로 지원하는 양상이 다르기에 언어가 가진 자료구조의 종류를 아는것은 중요합니다.

List(Array)

파이썬에서는 List, 자바스크립트에서는 Array라고 불리는 자료구조는 가장 기초적이며 자주 사용되는 자료 구조 입니다.

1. List(Array)의 특징

• 저장되는 데이터는 일반적으로 요소(element)라고 하며, 데이터를 순차적으로 저장합니다.
• 주로 서로 연결된 데이터를 순차적으로 저장할때 사용합니다.
• 순서가 상관없는 데이터들을 저장할때도 사용합니다.
• 리스트안의 요소들을 수정할 수 있습니다.
• 동일한 값도 여러번 삽입(insertion)가능 합니다.(중복 허용).
• 리스트안에 리스트를 만드는것이 가능합니다.(Multi-dimensional Array)
  이를 통해서 다중차원 리스트(예를들면 2D 리스트)를 만드는것이 가능합니다.
  2D 리스트는 선형대수학에서 배우는 행렬(matrix)을 생각하면 됩니다.

---

-참고 (몰라도 됨)-

선형대수학의 행렬과 다차원 리스트의 차이점은?

선형대수학에서 2X2 행렬의 경우 1행 1열, 1행 2열, 2행 1열, 2행 2열
이렇게 '행(row)' 과 '열(column)' 순서대로 읽으며 시작 인덱스가 1이지만,
대부분의 언어(c, c++, c#, python, Java, JavaScript 등...)에서는 인덱스 숫자가 0부터 시작합니다.

인덱스 순서가 0이 아닌 언어도 있나요?
Fortran, Julia, MATLAB과 같은 수치해석용 언어는 배열의 시작 인덱스가 1부터 시작하며, Fortran의 경우에는 행,열 순서가 아니라 열,행 순서입니다.

---

2. List(Array)의 내부 구조

리스트에 순차적으로 데이터를 저장하다보니,
데이터에 인덱스 번호를 주고 특정 인덱스에 데이터를 저장하거나
이미 저장된 데이터(요소)에 접근해서 해당 요소를 읽거나 삭제하는게 가능합니다.
또한 요소의 특정 시작 인덱스 n부터 특정 인덱스 M까지 따로 분리해서 조작하는것이 가능합니다.

3. List(Array)의 단점

3.1) Removing or Adding Elements

데이터를 순차적으로 저장하기에 생기는 단점으로 리스트 중간의 특정 요소를 삭제할 경우,

삭제한 요소 뒤쪽의 요소들을 전부 앞으로 이동시켜줘야 합니다.
따라서 다른 자료 구조에 비해서 요소를 삭제하는것이 느릴 수 있습니다.

마찬가지로 리스트 중간에 데이터를 삽입하는것도 같은 방식으로 작동하기에
(삽입된 데이터 뒤쪽의 요소들을 한칸씩 뒤로 이동) 다른 자료구조에 비해 느릴 수 있습니다.

따라서 List(Array)는 요소를 자주 삭제하거나 추가해야하는 데이터를 담기에는 적절하지 않습니다.

3.2) Array Resizing

리스트를 사용하면, 메모리에 데이터를 순차적으로 저장하기 때문에,
처음 리스트를 생성할때, 어느정도 미리 메모리 할당을 합니다.(pre-allocation)

미리 할당한 메모리 공간보다 더 큰 데이터를 저장해야 할 경우에,
메모리의 빈공간에 사용한 메모리보다 더 크게 할당을 하고
기존 메모리에 있던 데이터를 새로 할당한 더 커진 메모리 공간에 복사합니다.
따라서 배열의 resizing은 상대적으로 오래걸리는 작업(operation)입니다.

따라서 List(Array)는
저장할 데이터의 크기를 예측할 수 없을 경우, 사용하기에 적절한 자료 구조는 아닙니다.

4. 언제 List(Array)를 사용하면 좋을까?

• 순차적인 데이터를 저장할 경우
• 다차원 데이터를 다룰 때 (예를들어서 선형대수학의 행렬)
• 인덱스가 있기 때문에 특정 요소를 빠르게 읽어야 할 경우 사용하면 좋다.
• 데이터의 크기가 자주 바뀌지 않고, 특정 요소가 자주 삭제 되거나 추가 되지 않을때