[자료구조] Array vs Linked list

728x90

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

지 않지만 각각의 Node가 다음 메모리 주소값을 저장하고 있으므로 논리적으론 연속적이다.

그리고 데이터 조회는 Array의 경우 O(1) (random access), Linked List는 O(n) (순차 접근)의 시간복잡도를 갖습니다.

삽입/삭제의 경우는 Array는 O(n), Linked List는 O(1)의 시간 복잡도를 갖습니다.

따라서 얼만큼의 데이터를 저장할지 예상이 되고 조회를 많이 한다면 Array를 사용하고
얼만큼의 데이터를 저장할지 예상이 되지 않고 삽입/삭제가 많다면 Linked List를 사용하는 것이 유리

Array는 compile 시간에 Stack 메모리에 할당

Linked List는 runtime 시간에 Heap 메모리에 할당

[자료구조] Array

Array란?연관된 데이터들을 모아서 메모리상에 연속적이며 순차적으로 미리 할당된 크기만큼 저장하는 자료구조Array의 특징은 위에서 설명했듯이 - 고정된 저장 공간- 순차적인 데이터 저장 그

changbroblog.tistory.com

[자료구조] Linked List

Linked List란? (tree와 graph를 구현할때 자주 사용)Linked List는 Node라는 구조체로 이루어져 있고 Node는 데이터 값과 다음 Node의 주소값으로 이루어져 있다.물리적인 메모리상으로는 비연속적으로 저장

changbroblog.tistory.com

뜨거운 개발자