[3] Array vs LinkedList

* 저의 면접을 대비해서 여러 사이트를 참고하여 제가 이해하기 쉽게 정리한 것입니다.

* 혹시라도 문제가 된다면 비공개조치 하겠습니다.

* 레퍼런스는 항상 표기 하겠습니다.

---

---

이번엔 배열과 리스트를 한 번 파헤쳐보죠!

아래 내용은 모두 [_Jbee]님 블로그를 보고 요약했습니다.

1. 배열(Array)이란?

- 가장 기본적인 자료구조로, 많은 데이터를 하나의 이름으로 Groupping하여 관리하기 위한 목적으로 사용됩니다.

int arr[2] = {0, 1};

장점

- 논리적 저장 순서와 물리적 저장 순서가 일치합니다.

ㄴ 그래서 인덱스에 해당하는 원소에 빠르게 접근이 가능합니다.

ㄴ 시간은 O(1)밖에 걸리지 않아요!

ㄴ 이를 'Random Access가 가능하다' 라고 합니다.

- 심플하다.

단점

- 삽입, 삭제 과정이 굉장히 비 효율적입니다. ( O(n) )

ㄴ 왜냐구요? 우선 삽입할 위치를 찾거나, 삭제할 원소를 찾는데 O(1)이 걸립니다.

ㄴ 해당 위치에 삽입하려면, 해당 인덱스로부터 뒤로 늘어져있는 모든 원소들을 뒤로 한 칸씩 밀어야합니다.

ㄴ 반대로 삭제를 하게 되면, 해당 위치를 기준으로 뒤로 늘어져있는 모든 원소들을 앞으로 밀착시켜야 합니다.

ㄴ 위의 두 과정에서, 땡기고 미는 과정에서 Cost가 발생하는데, 그 시간이 O(n)을 갖습니다.

ㄴ 배열의 가장 큰 특징인 '연속성(Sequential)'이 깨지게 됩니다.

- 초기에 배열 크기를 지정해야 합니다

ㄴ 물론 나중에 동적할당으로 크기를 조정할 수도 있지만

ㄴ 삽입, 삭제를 자유자재로 하기에는 번거롭다는 함정이 있죠!(그래서 전 맨날 벡터만 씁니다)

물론 이러한 단점을 잡아주는 동적 배열도 있습니다.

- 하지만 지금은 배열과 리스트를 비교하는 중이니, 동적 배열은 맨 밑에서 설명하도록 하죠!

2. Linked List란?

- Array의 단점을 모두 보완해줄 흑기사! 그가 바로 Linked List입니다.

- [데이터, next Pointer]의 한 묶음을 노드로 갖고, 이 노드들 끼리 순차적(Seqeuntial)으로 연결되어 있는 방식의 자료구조입니다.

장점

- 크기가 고정되어 있지 않아서 삽입, 삭제가 용이합니다. ( O(1) )

ㄴ 배열과는 달리, 포인터만 갖고 요리조리 바꿔주면 되니까 밀당(?)을 할 필요가 없죠!

- 필요할 때마다 그 크기를 늘리거나, 줄일 수 있어서 메모리의 낭비가 배열보단 덜합니다.

단점

- 배열에 비해 복잡하고, 구현이 어렵습니다.

ㄴ 배열은 한 공간 안에 Element만 들어가있지만

ㄴ 리스트는 한 공간안에 Element와 자신의 다음 리스트를 가리키는 포인터가 노드형태로 저장되어 있기 때문이죠!

- 탐색 속도가 느리다 ( O(n) )

ㄴ 예를 들어, 네 번째 인덱스에 있는 원소를 찾으려면

ㄴ 0번째 인덱스부터 오른쪽으로 4번 이동해야 찾을 수 있습니다.

ㄴ 이를 일반화 시키면, n번째 값을 찾으려면 0번째 인덱스부터 n번 움직여야 한다는 소리죠.

