[자료구조] 배열과 리스트 그리고 벡터

코딩 테스트에서 주어진 문제를 해결하기 위해서는

사용해야할 알고리즘 그리고 자료구조가 중요하다.

필자는 자료구조에 대한 정리글을 써보려한다.

 

 

백준에서 문제를 해결하면서, 혹은 강의를 들으면서

배열과 리스트는 똑같은 개념이 아닌가? 하며

매일 헷갈렸다.

이번 기회에 그 개념을 바로 잡아보자.

 

 

배열

• 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조
• 배열의 값은 인덱스를 통해 참조
• 선언한 자료형의 값만 저장 가능

배열의 구조

배열의 특징

1. 인덱스를 사용하여 값에 바로 접근 가능
2. 새로운 값을 삽입하거나 특정 인덱스에 있는 값 수정 어려움.
   값을 삽입하거나 삭제하려면
   해당 인덱스 주변에 있는 값을 이동시켜야 함.
3. 배열의 크기는 선언할 때 지정.
   한번의 선언 가능, 크기를 늘리거나 줄일 수 없음.
4. 구조 간단

 

 

 

리스트

: 값과 포인터를 묶은 노드를 포인터로 연결한 자료구조

리스트의 구조

 

리스트의 특징

1. 인덱스 존재 X.
   값에 접근하려면 Head 포인터부터 순서대로 접근.
   속도 느림.
2. 포인터 연결구조이기 때문에 데이터 삽입/삭제시 연산 속도 빠름.
3. 선언 시 크기를 별도로 지정하지 않아도 됨.
   리스트의 크기가 정해져있지 않음.
4. 포인터 저장 공간이 필요하므로
   배열보다 복잡한 구조

 

 

 

 

벡터

• C++ 표준 라이브러리(Standard Template Library)에 있는 자료구조 컨테이너
• 가존 배열과 같은 특징을 가짐
• 배열의 단점 보완한 동적 배열의 형태

 

벡터의 특징

1. 동적으로 원소 추가 가능.
   크기가 자동으로 늘어남.
2. 맨 마지막 위치에 데이터를 삽입하거나 삭제할 때는 문제 없음.
   중간 데이터 삽입/삭제는 배열과 똑같이 동작
3. 인덱스를 통한 데이터에 대한 접근 가능(배열과 같은 특징)

//선언
vector<int> A;

//삽입 연산
A.push_back(1); //마지막에 1 추가
A.insert(A.begin(), 7); //맨 앞에 7 삽입
A.insert(A.begin()+2, 10); //index 2 위치에 10 삽입

//값 변경
A[4] = -5;

//삭제 연산
A.pop_back(); //마지막 값 삭제
A.erase(A.begin()+3); //index 3에 해당하는 값 삭제
A.clear(); //모든 값 삭제

//정보 가져오기
A.size(); //데이터 개수
A.fornt(); //처음 값
A.back(); //마지막 값
A[3]; //index 3에 해당하는 값
A.at(5); //index 5에 해당하는 값
A.begin(); //첫 번째 데이터 위치
A.end(); //마지막 데이터의 다음 위치