Array vs Linked list

👀Array는 어떤 자료구조 ?

• 연관된 data를 메모리상에 연속적, 순차적(order)으로 미리 할당된 크기(fixed-size)만큼 저장하는 자료구조
• 장점: lookup과 append가 빠르다 👉 조회를 자주 해야되는 작업에 많이 쓴다.
• 단점: fixed-size의 특성상 선언 시 Array의 크기를 미리 정해야 한다 👉 메모리 낭비나 추가 overhead 발생할 수 있다.

Time complexity

접근(access) , 추가(append) 👉  O(1)       /      삽입(insertion), 삭제(deletion) , 검색(search) 👉  O(n)

 

Q) 예상보다 더 많은 data를 저장하느라 Array의 size를 넘어서게 됐다면, 어떻게 해결할 것인지?

기존의 size보다 더 큰 Array를 선언, 데이터를 옮겨 할당한다. 모든 데이터를 옮겼다면 기존 Array는 메모리에서 삭제한다.

👉 이런 방식으로 동적으로 배열의 크기를 조절하는 자료구조를 Dynamic Array라고 한다.

👀Dynamic Array는 어떤 자료구조 ?

• Array의 경우 fixed-size이므로 선언 시 설정한 size보다 많은 data가 추가되면 저장할 수 없다.
• 이에 반해 Dynamic Array는 저장공간이 가득 차게 되면 resize를 하여 유동적으로 size를 조절하여 데이터를 저장하는 자료구조
• Array의 fixed-size의 한계점을 보완하고자 고안된 자료구조 (size를 미리 고민할 필요가 없다)

- resizing 대표 방법 - doubling(2배 size 할당)

• 데이터를 추가(append O(1) )하다가 메모리 초과 시 기존 배열의 크기보다 두배 큰 배열 선언, 데이터를 일일이 옮기는(n개의 데이터를 일일이 옮겨야 하므로 ( O(n) ) 의 방법이다.

- 분할상환 시간복잡도 Amortized time Complexity

• Dynamic Array에 데이터를 추가할 때마다 O(1)   -  미리 선언된 size를 넘어서는 순간 resize - 일일이 데이터 옮기는 작업 O(n) 

대부분의 시간 ( O(1) ) , resize & 옮기는 과정  O(n) 가끔 발생  - 전체적인 시간복잡도 O(1) (amortized ( 분할된 ) ) 

약간 미분느낌쓰 ?

👀Linked List는 어떤 자료구조 ?

• node라는 구조체로 이루어져 있다.
• 물리적인 메모리상에서는 비연속적으로 저장된다.
• 하지만 구성하는 각각의 Node가 next Node의 address를 가리키기 때문에 논리적 연속성을 가진 자료구조
• 데이터 추가 되는 시점에 메모리를 할당하므로 메모리를 좀 더 효율적으로 사용할 수 있다.
• Next Address를 추가적으로 저장해야 하므로 데이터 하나당 차지하는 메모리가 더 커질 수 있다.

 

Time complexity

접근(access) , 검색(search) 👉  O(n)       /      삽입(insertion), 삭제(deletion) ,  👉  O(1)

 

🥸Array vs Linked list ?

Array는 메모리 상 연속적 / Linked list는 메모리 상에선 불연속이지만, 각각의 원소에 다음 원소의 메모리 주소값을 저장하여 논리적 연속성을 유지한다. 주된 차이점들은 메모리 구조에 기인한다. 메모리 구조의 차이로 인해 operation 구현방법이 다르고 시간복잡도도 다르다.

 

그러므로 각 시간복잡도도 다르다. 조회의 경우 Array는 O(1) , Linked list는O(n)  삽입, 삭제는 Array O(n) , Linked list O(1) 이다.

얼마만큼의 데이터를 저장할지 미리 알고, 조회를 많이한다 ? + ( 데이터를 반복문을 통해 빠르게 순회할 때 ) 👉 Array

몇개의 데이터를 저장할 지 불확실하고 삽입 삭제가 잦다? +( 조회 작업을 별로 하지 않을 때 ) 👉 Linked list

메모리  할당(memory allocation) 은 언제? 어느 영역?

Array는 컴파일 단계에서 일어난다. 이를 정적 메모리 할당 ( Static Memory Allocation )이라 한다. 이 경우 Stack memory영역에 할당된다.

Linked list의 경우 런타임 단계에서 새로운 node가 추가될 떄마다 memory allocation이 일어난다. 이를 동적 메모리 할당 ( Dynamic Memory Allocation) 이라고 부른다. Heap 메모리 영역에 할당된다.