🐰 크기
배열
-
정적 자료구조 -
배열을 만들기 위해서는 미리 크기를 정해놔야 한다. 크기를 정해놓고 배열을 만들게 되면 딱 그 크기만큼 연속된 메모리 주소를 할당 받는다.
-
따라서, 한번 크기를 정해 놓으면
크기 수정이 불가하고배열 크기 이상의 데이터를 저장할 수 없다. -
크기를 변경하려면 새로운 배열을 생성하고 이전 배열의 데이터를 복사해야한다.
연결 리스트
-
동적 자료구조 -
동적으로 크기가 조절될 수 있다.
-
그래서 요소를 추가하나 삭제할 때마다 크기가 자동으로 조절되기 때문에 크기를 직접 지정할 필요가 없다.
-
노드가 존재하는데, 그 노드에는 저장된 데이터 값과 다음 데이터가 있는 메모리 주소(단일 연결리스트의 경우)를 가지고 있다.
-
따라서 데이터들이 배열처럼 연속적으로 메모리에 저장되어 있지 않고 서로 떨어져 있어도
선형구조로 데이터를 저장할 수 있다.
🐰 메모리 사용
배열
-
요소들을 연속적으로 저장하므로 메모리 상에서 효율적으로 관리된다.
-
하지만 크기가 고정되어 있기 때문에 미리 큰 크기의 배열을 생성해야 할 수도 있다.
연결 리스트
-
각 요소가 독립적인 노드로 구성되어 있으므로 포인터를 사용하여 연결되어 있다.
-
이로 인해 추가적인 메모리 오버헤드가 발생할 수 있지만, 동적 크기 조절이 가능하다는 장점이 있다.
🐰 접근 시간
배열
-
인덱스를 통해 요소에 빠르게 접근할 수 있다.
-
인덱스를 알고있다면 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 영역에 할당이 된다.
정리
- 배열은 정적 자료구조로, 크기를 미리 정해놓고 연속된 메모리에 요소들을 저장합니다. 이로 인해 메모리 상에서 효율적으로 관리되며, 인덱스를 통해 빠르게 요소에 접근할 수 있습니다. 또한 요소를 추가하거나 삭제할 때에는 다른 요소들을 이동시켜야 하므로 O(n) 시간이 걸립니다.
반면, 연결 리스트는 동적 자료구조로, 동적으로 크기가 조절될 수 있습니다. 각 요소는 독립적인 노드로 구성되어 있고, 노드들은 포인터를 통해 서로 연결되어 있습니다. 요소를 추가하거나 삭제할 때에는 단순히 노드의 연결만 조정하면 되기 때문에 O(1) 시간이 걸립니다. 다만 리스트 앞이나 중간에 요소를 추가/삭제하는 경우 노드를 찾는 시간이 추가적으로 필요할 수 있습니다.
결론적으로, 배열은 데이터의 접근, 탐색할 때 유용하고 연결 리스트는 데이터의 추가, 삭제할 때 유용하게 사용됩니다.
참고
