[CS지식] 자료구조 : Array vs Linked list

배열 (Array

장점:

1. 인덱스로의 접근: O(1)의 시간 복잡도로 원소에 접근할 수 있습니다.
2. 메모리 효율성: 배열은 메모리의 연속적인 위치에 데이터를 저장하므로 공간 낭비가 적습니다. 또한, 연결 리스트에 비해 오버헤드가 적습니다.
3. 캐시 지역성: 데이터가 연속적으로 저장되기 때문에 CPU 캐시의 효율이 좋아질 수 있습니다.

단점:

1. 크기 고정: 초기에 배열의 크기를 정하면, 그 크기를 변경하기 어렵습니다.
2. 삽입/삭제: 중간에 원소를 삽입하거나 삭제할 경우 O(n)의 시간이 걸릴 수 있습니다.
3. 메모리 할당: 큰 배열을 한 번에 메모리에 할당하기가 어려울 수 있습니다.

연결 리스트 (Linked List)

장점:

1. 동적 크기: 연결 리스트는 필요에 따라 크기를 쉽게 변경할 수 있습니다.
2. 중간 삽입/삭제: 연결 리스트에서는 포인터만 변경하면 되므로, 중간에 원소를 삽입하거나 삭제하는 것이 O(1)의 시간에 가능합니다. (단, 삭제할 노드나 삽입 위치를 찾기 위해서는 O(n)의 시간이 걸릴 수 있습니다.)
3. 메모리 할당: 각 노드를 따로 할당할 수 있으므로, 큰 메모리 공간을 한 번에 할당할 필요가 없습니다.

단점:

1. 메모리 오버헤드: 각 노드마다 포인터 정보를 저장해야 하므로, 메모리 오버헤드가 있습니다.
2. 캐시 미스: 연속적이지 않은 메모리 위치에 데이터가 저장되므로, 캐시 미스가 발생하기 쉽습니다.
3. 인덱스로의 접근: 연결 리스트에서 특정 인덱스의 원소에 접근하려면, 처음부터 해당 위치까지 순차적으로 접근해야 합니다. 따라서 O(n)의 시간이 걸릴 수 있습니다.

결론

 

결론적으로, 배열은 인덱스를 통한 빠른 접근이 필요하거나, 메모리 사용을 최소화하고 싶을 때 유용합니다.

반면, 연결 리스트는 데이터의 삽입과 삭제가 빈번하거나, 자료의 크기를 동적으로 변경해야 할 때 적합합니다.

상황과 필요에 따라 적절한 자료 구조를 선택해야 합니다.