[CS] Array와 Linked List의 차이

여러 개의 목판으로 이루어진 흔들다리를 생각해보자.

Array는 목판마다 번호를 적어 놓았다.

Linked List는 목판을 이어 붙이기만 했다.

 

[탐색]

이번에는 다리에서 목판을 찾아야 한다고 생각해보자.

Array의 경우 목판 별로 숫자를 적어놨다. 그러니 바로 찾을 수 있다. O(1)

Linked List의 경우 숫자를 적지 않고 이어 붙여놓기만 했다. 그러니 처음부터 찾아야 한다. O(n)

 

[삭제]

흔들 다리 앞이 낡아서 목판 하나를 끊어내야 한다고 생각해보자.

Array의 경우는 처음을 끊어내고 한쪽 다리의 목판을 하나하나씩 떼고 옮겨 새로 붙이고 번호도 새로 적는다. O(n)

Linked List는 그냥 끊어내면 된다. O(1)

 

[삽입]

이번에는 흔들다리 앞에 목판 하나를 추가해야 한다고 생각해보자.

Array의 경우는 앞에 목판을 넣고 그 이후 목판은 다시 떼서 앞의 목판에 붙이고 번호를 새로 적기를 끝 목판까지 반복한다. O(n)

Linked List는 새로운 목판을 앞에 넣고 원래 첫번째 목판과 연결하기만 하면 된다. O(1)

 

[삭제-중간]

흔들 다리 중간이 낡아서 목판 하나를 끊어내야 한다고 생각해보자.

Array의 경우는 바로 찾아서 중간을 끊어내고 한쪽 다리의 목판을 하나하나씩 떼고 옮겨 새로 붙이고 번호도 새로 적는다. O(n)

Linked List는 처음부터 보며 위치를 찾고 그냥 끊어내면 된다. O(n)

 

[삽입-중간]

이번에는 흔들다리 중간에 목판 하나를 추가해야 한다고 생각해보자.

Array의 경우는 바로 찾아서 중간에 목판을 넣고 그 이후 목판은 다시 떼서 앞의 목판에 붙이고 번호를 새로 적기를 끝 목판까지 반복한다. O(n)

Linked List는 처음부터 위치를 찾고 새로운 목판을 중간에 넣고 앞뒤 목판과 연결하면 하면 된다. O(n)