Array 와 List

Array 

연관된 data를 메모리상에 연속적이며 순차적으로 미리 할당된 크기만큼 저장하는 자료구조이다

• 고정된 저장 공간을 가지고 있다
• 순차적인 데이터를 저장한다.

이 두가지를 통해 Array의 다양한 특징을 알아보자

고정된 저장 공간을 가지고 있다.

• 예상보다 적은 데이터를 가지고 있다면 남은 메모리 공간이 낭비가 된다
• 예상보다 많은 데이터를 가지고 있다면 공간을 변형 시킬수 없기 때문에 데이터를 새로 생성해서 사용해야한다.

순차적인 데이터를 저장한다

• 인덱스를 기준으로 데이터를 저장하게 되면서 조회(lookup)이 O(1)이라는 굉장히 빠른 시간복잡도를 가진다. 
  • 내가 어떤 인덱스에 무슨 데이터가 저장되어있는지 확인하려면 첫번째 인덱스에서 추가적인 횟수만 더해서 확인하면 되기 때문이다.
• 반대로 삽입, 삭제, 탐색에는 O(n)이라는 단점을 보인다 
  • 순차적으로 데이터를 저장해야하기 때문에 중간의 데이터가 빠지거나 지워지면 데이터들을 shift해주어야한다
  • 또한 탐색은 내가 원하는 데이터가 지정되면 그 데이터를 찾기위해 순차적으로 찾아보야한다.

 

Dynamic Array

Array와는 다르게 Dynamic Array는 저장공간이 가득 차면 resize를 하여 유동적으로 size를 조절하여 데이터를 저장하는 자료구조이다

 

글만 봐도 딱 알 수 있다. Array의 메모리 공간의 이슈를 막기 위해 나온것이다. Dynamic Array의 가장 큰 차이점은 size를 자동적으로 resize한다는 것인데 기존에 할당시킨 memory를 초과하게 되면, size를 늘린 배열을 선언하고 그 곳으로 모든 데이터를 옮김으로써 늘어난 크기의 size를 가진 배열이 된다. 이를 resize라고 하고 이로써 새로운 data를 저장할 수 있게되는것이다. 그렇다면 resizing을 하는 방법은 무엇이 있을까?

 

Doubling

resizing을 하는 가장 대표적인 방법이다. 단어 그대로 데이터를 추가하는 과정에 할당된 데이터의 크기를 넘기면 메모리 할당량을 기존에 사용하던 배열의 크기에서 2배로 늘려 새로 만들고 거기에 데이터를 옮겨담는다.

 

여기서 관점은 append의 시간 복잡도이다 

1. 데이터를 추가하는것은 배열의 가장 마지막에 추가하는 O(1)이 걸린다.

2. 데이터를 새로운 메모리에 옮기는 과정은 O(n)의 시간 복잡도를 가지기 때문이다.

그럼 도데체 append의 정확한 시간 복잡도는 무엇일까? append의 과정을 넓게 보자 그러면 인덱스를 추가하는 작업이 압도적으로 많고 그중 정말 조금씩 이뤄지는것이 데이터를 옮기는 과정일것이다. 그래서 전체적인 과정을 기준으로 봤을때는 O(n)의 시간복잡도가 O(1)에 분담되어 평균화가 되고 O(1)에 훨씬 가깝다 하고 할수 있다. 이를 정확히 표현할때는 Amotized O(1) 이라고 한다. 

 

 

List (Array List, Linked List)

List는 Array의 단점을 보안하기 위해 나왔다 볼수 있다 List를 설명할때는 Linked List를 대표적으로 많이 설명한다

1. 데이터를 추가하는 시점에서 메모리를 할당하기 때문에 메모리를 좀 더 효율적으로 사용할 수 있다.

2. List는 Node라는 구조체로 이루어져있다. Node는 데이터 값과 다음 node의 address를 저장한다.

물리적인 메모리상에서는 비연속적으로 저장되지만 node를 가리키는 Node address 덕분에 논리적 연속성을 가졌다 라고 말할수 있다

 

list는 메모리에 무작위로 데이터를 저장하지만 데이터에 본인 다음으로 오는 주소값을 가리키다 마지막엔 null을 가리킨다.

 

논리적 연속성

각 node들은 next address정보를 가지고 있기 때문에 논리적으로 연속성을 유지하면서 연결되어있다.

Array의 경우는 연속성을 유지하기위해 물리적 메모리 상에서 순차적으로 저장(인덱스)하는 방법을 사용했다

List는 메모리에서 연속성을 유지하지 않아도 되기 때문에 메모리 사용이 좀 더 자유롭다 하지만 naxt address를 저장하기 위해 약 4byte의 메모리를 더 차지하게 된다.

 

