[자료구조] 배열(Array) / 리스트(List)

■ 배열 (Array)

• 배열의 크기는 한 번 정하면 변경할 수 없다.
• 배열 초기화 시에 메모리에 할당되어 ArrayList보다 속도가 빠르다.
• 논리적 저장 순서와 물리적 저장 순서가 일치한다.
• 인덱스를 사용해 특정 원소에 접근이 가능하다.
  • 즉, Random Access(비순차적 접급)가 가능하다.
• 인덱스를 알고 있다면 특정 원소에 접근하는 시간 복잡도는 O(1)이다.
• 생성할 때 데이터를 저장하는데 필요한 메모리를 한 번에 확보해서 사용한다. (연속된 메모리 사용)
  • 배열의 크기를 바꿀 수 없다. 즉, 배열의 크기는 제한적이다.
• 배열의 원소를 삭제할 경우 
  • 삭제한 원소보다 큰 인덱스를 값을 갖는 원소들을 1씩 옮겨줘야 하기 때문에 시간 복잡도는 O(n)이다.
• 배열의 원소를 삽입할 경우
  • 배열의 크기가 충분할 때는 시간 복잡도는 O(1)이다.
  • 여유 공간이 없을 경우, 확장이 필요하기 때문에(새로운 원소를 추가하고 인덱스를 1씩 옮겨줘야 함) 시간 복잡도는 O(n)이다.
• 메모리는 Array가 선언될 때(컴파일 할 때) Stack 영역에 할당한다.

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

※ 배열의 특징

• 크기가 정해져 있다 / 기능이 없다
  • 이는 배열의 장점이자 단점으로 배열은 다른 자료구조의 좋은 부품으로 사용될 수 있다.
• 인덱스 를 가지며, 엘리먼트의 인덱스는 변경되지 않는다.
  • (= 현실세계의 주민번호, 학급에서 학생에게 부여하는 번호)
• 유관 데이터를 메모리에 순차적으로 (인덱스) 나열할 수 있다.
• 인덱스를 활용하여 빠르게 조회가 가능하다.
• cache hit 의 가능성이 커져서 성능에 큰 도움이 된다.
• 인덱스를 이용하여 데이터를 가져오려면 데이터에 대한 인덱스 값이 고정되어야 한다. (삭제된 엘리먼트의 공간이 그대로 남는다. -> 메모리의 낭비)

※배열의 한계

• 배열은 길이를 바꿀 수 없다. 가변 배열과 같이 길이가 변경 가능한 배열의 경우,
  • 기존의 배열은 그대로 두고,
  • 새로운 길이로 지정된 배열을 따로 할당 후 (메모리가 있는지 탐색 필요)
  • 데이터의 복사를 진행하고,
  • 기존의 배열을 삭제한다.
  • 총 3번의 작업 + 메모리 탐색 이 필요하기 때문에 리소스 낭비가 크다.
• 위와 같은 한계를 해결하기 위해서 linked list 자료형을 활용할 수 있다. (탐색, 할당, 복사, 삭제 등의 리소스 낭비가 없다.)
• 배열은 인덱스에 따라서 값을 유지하기 때문에, 엘리먼트가 삭제되어도 빈자리(null)가 남게 된다. (불필요한 메모리 차지)
• 조건문을 통해서 빈 엘리먼트를 제외할 수 있으나, 조건문을 많이 사용하는 것은 좋지 않다.
• 삭제한 데이터를 뒤에 위치한 엘리먼트로 메꾸면, 데이터가 순서에 따라서 빈틈없이 연속적으로 위치하며 이를 list(리스트) 라고 한다.
• 인덱스가 중요한 경우는 배열을 사용, 인덱스가 중요하지 않은 경우에는 리스트를 사용한다.

배열은 삭제된 데이터의 빈공간을 그대로 남겨둔다, 리스트는 빈공간을 채운다.

(출처: 생활코딩 - 배열)

---

■ 리스트 (List)

• 리스트는 배열이 가지고 있는 인덱스라는 장점을 버리고 대신 빈틈없는 데이터의 적재 라는 장점을 취한 데이터 스트럭쳐
• 리스트 자료구조의 핵심은 엘리먼트들 간의 순서. 따라서 리스트를 다른 말로는 시퀀스(sequence) 라고도 부른다. 즉 순서가 있는 데이터의 모임이 리스트이다.
• 리스트에서 인덱스는 몇 번째 데이터인가 정도의 의미를 가진다.
  • 배열(Array) 에서의 인덱스는 값에 대한 유일무이한 식별자
• 빈 엘리먼트는 허용하지 않는다.
• 순차성을 보장하지 못하기 때문에 spacial locality 보장이 되지 않아서 cash hit가 어렵다.
• 데이터 갯수가 확실하게 정해져 있고, 자주 사용된다면 array가 더 효율적이다.
• 리스트에 대한 효용은 어떤 언어를 사용하느냐에 따라서 달라진다. 특히 많은 언어가 리스트를 기본적으로 지원하기 때문에 리스트를 직접 구현하는 경우는 줄고 있다.

 

▷ LinkedList

• [LinkedList 구조]

 

• 자료의 주소 값으로 노드를 이용해 서로 연결되어 있는 구조를 갖는다.
• 즉, 메모리를 연속적으로 사용하지 않는다. 
• 순차적 접근방식이다. 즉, 특정 원소에 접근하기 위해서 처음부터 검색하면서 찾는다. 
• 동적으로 삽입, 삭제가 편하다.
• 원소를 삽입할 경우
  • 맨 앞 , 맨 뒤 삽입은 위치를 찾지 않아도 되서 시간 복잡도 O(1)이다.
  • 중간 삽입은 이전 노드와 다음 노드의 위치를 알고 있는 경우 시간 복잡도는 O(1)이다.
  • 하지만 탐색을 해야하는 경우 시간 복잡도 O(n)이다.
• 원소를 삭제할 경우
  • 삽입과 마찬가지로 맨 앞, 맨 뒤 삭제는 시간 복잡도 O(1)이다.
  • 중간 삭제는 시간 복잡도 O(n) 또는 O(1)이다. (삽입과 같음)
• 특정 위치에 있는 원소에 바로 접근이 불가능하다. (주소를 바로 알 수 없기 때문)
  • 원하는 원소를 찾기 위해서 최소 한 번은 리스트를 순회해야하기 때문에 시간 복잡도는 O(n)이다.
• 메모리는 새로운 노드가 추가될 때 (Runtime) Heap 영역에 할당한다.

 

▷ ArrayList

• 크기가 가변적이다.
• 내부적으로 배열을 사용하기 때문에(인덱스를 이용해서) 접근하는 것이 빠르다.
• add(), remove()를 통해 추가/삭제가 가능하다.
  • 데이터 추가/삭제 시 메모리를 재할당하기 때문에 속도가 배열보다 느리다.

(출처: 생활코딩 - 리스트)

 

※ ArrayList vs LinkedList

작업	ArrayList	LinkedList
탐색 get()	O(1)	O(n)
삽입 add()	O(1)	O(1) : 맨 앞, 맨 뒤   O(n) : 탐색을 통한 중간 삽입
삭제 remove()	O(n)	O(1) : 맨 앞, 맨 뒤  O(n) : 탐색을 통한 중간 삭제