선형리스트, (정적배열) 배열 vs (동적배열) List vs LinkedList

정적배열과 동적배열의 개념 및 차이

 

정적 배열은 배열의 크기가 컴파일 타임에 정해져 프로그램 실행 도중에 크기를 늘리거나 줄이거나 할 수 없지만 메모리에 연속적으로 저장되어 인덱스라는 개념을 이용해 접근과 탐색에는 용이하며 캐시 적중률(Hit Rate) 효율성이 좋다. 

 

# 캐시 적중률이란? (CS) - 알아두면 나쁠꺼 없음

캐시 적중률이란? (CS 내용) 캐싱(caching)은 컴퓨터의 처리 성능을 높이기 위한 기법 CPU는 데이터를 처리하기 위해 메모리와 끊임없이 데이터를 주고받는다. 이 때 CPU에 비해 메모리는 속도가 느리기 때문에 메모리에 접근할 때 CPU는 효율적으로 사용되지 못한다. 캐시 메모리(cache memory)는 CPU와 메모리의 속도 차이로 인한 병목 현상을 완화하기 위해 사용한다. 출처 : https://www.quora.com/What-is-Memory-hierarchy 책상에서 자주 사용하는 물건을 가까운 자리에 두듯, 자주 사용하는 데이터를 CPU와 가까운 위치에 저장해 필요할 때 마다 빠르게 꺼내쓸 수 있다.  캐시메모리가 있는 컴퓨터 시스템은 CPU가 메모리에 접근하기 전 먼저 캐시 메모리에서 원하는 데이터의 존재 여부를 확인한다. 이때 필요한 데이터가 있는 경우를 적중(hit), 없는 경우를 실패(miss)라고 한다. 이 때 요청한 데이터를 캐시메모리에서 찾을 확률을 캐시 적중률(hit ratio)이라고 한다.

 

 

동적 배열은, 배열의 크기(사이즈)가 정해지지 않고 런타임 도중에 크기가 결정되는 타입이며 순차적으로 저장되는 구조이므로 선형 자료 구조라고 불린다.

C# 에서는 선형 리스트 종류는 List, ArrayList, LinkedList가 있으며 List와 ArrayList의 차이는 다른 타입의 요소를 저장할 수 있는 여부인데 List는 동일한 타입의 요소들만 저장할 수 있으며 ArrayList는 다른 타입의 요소를 저장할 수 있다. 따라서 ArraysList는 type-safe 하지 못하며 박싱과 언박싱을 해줘야 할 필요가 있다.

 

List 구현 원리

 

List의 구현 원리를 말하자면 배열기반으로 되어있어 기존 배열에는 크기를 늘리는 것이 불가능하지만 List는 내부적으로 추가에 있어서 배열의 요소가 미리 정해둔 배열의 크기를 초과하게 되는 경우 배열의 크기를 일정한 크기로 늘려나가는 방식이며 기존의 요소들은 새 배열로 복사하는 방식을 사용 (Count와 Capacity라는 개념을 사용함)

 

LinkedList

 

LinkedList는 List와 거의 동일하지만 LinkedList는 노드기반으로 메모리에 불연속적으로 저장 되어있다. 노드가 다른 노드를 참조하는 방식이므로 크기를 정해두지 않아도 크기를 늘리거나 줄일 수 있으며 요소의 삽입, 삭제에 있어서 자유롭다. 또한 LinkedList는 요소 삭제에서 뒤에있는 다른 노드와 바로 연결하기 때문에 메모리에 빈공간이 발생하지 않는다.

 

요소의 추가에 있어 노드의 tail에 이어서 추가하는 방식을 사용하여 O(1)이라는 시간복잡도를 가지고,

삭제에 있어서는 삭제 노드에 대해서 head와 tail에 대한 참조만 바꿔주는 방식을 사용하므로 해당 노드를 찾아 것에 요소 n 만큼 O(n) 시간복잡도를 가지고 그 위치에 요소를 지우는 방식을 사용한다.

탐색에 있어서는 노드의 처음 head부터 tail까지 찾아야하므로 O(n) 시간 복잡도를 가지고있다.

접근에 있어서도 시작부터 끝까지 노드를 탐색해야하는 수고가 생겨 O(n) 시간복잡도를 가진다.

List는 데이터의 크기가 정해져 있고, 추가적인 삽입 삭제가 일어나지 않으며 검색을 필요로 할 때 유리.

LinkedList는 데이터의 크기가 정해져 있지 않고, 삽입 삭제가 많이 일어나며, 검색이 적은 경우 유리.

 

Array vs LinkedList