어레이 리스트, 링크드 리스트

 

• Array는 연속된 메모리 공간에 존재하고 Linked List는 메모리 상에서 떨어져 있는 데이터들이 앞의 데이터와 뒤의 데이터를 기억하는 형태로 존재한다.
• Array에 저장되어 있는 데이터를 조회할 때는 O(1)로 가능하지만 Linked List는 O(N)이 소요된다.
• Array에 데이터 추가 및 삭제할 때는 O(N)이 소요되지만 Linked List는 O(1)로 가능하다.
• 추가적으로 Array는 컴파일 과정에서 메모리가 할당되는 정적 메모리 할당인 반면 Linked List는 런타임 환경에서 메모리가 할당되는 동적 메모리 할당이다.
• 또한 배열은 Stack 영역에 메모리 할당이 되고, Linked List는 Heap 영역에 할당이 된다.