18_Step : Array와 LinkedList

Array와 LinkedList는 비슷하지만 큰 차이점을 가지고 있다.

 

- 원하는 데이터 찾는데 걸리는 시간

Array는 1-2-3-4의 데이터가 있다고 가정했을 때 1~4 중 원하는 데이터를 바로 찾을 수 있어서 O(1)으로 시간이 동일하게 걸린다.

LinkedList는 1-2-3-4의 데이터 중 3번 데이터를 찾고 싶으면 1번부터 순차적으로 다 확인을 하며 찾아가기 떄문에 O(N)의 시간이 걸린다.

 

-중간에 데이터를 삽입할 때 걸리는 시간

Array는 1-2-4-5에서 3을 2-4 사이에 넣고 싶다면 데이터를 맨 뒤에 넣어서 1-2-4-5-3을 만들고 1-2-4-3-5, 1-2-3-4-5 이런식으로 밀어주기를 해야하기 때문에 O(N)의 시간이 걸린다.

LinkedList는 2에서 3으로 연결하라는 노드만 찍어주면 바로 연결할 수가 있어서 O(1)의 시간이 걸린다.

 

-데이터 추가시

Array는 공간이 꽉 찼으면 새로운 메모리를 할당받아야 한다.

LinkedList는 맨 뒤의 노드만 동적으로 추가해주면 된다.

 

-결론-

Array는 데이터 조회와 같은 경우가 많을 때 사용하는게 좋다.

LinkedList는 추가,삭제를 자주 해야할 경우에 사용하면 좋다.