[Algorithm] 배열(Array)과 링크드 리스트(LinkedList)의 차이점

1. 배열(Array)의 특징

    - 배열은 각 원소에 즉시 접근 가능 ex) array[0], array[1] 이런식으로 즉 O(1)내에 접근 가능   

    - 배열은 원소를 중간에 삽입/삭제 하려면 모든 원소를 다 옮겨야 함 
       (최악의 경우 배열의 길이 N만큼 옮겨야 해서 O(N)의 시간복잡도)

    - 원소를 새로 추가하려면, 새로운 공간을 할당해야 하므로 비효율적인 자료구조

 

2. 링크드 리스트 (LinkedList)의 특징

    - 리스트는 크기가 정해지지 않은 데이터의 공간

    - 리스트는 특정 원소에 접근하려면 포인터를 따라 탐색

      (최악의 경우 모든 노드를 탐색해야 하므로 O(N)의 시간복잡도)

    - 리스트는 원소를 중간에 삽입/삭제 하기 위해서는 앞 뒤의 포인터만 변경

      (원소 삽입/삭제를 O(1)의 시간 복잡도)

 

	Array	LinkedList
특정 원소 조회	O(1)	O(N)
원소 중간 삽입/삭제	O(N)	O(1)
데이터 추가	데이터 추가 시 모든 공간이 다 차있다면 새로운 메모리 공간 할당	모든 공간이 다 찼어도 맨 뒤에 노드만 동적으로 추가
정리	데이터에 접근하는 경우가 빈번하다면 Array 사용	삽입과 삭제가 빈번하다면 LinkedList를 사용