Array와 Linked List의 차이점

List(순서가 있는 데이터 set)을 구현하기 위한 방법으로는 Array와 Linked List가 있다.

출처: https://www.oreilly.com/library/view/c-data-structures/9781788835213/assets/19502ab7-cdd7-4a71-a7c0-d8bf491c1354.png

두 자료구조에는 결정적인 차이가 있는데, Size의 고정 여부와 메모리가 연속적으로 할당되어 있는지의 여부가 다르다.

Array는 선언 시 Size가 고정되어 있으며, 연속적인 메모리 공간에 배열이 할당되게 된다.

따라서 Array의 각 element를 접근하기 위해서는 0번째 index의 주소값만 알면 되므로 Linked List에 비해 월등히 빠른 접근 시간을 가진다.

Linked List는 insert, delete연산을 수행할 때 마다 size가 변화하며, 각각의 element들은 독립적인 메모리 공간에 할당되기 때문에 element 자체에서 다음(+이전) element의 주소값을 가지고 있어야 한다.

그래서 Linked List는 필연적으로 접근 시간이 느릴 수 밖에 없다. 

 

하지만 Array는 임의의 위치에 insert, delete를 하기 위해 O(n)의 time complexity가 소모된다는 큰 단점이 존재한다. 위에서 언급한 것 처럼 연속된 메모리 공간에 값이 저장되어 있는데 중간 위치의 데이터가 변화하게 된다면 해당 element 이후의 element들도 값을 모두 앞으로 땡기거나(?) 한 칸씩 밀어내야 한다.

Linked List는 이 대신 element들을 가리키는 pointer에 대해서만 변화를 주면 되기 때문에, O(1)이 소모된다.

따라서, 다룰 데이터의 size가 가변적이고 insert, delete가 자주 발생한다면 Linked List를

다룰 데이터의 크기가 고정되어 있고, insert&delete가 자주 발생하진 않는 대신 access 혹은 edit이 자주 발생한다면 Array를 사용하는것이 적합하다.