[CS] Array&List

Array

연속 자료구조 (Array)

연속 자료구조는 데이터가 메모리에 연속적으로 존재하는 자료구조로, 대표적으로 배열이 있다. 배열은 인덱스를 사용하여 요소에 접근할 수 있어 특정 원소에 빠르게 접근할 수 있는 장점이 있다. 그러나 중간에 요소를 삽입 또는 삭제할 경우, 빈 공간을 채우기 위해 원소들을 한 칸씩 이동하는 작업이 필요하므로, 중간 삽입 또는 삭제가 빈번하게 발생할 때는 적합하지 않다.

가변배열

배열 생성시 크기를 고정하는 고정배열과 수정할 수 있는 가변배열이 있다. 고정배열의 경우, 한 번 크기를 지정하면 그 이상의 원소를 추가할 수 없다. 예를 들어, 크기가 50인 고정배열은 50개의 원소를 모두 채우면 추가적인 원소를 삽입할 수 없다. 이에 반해 가변배열은 기존 배열보다 큰 배열을 생성하고, 기존 배열의 원소들을 복사하여 추가적인 원소를 수용한다. C++에서는 가변배열로 주로 std::vector를 사용한다.

[STL] 1. vector

List

연결 자료구조 (List)

연결 자료구조는 데이터가 메모리의 임의의 위치에 존재하는 자료구조로, 대표적으로 연결 리스트가 있다. 연결 리스트의 최소 단위는 노드라고 불리는데, 데이터를 갖고 있는 데이터 부분과 다음 노드를 가리키는 포인터인 링크 부분으로 나뉜다. 삽입 및 삭제시에는 노드의 링크 부분만 수정해주면 되기 때문에 삽입 및 삭제 속도가 빨라, 요소의 중간 삽입 삭제가 빈번하게 일어날 경우에 적합한 자료구조이다.

이터레이터

연결 리스트는 인덱스 대신 이터레이터를 사용한다. 이터레이터는 인덱스와는 사용법이 다르며, 자료 공간을 순차적으로 돌아다니는 포인터 쯤으로 생각할 수 있다. 이터레이터는 순차적으로 요소에 접근하기 때문에 상대적으로 접근 속도가 느리다.

이중 연결 리스트

단일 연결 리스트는 링크가 다음 노드만 가리키지만, 이중 연결 리스트는 각 노드가 이전 노드와 다음 노드를 가리키므로, 특정 위치에 노드를 삽입하거나 삭제할 때 해당 위치의 이전 노드를 바로 찾을 수 있어 단일 연결 리스트보다 중간 삽입 삭제가 빠르다. C++에서는 연결 리스트로 주로 std::List를 사용한다.

[STL] 4. list