Array, List, Vector

2024. 3. 10. 11:01프로그래밍/자료구조

1.1 자료구조의 유형

1.1.1 연속된 자료 구조

단일 메모리 chunck

정적 배열, 동적 배열

시간복잡도(O(1))

1.1.2 연결된 자료 구조

노드(node)라 하는 chunck 데이터 저장

시간복잡도(O(n))

1.2 std::forward_list

연속 자료 → 연결 리스트

<구성요소.>

  1. 포인터
  2. new와 delete 연산자를 이용하여 메모리를 할당하고 해제

1.3 std::array + at(index)

배열은 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조이다.

배열의 값은 인덱스를 통해 참조할 수 있으며, 선언한 자료형의 값만 저장할 수 있다.

  • 인덱스를 사용하여 값에 바로 접근할 수 있다.
  • 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다. 값을 삽입하거나 삭제하려면 해당 인덱스 주변에 있는 값을 이동시키는 과정이 필요하다.
  • 배열의 크기는 선언할 때 지정할 수 있으며, 한 번 산언하면 크기를 늘리거나 줄일 수 없다.

1.4 std::vector

Array의 단점

  • [ ] array는 컴파일 시간에 결정되는 상수어야 하기 때문에 프로그램 실행 중 변경 불가능
  • [ ] 크기가 고정되어 있어서 원소를 추가하거나 삭제할 수 없다.
  • [ ] 메모리 할당 방법을 변경할 수 없다. 항상 스택 메모리를 사용해야 한다.

Array의 단점을 보완한 Vector

  • 동적으로 원소를 추가할 수 있다. -> 크기가 자동으로 늘어난다
  • 맨 마지막 위치에 데이터를 삽입하거나 삭제할 때는 문제가 없지만 중간 데이터의 삽입 삭제는 배열과 같은 매커니즘으로 동작한다.
  • 배열과 마찬가지로 인덱스를 이용하여 데이터에 접근할 수 있다
  • push_back(), insert() 함수 사용
  • 템플릿 매개변수 다음에 할당자(allocator)제공 가능

1.5 std::forward_list

std::forward_list는 리스트 끝에 원소 추가, 역방향 이동, 리스트 크기 반환 등의 기능은 제공하지 않는다.

→ 메모리를 적게 쓰고 빠른 성능을 유지하기 위함

1.5 std::list

std::list는 양쪽 방향으로 연결된 리스트, 즉 이중 연결 리스트(doubly-linked list) 구조로 되어 있다. 다만 메모리를 좀 더 사용한다.

struct doubly_linked_list_node
{
	int data;
	doubly_linked_list_node* next;
	doubly_linked_list_node* prev;
};

노드의 기본 형태는 위와 같다.

 

이중 연결 리스트는 이전 노드를 가리키는 포인터가 추가로 있다. 이 포인터를 이용하여 역방향으로 이동할 수 있으며, 맨 마지막 원소와 리스트 크기를 따로 저장하여 push_back() 또는 size()함수를 지원할 수도 있다.

또한 std::forward_list와 마찬가지로 template<typename T> 매개변수로 사용자 정의 할당자를 지정할 수도 있다.

 

💡 std::forward_list와 std::list의 push_front(), insert(), pop_front(), erase() 함수 시간 복잡도는 서로 같지만, std::list는 두 개의 포인터를 관리해야 하기 때문에 이중 연결 리스트에서 다인 연결 리스트보다 대략 두 배의 연산을 수행해야 한다.

 

  • 인덱스가 없으므로 값에 접근하려면 Head 포인터부터 순서대로 접근해야 한다. 값에 접근하는 속도가 느리다.
  • 포인터로 연결되어 있으므로 데이터를 삽입하거나 삭제하는 연산 속도가 빠르다
  • 선언할 떄 크기를 별도로 지정하지 않아도 된다. -> 리스트의 크기는 정해져 있지 않으며, 크기가 변하기 쉬운 데이터를 다룰 때 적절하다.
  • 포인터를 저장할 공간이 필요하므로 배열보다 구조가 복잡하다.

 

!https://blog.kakaocdn.net/dna/uIMDJ/btq3KRZv2BH/AAAAAAAAAAAAAAAAAAAAAMWeItmap7Y-MuqJNuKMLn6u4bSpNdEuL-Bf2UTuOoEO/img.png?credential=yqXZFxpELC7KVnFOS48ylbz2pIh7yKj8&expires=1753973999&allow_ip=&allow_referer=&signature=TbhH%2FZEe97eKaayX6I9rXh%2FsssU%3D

remove(), remove_if(), sort(), unique(), reverse() 등의 함수도 std::list에서 제공되며, std::forward_list와 같은 형태로 동작한다.

 

1.5.1 양방향 반복자(bidirectional iterators)

std::list는 역방향으로의 연산이 필요한 경우에는 역방향 반복자(reverse iterator)를 쓸 수 있지만 임의 접근 반복자(배열)보다는 유연하지 않다.

1.5.2 반복자 무효화

iterator는 메모리 주소를 가리키는 포인터를 이용하여 구현되었기 때문에 경우에 따라 컨테이너가 변경될 경우 제대로 동작하지 않을 수 있다. 그러므로 컨테이너가 변경되어 특정 노드 또는 원소의 메모리 주소가 바뀌면 사용하던 반복자가 무효화될 수 있고, 이 경우 예측할 수 없는 동작이 발생할 수 있다.

벡터와 달리 연결 리스트에서는 삽입 또는 삭제 동작에서 원소를 이동할 필요가 없으므로 반복자가 무효화되지 않는다. (td::list, std::forward_list)i

'프로그래밍 > 자료구조' 카테고리의 다른 글

Deque = Vector + List  (0) 2024.03.15
ADT & Composite Data Type  (1) 2024.03.15