Array (배열)
정의: 배열은 고정된 크기의 연속적인 메모리 공간에 원소들을 저장하는 자료구조입니다.
특징
고정된 크기: 배열은 생성 시에 크기가 정해지며, 이후 크기를 동적으로 변경하기는 어렵습니다.
인덱싱: 배열의 원소에는 인덱스를 사용해 접근할 수 있으며, O(1) 시간에 해당 원소를 찾을 수 있습니다.
메모리 사용: 연속적인 메모리 공간을 사용하므로 메모리 관리에 용이합니다.
주요 작업의 시간 복잡도
원소 조회 (인덱싱): O(1)
원소 추가/삭제 (끝에서): O(1)
원소 추가/삭제 (중간): O(n)
LinkedList (연결 리스트)
정의: 연결 리스트는 노드(Node)들의 집합으로, 각 노드는 데이터와 다음 노드를 가리키는 포인터로 구성됩니다.
특징
동적 크기: 연결 리스트는 동적으로 크기를 변경할 수 있습니다. 노드를 추가하거나 삭제하면서 크기를 조절할 수 있습니다.
포인터 사용: 각 노드는 데이터와 함께 다음 노드를 가리키는 포인터를 가지고 있습니다.
메모리 사용: 비연속적인 메모리 공간을 사용합니다.
주요 작업의 시간 복잡도
원소 조회: O(n)
원소 추가/삭제 (시작 또는 끝에서): O(1) - 단, 끝에서의 작업은 이중 연결 리스트 또는 꼬리 포인터가 있는 경우에만 O(1)
원소 추가/삭제 (중간): O(n)
배열과 연결 리스트는 각각의 장단점이 있으므로, 사용 사례에 따라 적절한 자료구조를 선택해야 합니다. 예를 들어, 중간에 자주 원소를 추가하거나 삭제해야 하는 경우 연결 리스트가 유용할 수 있습니다. 반면, 원소에 빠르게 접근해야 하는 경우 배열이 더 적합합니다.
화이팅 화이팅