Array / Vector(c# List) / LinkedList 차이, 장단점

일단 Array와 List 두개를 비교하고 그리고 LinkedList를 봐보자.

1. Array(배열) / Vector & List

공통점
어떤 메모리 블록에 연속적으로 나열된 같은 유형의 변수 모음이라고 한다.(선형적)
인덱스가 존재하기 때문에 n개의 데이터가 존재한다고 가정할때 록업을 실시할 시 O(n)이 아닌 O(1)로 값을 찾아 갈 수 있다.

차이점
메모리 측면에서 Array는 컴파일 타임에 결정되는 반면에 Vector & List 는 런타임에 메모리 크기가 결정이 된다.
즉 Array는 스택영역, Vector & List는 힙 영역에 할당된다고 할 수 있다.

컴파일에 결정된다는 것은(Array) 미리 크기를 결정을하고 그 이후에 늘리는게 불가능하다.

반면에 힙 영역에 결정되는(Vector & list)는 런타임에 결정이 나기 때문에 실행 중간에 크기를 유동적으로 결정 하거나 더 값이 추가할 수 있다.


추가.
값을 추가가 가능한 이유는 Capacity라는게 존재하는데 이는 더 값이 추가될것을 대비하에 미리 크기를 힙영역에 확보하는 행위이다. (length와는 무관)

ex) capacity = 8이라고 가정
만약 값이 계속적으로 추가되면서 값이 8개로 꽉 차고 더 값이 추가적으로 들어오면 이는 capacity*2 = 16 해서 새로운 힙영역을 할당할 곳을 찾고 기존에 8개를 저장했던것을 새로운 영역에 그대로 복사를 하고 나머지 8개를 더 확보하는 형식으로 이루어 진다.



삭제.
만약 i번째(중간) 값이 삭제 된다면 i+1 부터 length 까지 한칸씩 당겨 중간에 빵꾸난것을 메꾸는 방식으로 이루어진다. 이 또란 오버헤드가 발생한다. 만약 capacity가 64까지 늘어난 상태인데 삭제로 인해 값이 1개라고 하더라도 Capacity는 변화되지 않습니다.


이렇게 추가/삭제 가능하다고 해서 막무가내로 한다면 이렇게 새로운 힙영역을 찾고 복사하는 행위, 삭제로 인해 값을 하나씩 땡기는 행위로 오버헤드가 발생하기에 만약 추가/삭제가 많은 경우 다른 자료구조를 사용하도록 하자.


LinkedList
링크드 리스트도 마찬가지로 힙영역에 할당이 된다. 
이는 각 데이터를 객체를 생성하여 동적으로 할당해야 한다. 이는 오히려 배열의 복사 작업보다 메모리 할당에 더 오랜 시간이 걸릴 수도 있다. 

또한 각 데이터는 메모리에 거의 떨어져서 할당이 된다. 이는 인덱스가 존재 하지 않기 때문에 록업을 할때 Head 부터 찾아야 하기 때문에 O(n)이라는 시간복잡도를 가진다.

삽입/삭제
링크드 리스트의 장점은 여기서 발휘된다. 
값이 중간에 삽입,삭제는 다음 노드를 가리키는 노드를 바꾸고 기존꺼를 delete를 해주는 방식으로 이루어 지기 때문에(삭제) 효율을 가지고 있다. 또한 메모리 상으로 바로 옆에 존재 하지 않아도 되기 때문에 새로 공간을 확보해서 복사를 하던지 삭제를 하는 행위는 일어나지 않는다. 

단 노드마다 포인터 관련된 오버헤드를 감수해야한다.