Array 배열

• 데이터가 많아지면 모아서 관리하는 것이 필요하다. 이럴 때 사용하는 것이 배열.
• 여러 가지 데이터를 하나의 이름으로 그룹화 하여 관리하기 위한 자료구조
• 배열을 이용하면 하나의 변수에 여러 정보를 담을 수 있고, 반복문과 함께 사용하면 많은 정보도 효율적으로 처리할 수 있다.
• 배열의 인덱스는 값에 대한 유일무이한 식별자이다. ( 리스트에서 인덱스는 몇 번째 데이터인가의 의미를 가짐 )

배열의 특징

• 크기가 정해져 있다, 기능이 없다.

  • 이는 배열의 장점이자 단점. 다른 자료구조의 토대로 쓰일 수 있다.
• 인덱스를 가지고, 엘리먼트의 인덱스는 변경되지 않는다.
• 유관 데이터를 메모리에 순차적으로 나열할 수 있다.
• 인덱스를 활용하여 빠르게 조회 가능
• cache hit의 가능성이 커져 성능 향상에 도움을 준다.
• 인덱스를 이용하여 데이터를 가져오려면 데이터에 대한 인덱스 값이 고정되어야 한다. 삭제된 엘리먼트의 공간이 그대로 남는다.

배열의 한계

• 배열은 길이 변경이 불가능하다. 가변 배열과 같이 길이를 변경할 수 있는 배열은 1) 새로운 길이의 배열 할당 2) 데이터 복사 3) 기존 배열 삭제 의 순서로 길이를 변경하기 때문에 리소스 낭비가 크다.
• 이와 같은 한계를 해결하기 위해 linked list 자료형을 사용할 수 있다. (탐색, 복사, 할당, 삭제 등의 리소스 낭비가 없다)
• 배열은 인덱스에 따라 값을 유지하기 때문에 엘리먼트가 삭제되어도 빈 자리(null)가 남는다.
• 조건문을 통해 빈 엘리먼트를 제외할 수 있지만, 조건문을 많이 사용하는 것은 좋지 않다.
• 삭제한 데이터를 뒤에 위치한 엘리먼트로 메꾸면 ( 빈자리가 없도록 채우면 ) 데이터는 순서에 따라 연속적으로 위치하게 되고 이를 List 리스트라고 한다.
• 인덱스가 중요한 경우에는 배열을, 인덱스가 중요하지 않은 경우에는 리스트를 사용한다.

List 리스트

• 리스트는 배열의 인덱스를 버리고 빈틈 없는 데이터의 적재를 목표로 하는 자료구조이다.
• 리스트의 핵심은 엘리먼트간의 순서 이다. 따라서 리스트를 시퀀스Sequence라고도 부른다.
• 리스트에서 인덱스는 몇 번째 데이터인가의 의미를 가진다. ( 배열에서의 인덱스는 값에 대한 유일무이한 식별자 )
• 빈 엘리먼트는 허용하지 않는다.

• 순차성을 보장하지 못하기 때문에 spatial locality를 보장할 수 없어 cache hit가 어렵다.

  Locality : Temporal locality와 Spatial locality가 있다. Temporal의 경우 최근 접근한 데이터를 더 자주 접근하는 경향(시간, Spatial의 경우 접근한 데이터의 주변 공간에 더 자주 접근하는 경향. 참고자료 https://parksb.github.io/article/29.html

• 데이터의 갯수가 확실하게 정해져 있고, 자주 사용된다면 배열이 더 효율적이다.
• 리스트는 어떤 언어를 사용하느냐에 따라 효용이 달라진다. 많은 언어가 리스트를 기본적으로 지원하기 때문에 리스트를 직접 구현하는 것은 줄고 있다.

리스트의 대표 기능(operation)

• 처음, 중간, 끝에 엘리먼트를 추가/삭제하는 기능
• 리스트에 데이터가 있는지를 체크하는 기능
• 리스트의 모든 데이터에 접근할 수 있는 기능

언어별 리스트 지원

C

리스트를 지원하지 않고 배열만 지원한다. 리스트를 사용하려면 직접 만들거나 라이브러리를 사용해야 한다.

JavaScript

배열에 리스트의 기능이 포함되어 있다.

Python

기본적으로 리스트를 제공하고, 배열을 제공하지 않는다. 파이썬에서는 리스트=배열. 파이썬의 리스트 크기는 가변적이고, 어떤 원소 타입이든 저장할 수 있다. 단 메모리를 많이 사용한다.

Java

자바는 배열과 리스트를 모두 지원하고, 두 가지가 완전히 분리되어 있다. 배열과 리스트를 개발자가 직접 선택 가능.

두 가지 형태의 리스트를 제공한다 : LinkedList, ArrayList 같은 기능(메소드)를 가진 리스트가 두 종류 존재한다.

Java에서의 LinkedList, ArrayList

Java에서는 배열 이외에 LinkedList, ArrayList 두 가지 종류의 리스트를 제공한다.

• ArrayList → 추가/삭제가 비교적 느리고, 인덱스 조회가 빠르다.
• LinkedList → 추가/삭제가 빠르고, 인덱스 조회가 비교적 느리다.