배열(Array) / 연결리스트(Linked List)

	Array	Linked List
저장방식	요소들이 인접한 메모리 위치에 저장된다.	요소들이 메모리 어딘가에 저장되며, 새로운 요소의 주소는 Linked List의 이전 노드(Node)에 저장된다.
종류	일차원배열, 이차원배열, 다차원배열	단일 연결 리스트(Singly Linked List), 이중 연결 리스트(Doubly Linked List), 다중 연결 리스트(Multiply Linked List), 원형 연결 리스트(Circular Linked List)
크기	Array의 크기는 반드시 배열 선언 시점에 지정되어야 한다.	LinkedList의 크기는 새로운 요소가 추가될 때, runtime 시점에서 크기가 커질 수 있다.
메모리 할당	Array가 선언되자마자 Compile 시점에 Heap 영역에 메모리가 할당된다. (Static Memory Allocation)	세로운 노드가 추가될때 runtime 시점에 Heap 영역에 메모리가 할당된다. (Dynamic Memory Allocation)
요소 접근	Random Access를 지원한다. (index를 통해 요소에 직접 접근 가능, O(1))	Sequential Access를 지원한다. (요소에 접근할 때, 처음부터 순차적으로 접근해야 한다, O(N))
삽입 / 삭제	index로 접근 후 삽입 / 삭제(O(1)) + 전체 배열 요소를 Shift(O(N))	삽입하려는 위치에 접근 후 삽입 / 삭제(O(N)) 만약, 맨 앞이나 뒤에 삽입 / 삭제 시, O(1)
정리	데이터 접근이 주 업무일 경우 사용	데이터 수정이 주 업무일 경우 사용