여기서 생기는 의문

Q) 배열도 삽입, 삭제에 O(n)이고, 리스트도 O(n)인데 뭔 차이죠?

A) Tree를 배열로 구현해보시고, 리스트로 구현해보세요! 그곳에 답이 있습니다.

종류가 여러가지라던데...

1) Singly Linked List (단일 연결 리스트)

2) Doubly Linked List (이중 연결 리스트)

3) Circular Linked List (원형 연결 리스트)

<그림 출처 : [게임 개발자 블로그], [CodeGroundNote]>

<시간 복잡도 출처 : 위키피디아>

자세한 구현은 알고리즘 파트에서 하는걸로 하고, 여기는 면접 전용이니까! 개념적으로 차이를 제대로 알아두는데 의의를 두고 있습니다.

그럼 이제, 동적 배열에 대해서 한 번 알아볼까요?

동적 배열(Dynamic Array)

- 배열의 두 가지 단점을 보완해줄 수 있는 또 한 가지의 방법, 바로 동적 배열입니다.

- 자료의 크기가 변함에 따라, 배열의 크기가 유동적으로 늘어나는 자료 구조 입니다.

- 기존 배열의 장점인 Searching Time이 O(1)인 장점은 그대로 유지하면서, 메모리의 낭비를 최소화시켜줍니다!

- 윤빵꾸님의 블로그를 참고하여 정리하였습니다.

어떻게 동작하나요?

<출처 : [윤빵꾸]님 블로그>

1) 처음에 동적 배열이 생성되었을 때, 배열에 일정 크기를 할당하고, 원소를 추가합니다.

2) 원소를 계속 추가해 나가다가 배열이 꽉차게 되면, 크기를 2배 늘린 배열에 기존 배열을 복사합니다.

3) 반복합니다.

그럼 여기서 의문이 생깁니다. 왜 하필이면 2배로 늘리느냐?

- 그 이유는, 소스코드 구현에서 핵심적으로 사용되는 확장 method의 수행 시간을 평균적으로 O(1)로 만들기 위해서라고 합니다.

확장 Method가 뭘 하길래?

- 확장 Method는 할당 받은 배열의 크기가 여유로울때는 원소를 추가하는 역할만하기 때문에 O(1)의 수행시간을 갖습니다.

- 그러나 크기가 꽉 찼을때에는, 배열의 크기를 늘리고, n개 만큼의 배열을 복사하는 수행도 동반하기 때문에 O(n)의 수행시간을 갖습니다.

- 자세한 계산은 [윤빵꾸님의 블로그]를 참고해주세요! 설명이 정말 대박입니다.

이제 동적 배열이 뭔지 알게됐습니다. 근데 이거 일일이 다 구현하기 귀찮겠죠?

그래서 자바는 표준 라이브러리에서 동적 배열로써 ArrayList를 제공합니다.

꼬리에 꼬리를 무는 질문... ArrayList랑 Vector랑 뭔차이야?

- 이 질문은 제가 Vector를 즐겨 썼기 때문에, ArrayList랑 차이점이 진짜 뭔지 궁금해서 추가해봤습니다.

- 동작이 둘이 똑같거든요.... 도대체 뭔 차이지? 싶었습니다.

차이점

1) 동기화 : Vector는 동기화 되지만, ArrayList는 동기화되지 않습니다.

2) 데이터 증가 : ArrayList와 벡터 요소는 모두 배열로 저장되지만, 벡터의 기본 크기는 10이고 ArrayList는 기본 크기가 없습니다.

3) 요소 이동 : ArrayList는 인덱스로 접근할 수 있습니다만, 벡터의 경우 이터레이터(Iterator)를 필요로 합니다.

[이 사이트]를 참고하여 작성하였습니다.

오늘은 차이가 저런게 있구나 정도만 알고, 다른 포스팅에서 더 자세히 다루도록 하겠습니다. OS적 요소도 들어가있거든요!