# Array & Linked List - Array 와 Linked List는 하도 많이 비교하고 기초적인거여서 자세히 다룰 것도 없다. 근데 초단순한 내용 말고, 몇 가지 짚고 넘어가면 좋을 내용들이 있지 않을까해서 끄적여본다. Array --- - 일단, Array 의 핵심은 **메모리에 연속적으로 할당된 저장 공간**이라고 생각하면 된다. 여기서 포인트는 '연속적으로 할당된 공간'이라는 것이다. 그러면 Linked List 는 연속적이지 않은 공간에 할당된다는 것인가? 그렇다. Linked List 는 동적으로 메모리를 할당받기 때문에 내가 직전에 만든 노드와 나란히 메모리를 할당받는다고 보장할 수 없다. (만약에 배열처럼 정해진 크기의 메모리를 할당받으면 연속적일 수 있지만, 이걸 Linked List라고 보진 않는다. 동적으로 메모리를 할당받은 '배열'이라고 부를거다) - Array를 사용할 때의 장점은 **random access time**이고, 단점으로는 **중간에 insert, delete를 할 때, 다른 값들을 한 칸씩 땡겨야 O(N)의 시간이 소요된다는 점**이다. 이런 행위는 비효율적이라고 볼 수 있지만, insert, delete가 아니라 flag 하나만 표시해서 비었음~ 이라고 표시해서 사용하는 경우가 종종있다. access time 이 상수라는 점이 크게 작용하기 때문에 그정도의 메모리 낭비는 괜찮다고 생각하나보다. 예를 들면, heap을 구성할 때 `lazy propagation` 을 구현하는 것은 heap 의 노드에 체크만 해놓고 heap을 재구성하지 않는다. (자세한 것은 heap에서 다룹시다) Linked List --- - Linked List는 삼성전자 프로 시험의 꽃이라고 할 수 있는 자료구조다. 왜 그럴까... Array로는 낼 문제가 없고 적당히 쉽고 범용적인 자료구조를 선택하려고 하니까 Linked List를 선택한걸까? - 사설은 접어두고, Linked List는 **Singly Linked List 와 Doubly Linked List** 가 있다. Singly Linked List는 단방향이고 포인터를 위한 공간이 노드 당 하나만 필요하지만, Doubly Linked List는 양방향이고 포인터를 위한 공간이 노드 당 두 개가 있기 때문에 메모리를 더 소모한다. 하지만 Linked List를 search할 때, 역으로 search를 할 수 있다는 점이 강점이다. - Linked List 를 구현하는 방법은 여러가지가 있다. 차이는 head 노드를 dummy 노드로 하냐 안하냐 차이다. head 노드를 dummy 노드로 사용하면 메모리를 추가로 사용한다는 단점이 있지만, 코드가 일관되고 깔끔해진다는 장점이 있다. 반대로 dummy 노드를 사용하지 않으면 메모리 공간은 절약할 수 있지만, head를 따로 처리해야한다는 점에서 코드는 간결하지 않을 수 있다. Linked List의 구현 --- ### head 가 dummy 인 경우 ```python= ``` ### head 가 dummy 가 아닌 경우 ```python= ``` Array vs Linked List --- - Array 와 Linked List의 차이는?