정적 자료구조
배열을 만들기 위해서는 미리 크기를 정해놔야 한다. 크기를 정해놓고 배열을 만들게 되면 딱 그 크기만큼 연속된 메모리 주소를 할당 받는다.
따라서, 한번 크기를 정해 놓으면 크기 수정이 불가
하고 배열 크기 이상의 데이터를 저장할 수 없다.
크기를 변경하려면 새로운 배열을 생성하고 이전 배열의 데이터를 복사해야한다.
동적 자료구조
동적으로 크기가 조절될 수 있다.
그래서 요소를 추가하나 삭제할 때마다 크기가 자동으로 조절되기 때문에 크기를 직접 지정할 필요가 없다.
노드가 존재하는데, 그 노드에는 저장된 데이터 값과 다음 데이터가 있는 메모리 주소(단일 연결리스트의 경우)를 가지고 있다.
따라서 데이터들이 배열처럼 연속적으로 메모리에 저장되어 있지 않고 서로 떨어져 있어도 선형구조
로 데이터를 저장할 수 있다.
요소들을 연속적으로 저장하므로 메모리 상에서 효율적으로 관리된다.
하지만 크기가 고정되어 있기 때문에 미리 큰 크기의 배열을 생성해야 할 수도 있다.
각 요소가 독립적인 노드로 구성되어 있으므로 포인터를 사용하여 연결되어 있다.
이로 인해 추가적인 메모리 오버헤드가 발생할 수 있지만, 동적 크기 조절이 가능하다는 장점이 있다.
인덱스를 통해 요소에 빠르게 접근할 수 있다.
인덱스를 알고있다면 O(1) 시간에 접근할 수 있다.
특정 요소에 접근하려면 처음부터 해당 요소까지 순차적으로 탐색해야 한다.
따라서 특정 요소에 접근하는 데는 O(n) 시간이 걸린다.
배열의 크기가 고정되어 있기 때문에 요소를 추가하거나 삭제할 때 다른 요소들을 이동시켜야 한다.
따라서 요소를 추가하거나 삭제하는 데에는 O(n) 시간이 걸린다.
요소를 추가하거나 삭제할 때마다 단순히 노드의 연결을 조정하면 된다.
따라서 요소를 추가하거나 삭제하는 데에는 일반적으로 O(1) 시간이 걸린다. (단, 리스트 앞이나 중간에 요소를 추가/삭제하는 경우 노드를 찾는 시간이 추가적으로 필요할 수 있다.)
연속적으로 메모리를 할당받아서 데이터를 저장하기 때문에 탐색은 굉장히 빠르다. 대신에 데이터 추가, 삭제로부터 절대 자유로울 수 없다.
데이터의 접근, 탐색이 중요하다면 배열을 사용
노드가 있기 때문에 데이터의 추가, 삭제로부터 자유로워질 수 있었지만 대신 탐색이 느려졌다.
데이터의 추가, 삭제가 중요하다면 연결리스트를 사용
Array는 연속된 메모리 공간에 존재하고 Linked List는 메모리 상에서 떨어져 있는 데이터들이 앞의 데이터와 뒤의 데이터를 기억하는 형태로 존재한다.
Array에 저장되어 있는 데이터를 조회할 때는 O(1)로 가능하지만 Linked List는 O(N)이 소요된다.
Array에 데이터 추가 및 삭제할 때는 O(N)이 소요되지만 Linked List는 O(1)로 가능하다.
추가적으로 Array는 컴파일 과정에서 메모리가 할당되는 정적 메모리 할당인 반면 Linked List는 런타임 환경에서 메모리가 할당되는 동적 메모리 할당이다.
또한 배열은 Stack 영역에 메모리 할당이 되고, Linked List는 Heap 영역에 할당이 된다.