[자료구조] 배열과 리스트 (+벡터)

배열과 리스트

• 동일한 특성의 데이터들의 집합을 가리키는 자료구조

 

배열(Array)

장점	1. 구현이 쉬움 2. 인덱스가 있어 조회에서 빠른 성능을 보여줌 3. 연속된 메모리 공간에 할당되어 순차 접근에도 빠름 4. 참조를 위한 추가 메모리 할당이 필요 없음
단점	1. 삽입/삭제 시 뒤에 요소들을 이동해야 해서 비효율적 2. 선언 시 지정한 크기 변경 불가 3. 메모리 재사용 불가(초기 사이즈 만큼 할당, 데이터가 없더라도 메모리 차지)

 

 

리스트(List)

• 비연속적인 메모리
• 리스트는 double linked list로 구현되어 있다.
• 메모리 선할당을 하지 않는다. 메모리 그 자신을 위한 메모리 오버헤드는 상수다.
• 리스트 안에 각 요소는 이후와 이전의 요소를 가리키는 포인터를 가지고 있어 추가 공간이 필요하다.
• 당신이 요소를 추가할 때, 전체 리스트의 메모리를 재할당할 필요가 없다.
• 추가와 제거에 비용이 싸고, 리스트 어디서든 일어날 수 있다.
• 요소에 랜덤 접근 할 수 없기 때문에, 특정한 요소에서 얻는 것이 비용이 비쌀 수 있다.
• 리스트에서 요소를 추가 제거 할때, iterator은 유효하게 남아 있다.
• 만약 요소의 배열이 필요하다면, 당신은 새로운 배열을 만들어야만 하며 새로운 배열에 요소들을 추가해야 한다. 이는 근본적인 배열이 없기 때문이다.

장점	1. 삽입/삭제 시 전후 노드의 참조 관계만 수정하면 되기 때문에 효율적 2. 크기가 고정적이지 않음 3. 메모리 재사용 가능(삭제 시 해당 노드의 참조가 사라져 GC에 의해 가용 메모리로 전환)
단점	1. 구현이 상대적으로 복잡 2. 검색이 비효율적(처음부터 순차적으로 검색해야 함) 3. 참조를 위한 메모리가 필요

 

벡터(Vector)

• 연속적인 메모리
• 미래에 들어갈 요소를 위해 선할당을 한다.
• 각 요소는 요소 타입 그 자체만큼의 공간을 요구한다. (포인터들을 포함하지 않는다)
• 당신이 요소를 추가하는 어느 때나, 전체 vector의 메모리를 재할당 할 수 있다.
• 끝에 요소를 추가하는 것은 상수(상환 시간)지만, 다른곳에서 추가하는 것은 O(n) 값이 든다.
• 끝에 요소를 제거하는 것은 상수 시간이지만, 다른 곳에서 제거하는 것은 O(n)이다.
• 랜덤하게 vector요소에 접근 할 수 있다.
• vector에 혹은 vector로 부터 요소를 추가하거나 제거하면, iterator는 무효화된다.
• 당신이 요소의 배열을 필요로 한다면, 근본적인 배열에서 쉽게 얻을 수 있다.

장점	1. 개별 원소들 접근 가능 2. 원소를 마지막에 삽입 하는 것이 빠름 3. 랜덤으로 원소 순회가 가능 4. 개별 원소에 대한 접근 속도가 빠름
단점	1. 컨테이너 끝이 아닌 곳에 삽입/제거시 성능이 현저히 떨어짐 2. 동적이라 확장/축소가 편하나 확장시 비용이 크다.

 

사용 예시

배열을 사용해야 할 때

• 저장할 데이터의 개수가 정해져 있음
• 삽입/삭제 작업이 적음
• 특정 위치의 데이터를 조회하는 작업이 많음

 

리스트를 사용해야 할 때

• 저장할 데이터의 개수가 정해져 있지 않음
• 삽입/삭제 작업이 많음
• 특정 위치의 데이터를 조회하는 작업이 별로 없음

 

 

 

Vector와 List의 차이점

• vector를 중간 삽입시 원소를 밀어내지만 list는 노드를 연결만 하기 때문에, 삽입 삭제 부분에서 시간 복잡도의 우위를 가진다.
• vecotr는 랜덤 부분 접근이 가능하지만 list는 더블링크드리스트로 되어있기 때문에 x[2]와 같은 랜덤 접근이 되지 않는다. 검색적인 측면에서는 vector가 우위에 있다.

 

 

---

참조 및 출처 :

https://bb-dochi.tistory.com/9

https://chanheess.tistory.com/154