Portfolio

☝️ Array vs Linked List Array Dynamic Array Linked List ⏱ 시간 복잡도 Array vs Linked List ✌️ ArrayList vs LinkedList ArrayList란?LinkedList란?ArrayList vs LinkedList ⏱ 시간 복잡도 🔖 참고 사이트

☝️ Array vs Linked List

💡 Array 관련된 질문은 높은 확률로 Linked List의 비교 질문으로 이어진다!

가장 큰 차이점은 메모리에 저장되는 방식 & opration의 연산속도(time complexity) 입니다.

Array


int array[4] = {1, 2, 3, 4}

메모리 저장 방식

고정된 저장 공간(fixed-size)
순차적인 데이터 저장(order)

→ 메모리상에 연속적이며 순차적으로 저장한다.

Array - operation들의 time complexity

조회(lookup) : O(1) - random access


// ✨ 순차적이기 때문에 
// array[0]의 메모리 주소에서 몇번째까지 가야되는지 
// 단번에 계산해서 갈 수 있다.
array[3]

마지막 인덱스 추가(append) : O(1)
마지막 인덱스 삭제 : O(1)
삽입(insert) : O(n) → 중간에 삽입을 하면, 그 뒤에 것들을 모두 뒤로 밀어야 됨.
삭제(delete) : O(n) → 중간에 있는 녀석을 삭제하면, 그 뒤에 것들을 모두 앞으로 당겨야 됨.
탐색(search) : O(n) → 어떤 숫자가 몇번째 있는지? → 순차적으로 검색할 수 밖에 없다!

장점

lookup과 append가 빠르다.

→ 조회를 자주해야 하는 작업에서는 Array 자료구조를 많이 씁니다.

단점

fixed-size 특성상 선언시 크기를 미리 정해야 된다!

→ 메모리 낭비나 추가적인 overhead가 발생할 수 있습니다.

Dynamic Array

size를 자동적으로 resizing을 하는 Array 이다.

data를 계속 추가하다가 기존 할당된 memory를 초과하게 되면

size를 늘린 배열을 선언하고 이곳으로 데이터를 옮긴다. (대표적으로 2배 size로 늘리는 doubling이 있다.)

Doubling

resize의 대표적인 방법
append : O(1)
resizing : O(n)

분할상환 시간복잡도 Amortized time complexity

추가는 O(1), resize는 O(n) → 🤔 결과적으로 append의 시간복잡도는?

→ resize는 아주 가끔 발생하기 때문에 O(1)이다. (정확히는 amortized O(1))

🤔 Dynamic Array를 Linked List와 비교하여 장단점을 설명하시오.

장점은?

데이터 접근과 할당이 빠릅니다. index 접근하는 방법이 [배열 첫 데이터의 주소] + [offset]으로 이루어 졌기 때문. (random access)
맨 뒤에 데이터를 추가하거나 삭제하는 것이 상대적으로 빠릅니다.

단점은?

중간에 있는 data의 insert or remove인 경우 속도가 느립니다. 메모리상에서 연속적으로 데이터들이 저장되기 때문에 추가, 삭제하는 경우에는 data들을 모두 한칸씩 shift 해야되기 때문임.
resize 해야 될 때, 예상치 못한 현저히 낮은 performance가 발생.
resize에 시간이 많이 걸리므로 필요한 것 이상의 memory 공간을 할당 받습니다.

그래서 낭비되는 메모리 공간이 발생합니다.

Linked List

Node라는 구조체로 이루어져 있음 (Node: 데이터 값과 다음 Node의 address를 가지고 있음)

물리적인 메모리상에서는 비연속적으로 저장 되지만, 각각의 노드가 연결되어 있으므로 논리적인 연속성을 가지는 자료구조.

데이터가 추가되는 시점에서 메모리를 할당 → 메모리를 효율적으로 사용 가능!

노드에서 Next Address를 추가적으로 저장해야 되기 때문에, 데이터 하나당 차지하는 메모리가 더 커짐

⏱ 시간 복잡도

ㅤ	Linked List
access	O(n)
search	O(n)
insert	O(1)
delete	O(1)

Array vs Linked List

Q. 어느 상황에서 Array 보다 Linked List를 사용해야 되는가?

O(1)으로 삽입/삭제 자주 하는 경우

얼마만큼의 데이터가 들어올지 예측 안될때

조회 작업을 자주 안하는 경우

Q. 어느 상황에서 Linked List 보다 Array를 사용해야 되는가?

조회 작업을 자주 하는 경우

데이터 수가 예측 가능할 때

메모리를 적게 쓰는게 중요한 상황인 경우, 미리 들어올 데이터의 양만 알고 있다면 Array가 더 메모리를 효육적으로 사용!

Q. Array와 Linked List의 memory allocation은 언제 일어나고, 메모리의 어느 영역을 할당 받는가?

Array

compile 단계에서 발생 (Static Memory Allocation)
Stack 메모리에 할당 됨

Linked List

runtime 단계에서 새로운 노드가 추가 될 때 발생 (Dynamic Memory Allocation)
Heap 메모리 영역에 할당 됨

✌️ ArrayList vs LinkedList

ArrayList란?

추가 했을 때, 배열이 동적으로 늘어나는 것이 X → 더 큰 용량의 배열을 만들어 옮기는 작업을 함

초기 용량을 설정하는 것을 추천! 👍

기본 설정이 10개 이므로 초기 용량을 산정하고 지정하는것이 좋다.


// ✨ 기본 초기 용량
private static final int DEFAULT_CAPACITY = 10;

LinkedList란?

ArrayList vs LinkedList

순차적으로 추가/삭제 하는 경우에는 ArrayList

→ ArrayList의 재배치가 필요하지 않기 때문에 상당히 빠름

중간 데이터를 추가/삭제 하는 경우에는 LinkedList

→ 각 요소간의 연결만 변경해주면 되기 때문에 처리속도가 빠름

But.. ArrayList는 각 요소를 재배치하고 추가할 공간을 확보 또는 빈 공간을 채워야 되므로 느림

⏱ 시간 복잡도

ㅤ	메소드	ArrayList	Linked List
add at last index	add()	O(1)	O(1)
add at given index	add(index, value)	O(N)	O(1)
remove by index	remove(index)	O(N)	O(1)
remove by value	remove(value)	O(N)	O(1)
get by index	get(index)	O(1)	O(N)
search by value	indexOf(value)	O(N)	O(N)