위에서 부터 계속 해서 말하지만 List와 Array의 가장 큰 차이점은 메모리 할당 능력이라고 할수있다

Array는 연속적, List는 불연속적으로 저장하면서 서로의 operation 구현 방법 또한 다르고 시간 복잡도가 다르다

• 조회(Lookup)

Array는 메모리상에서 연속적으로 데이터를 저장하였기 때문에 저장된 데이터에 즉시 접근(random Acceess)이 가능하다

List는 메모리 상에서 불연속적으로 데이터를 저장하기 때문에 순차 접근만이 가능하다(Sequence Access)

Array는 O(1)의 시간 복잡도가 걸리고, List는 O(n)의 시간 복잡도가 걸린다.

 

• 삽입 / 삭제

Array의 경우 맨 마지막 원소를 추가 / 삭제하면 시간 복잡도가 O(1)이다. 하지만 맨 마지막 원소가 아닌 중간에 있는 원소를 삽입 / 삭제한다면 해당 원소보다 큰 인덱스의 원소들을 한칸씩 shift 해줘야하는 비용이 발생한다. 따라서 이 경우에는 시간 복잡도가 O(n)이다.

 

List는 어느 원소가 추가 / 삭제가 되더라도 Node에서 다음 주소를 가리키는 부분만 다른 주소값으로 변경하면 되기 때문에 shift의 필요가 없다. 즉, O(1)의 시간 복잡도를 가지게 된다.

 

• memory

Array - 데이터 접근과 append가 빠르다는 장점이 있다. 하지만 메모리의 낭비가 있다는 단점또한 존재한다는 것인데 배열은 선언시 fixed size를 설정하여 메모리를 할당합니다. 즉, 데이터가 저장되어 있지 않더라도 메모리를 차지하고 있기 때문에 메모리 낭비가 발생한다.

 

List - runtime중에서도 size를 늘리고 줄일수 있다. 그래서 initial size를 고민할 필요가 줄어들고, 필요한 만큼 memory allocation을 하여 메모리 낭비가 없다.

 

그럼 List를 이용한 두개를 알아보자 

1. Array List
   • 기본적으로 배열을 사용한다. 차이점은 초반에 크기를 정해줄 필요가 없다는것이다.
   • index가 있어서 무작위 접근이 가능하다
   • Array의 장점과 단점을 그대로 가지고 있다. = 조회가 빠르다 하지만 데이터의 추가와 삭제는 느리다
   • 하지만 크기를 정해놓고 사용하는 경우가 있는데 이유는 데이터를 끝에 추가할때 Array와는 다르게 ArrayList의 크기를 키운후 새로운 공간에 더 큰 메모리를 잡은 후 기존의 ArrayList의 요소를 복사하고 원소를 추가한다.(Dynamic Array와 비슷하다 보면된다) 그래서 시간이 오래걸린다. 이를 방지하기 위해 지정하는 경우가 있다
2. Linked List ( 평균적으로 Array와 List의 차이는 여기서 나온다.)
   • 메모리 낭비가 있을수있다.Array는 이를 방지하기 위해 범위를 정하는 경우가 많다.
   • 여기서 List의 특징의 대부분이 나타난다.

---

정리

1. Array는 메모리에 연속적으로 데이터를 저장해두고 List는 연속적이진 않지만 다음 주소를 적어두면서 논리적 연속성을 유지한다
2. 각 operation의 시간 복잡도가 다르다. 데이터 조회는 Array가 O(1), List가 O(n)이고, 삽입과 삭제는 Array가 O(n), List가 O(n)을 가진다.
3. Array를 사용해야 할때
   1. 조회 작업을 자주 하는 데이터일때
   2. Array를 선언할 당시에 데이터의 갯수를 미리 알고 있을때
   3. 데이터를 반복문을 통해서 빠르게 순회할때
   4. 메모리를 적게 쓰는게 중요한 상황일때, List보다 Array가 메모리를 적게 차지하기 때문에 미리 들어올 데이터의 양을 알고만 있다면 Array가 메모리를 좀 더 효율적으로 사용한다.
4. List를 사용해야 할때
   1. 데이터의 삽입과 삭제가 잦을때
   2. 얼마만큼의 데이터가 들어올지 예상하기 힘들때
   3. 조회 작업이 많지 않은 경우
5. 그리고 잠깐 설명했지만 ArrayList는 Array와 다른점이 너무 없다. 굳이 차이점이 바로 길이를 조정 할 수 있는가 없는가 정도의 차이이다. 그리고 나름의 List의 특징을 가지고 있기 때문에 가변적인 배열로 인해 마지막에 추가 하는것의 시간 복잡도가 늘어나면서 Array와 ArrayList를 잘 골라 사용해야 한다.