Array vs Linked List

오늘부터 자료구조에 대한 내용을 하나씩 정리하기로 했다.

기록을 하지 않으면 알아도 금방 까먹기 때문에 까먹더라도 다시 돌아갈 수 있게.

 

Array

배열은 메모리에 정해진 사이즈만큼 공간이 만들어져서 데이터를 저장하는 방식이다.

그래서 데이터는 연속적으로 위치한 메모리에 저장되어 있다.

 

장점

• 연속적으로 메모리에 위치해있기 때문에 인덱스를 통해 빠르게 내가 원하는 값을 찾아낼 수 있다.

단점

• 사이즈가 정해졌기 때문에 정해진 사이즈 이상으로 데이터를 저장할 수 없다.

Linked List

Linked List는 사이즈가 동적으로 할당된다.

메모리 상에 여기저기 흩뿌려져 있는 공간에 원하는 만큼 데이터를 넣을 수 있는 방식이다.

각 데이터는 다음 데이터의 주소를 알고 있는 포인터가 있어서 연결되어 있다.

 

장점

• 사이즈가 정해진게 아니기 때문에 원하는 만큼 데이터를 추가할 수 있다.

단점

• 메모리 상에 여기저기 흩뿌려져 있기 때문에 데이터를 찾아내려면 처음부터 하나씩 연결된 정보를 찾아 찾아가야 한다.

정리

그래서 둘을 비교하자면 속도 측면에서는 Array가 유리할 수 있다.

저장되는 위치가 연속적이기 때문에 인덱스로 바로 찾아낼 수 있기 때문.

 

데이터를 동적으로 계속해서 저장하기엔 Linked List가 유리할 수 있다.

사이즈가 고정적이지 않기 때문.

 

각 장단점을 파악한 후 적절하게 쓰임새에 맞게 사용하면 될 것 같다.

 

시간복잡도와 공간복잡도

Arrays의 시간 복잡도

• Read: O(1) (특정 인덱스 값을 한번 읽으면 끝)
• Write: O(1) (특정 인덱스에 값을 한번 추가하면 끝)

Arrays의 공간 복잡도

• 배열에 N개의 엔트리가 있다고 했을 때
  • 메모리 사용량
    • 저장하는 타입의 메모리 크기를 C라고 했을 때 C * N = O(N)

Linked List의 시간 복잡도

• Read: O(N) (N번째 원소를 읽기 위해서 시작부터 하나씩 읽어 나가 N번을 찾아야 한다)
• Write: O(N) (마지막에 원소를 넣어야하고 마지막을 찾기 위해 역시나 시작부터 하나씩 읽어가 마지막에 가서 쓰기를 해야한다 마지막 원소를 찾아내는데 O(N), 쓰기 O(1) 따라서 O(N)

Linked List의 공간 복잡도

각 노드가 데이터+포인터를 가지므로 하나의 노드엔 데이터 + 포인터의 공간을 차지. 따라서 N개의 노드를 가진 Linked List는 O(N).

 

참고: Linked List가 이중 연결 리스트(앞과 뒤 모두 포인터가 있는)여도 O(N). 왜냐하면 노드 수에 비례하기 때문.