Array / Linked list

💡 Array vs Liked list

Array는 메모리 상에서 연속적으로 데이터를 저장하는 자료구조이다

Linked List는 메모리상에서는 연속적이지 않지만, 논리적 연속성을 유지한다

그래서 각 operation의 시간복잡도가 다르다.

operation	Array time complexity	Linked List time complexity
access	O(1)	O(n)
search	O(1)	O(n)
insertion	O(n)	O(1)
deletion	O(n)	O(1)

유리한 사용방법
Array - 얼마만큼의 데이터를 저장할지 미리 알고있고, 조회가 잦다, 메모리를 적게 사용하는게 중요하다

Linked list - 몇개의 데이터를 저장할 지 불확실하고 삽입 삭제가 잦다

---

Array vs Linked list

💡 조회(lookup)

Array는 메모리상에 연속적으로 데이터를 저장하기 때문에

저장된 데이터에 즉시접근(radom access O(1))할 수 있음

반면에 Linked List는 메모리에 불연속적인 데이터 저장 방법을 택하여

순차 접근(sequetial Access)만이 가능, 즉 특정 index의 데이터를 조회하기 위해 O(n)의 시간이 걸리게 됨

💡 삽입/삭제(insert/delete)

Array의 경우 맨 마지막 원소를 추가/삭제하면 시간복잡도가 O(1)이다

하지만 맨 마지막 원소가 아닌 중간에 있는 원소를 삽입/삭제하면

해당 원소보다 큰 인덱스의 원소들을 한 칸씩 shift 해줘야 하는 비용이 발생함

따라서 이 경우에는 시간복잡도가 O(n)이 됨

Linked List의 경우 어느 원소를 추가/삭제 하더라도

node에 Next Address의 수정만이 일어나기 때문에 shift할 필요 없이 O(1)임

하지만 Linked list의 경우 추가/삭제를 하려는 index까지 도달하는데

O(n)의 시간이 걸리기 때문에 실직적으로 Linked List도 추가/삭제 시에

O(n)의 시간이 걸린다고 볼 수 있음

Memory

Array의 주된 장점은 데이터 접근과 append가 빠르다는 것

하지만 메모리 낭비라는 단점이 있다

배열은 선언시에 fixed size를 설정하여 메모리 할당을 해줌

즉 데이터가 저장되지 않더라도 메모리를 선점하고 있기 때문이다

이와 반면에 Linked List는 runtime중에도 size를 늘리고 줄일 수 있다

따라서 initial size를 고민할 필요 없고,

필요한 만큼 memorry allocation을 하여 메모리 낭비가 없다

반면에 Linked List는 value외에 Next Address를 추가로 저장하기 때문에

데이터 값이 Array보다 무겁다

memory allocation

• Array

compile 단계에서 (미리 fixed-size 선언)

memory allocation이 일어난다 이를 Static Memory Allocation 이라함

이 경우 Stack memory영역에 할당이 됨

• Linked list

runtime단계에서 새로운 node가 추가되는 경우 memory allocation이 일어나며

이를 Dynamic Memory Allocation이라고 부른다

즉 사용자의 동적 할당이 가능하기 때문에 Heap메모리 영역에 할당이 된다