2d3k
commented
1 year ago 메모리 할당: 배열은 연속된 메모리 공간에 데이터를 저장하므로, 메모리를 미리 할당해야 합니다. 반면에 링크드 리스트는 각 노드가 독립적으로 메모리에 할당되기 때문에, 동적으로 메모리를 할당하게 됩니다.
삽입과 삭제의 성능: 배열은 인덱스를 이용하여 데이터에 접근하므로, 데이터의 삽입과 삭제가 배열의 길이에 따라 시간 복잡도가 다를 수 있습니다. 배열의 중간에 데이터를 삽입하거나 삭제할 경우, 해당 위치 이후의 데이터들을 모두 이동시켜야 하기 때문에 시간 복잡도가 O(n)이 될 수 있습니다. 반면에 링크드 리스트는 노드의 포인터를 조작하여 데이터를 삽입하거나 삭제하므로, 시간 복잡도가 O(1)로 유지될 수 있습니다.
크기의 제한: 배열은 미리 할당된 고정 크기의 메모리를 사용하므로, 크기에 제한이 있을 수 있습니다. 반면에 링크드 리스트는 동적으로 메모리를 할당하므로, 크기에 제한이 없습니다.
메모리 사용량: 배열은 미리 할당된 고정 크기의 메모리를 사용하므로, 메모리 사용량이 크게 줄어들 수 있습니다. 반면에 링크드 리스트는 각 노드마다 포인터를 가지고 있어 메모리 사용량이 상대적으로 더 크게 될 수 있습니다.
접근 속도: 배열은 인덱스를 이용하여 데이터에 접근하므로, 데이터에 빠르게 접근할 수 있습니다. 반면에 링크드 리스트는 노드를 따라가면서 데이터에 접근해야 하므로, 접근 속도가 더 느릴 수 있습니다.
구현의 복잡성: 배열은 고정 크기의 메모리를 사용하고 인덱스를 이용하여 데이터를 관리하기 때문에, 구현이 비교적 간단할 수 있습니다. 반면에 링크드 리스트는 각 노드가 독립적으로 메모리를 할당하고 포인터를 조작해야 하므로, 구현이 상대적으로 복잡할 수 있습니다.
Queue를 구현할 때 링크드리스트와 배열의 차이