특정 크기만큼 연속된 메모리 공간에 데이터를 저장하는 자료구조이다. 연속된 공간에 데이터들이 나열되어 있기 때문에 처음 주소만 알면 다른 위치도 쉽게 알 수 있다. 따라서 배열은 랜덤하게 접근하는 것이 좋다. 하지만, 데이터를 빈번하게 삭제하거나 추가할 때에는 효율적이지 못하다. 데이터를 중간에 추가하려고 한다면 추가하려는 자리를 비우고 뒤에 있는 데이터들을 한 칸씩 뒤로 밀어야 하기 때문이다.
배열과 다르게 연속된 메모리 공간에 저장되어 있지 않다. 각각의 데이터가 메모리 공간상에 고유한 노드로 존재한다. 그리고 이 노드는 자신의 앞에 있는 데이터와 뒤에 있는 데이터에 대한 주소를 기억하고 있다.
✔ Big-O Notation(빅오 표기법)에 대해서 더 공부하기!