자기 전 누워서 정리하는 배열과 리스트

비선형 자료구조는 선형 자료구조를 기반으로 만들어진다.
비선형 자료구조는 경우에 따라
어떠한 선형 자료구조로 구현하느냐에 따라
성능과 메모리 공간 차지에 영향을 미친다.

따라서 선형 자료구조의 이해는 아주 중요한 기반지식이다.


배열은 연속된 메모리 구조를 가지고
크기가 정해져있다.

리스트는 노드와 노드로 연결된 메모리 구조를 가지고
크기가 가변적이다.

배열의 대표적인 stl은 벡터이다.

배열은 연속된 메모리 구조를 가지기 때문에,
캐시 공간적 지역성을 만족하여 주변 접근이 빠르다.
또한 인덱스를 이용한 임의접근이 가능하여,
데이터 접근 속도는 O(1)의 속도를 가진다.
벡터는 원소 삽입 삭제 시 사이즈를 넘어선 경우,
중간에 삽입 삭제가 일어나는 경우
삭제되고 재할당 된다.
이는 성능에 영향을 끼친다.
때문에 속도면에서 리스트에 비해 삽입 삭제가 느리다.
하지만 길고 큰 메모리를 저장해야하는 선형구조가 요구될 때는
연속된 메모리 공간이 필요한 벡터는 적합하지않다.
이는 외부 단편화가 일어나기 쉽기 때문이다.


리스트는 노드와 노드의 연결로 이루어진 선형자료구조이다.
이는 포인터로 연결되었기 때문에 삽입 삭제가 자유롭고,
길이가 가변적이다.
또한 포인터의 값만 수정하면 되므로 삽입 삭제가 빠르다.
리스트는 삽입 삭제가 잦거나
길고 큰 메모리를 저장해야하는 경우
각각 연결되지 않은 메모리 공간을 차지하기 때문에
자료형 1개의 크기에 맞는 공간이라면 노드가 할당된다.
따라서 길게 연결되고 메모리가 큰 자료구조를 요할 때 적합하다.
하지만 리스트는 임의접근이 불가능하다.
따라서 포인터를 계속 타고가야 하기 때문에,
n번째 자료를 찾기 위해서는 O(n)만큼 걸린다.