Array vs Linked List

Array

크기가 정해진 데이터의 공간으로 한 번 정해지면 후에 바꿀 수 없음

원소의 순서는 0부터 시작하고 이를 index 라고 부름

원소에 즉시 접근할 수 있다 . array[0]

상수 시간 O(1) 내에 접근 할 수 있음을 뜻한다. 

원소를 중간에 삽입/삭제를 하려면 모든 원소를 다 옮겨야 함.

최악의 경우 끝에서 끝으로 삽입/삭제시 배열의 길이 N 만큼 옮기기에 O(N)의 시간복잡도를 가짐

원소를 새로 추가하려면 새로운 메모리 공간을 할당해야 하기에 비효율적인 자료구조

데이터에 접근하는 경우가 빈번하다면 Array !

 

밑의 경우 array[9](="8")에서 array[4](="3")이동은 O(5)의 시간복잡도를 가짐

array

 

Linked List

리스트와 혼용되는 단어

크기가 정해지지 않은 데이터의 공간으로

연결고리로 이어주면 자유자재로 늘어날 수 있음

특정 원소에 접근하려면 포인터를 따라 탐색을 해야함

최악의 경우 끝에서 끝을 탐색해야하기에 O(N)의 시간 복잡도를 가짐

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

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

원소를 추가를 하려면 맨 뒤의 노드만 동적으로 추가하면 되기에 쉽게 데이터를 추가할 수 있음

삽입과 삭제가 빈번하다면 Linked List를 사용 ! 

linked link

 

참고 : python 에서 사용하는 list 는 array로 구현됨

내부적으로 동적 배열을 사용해 배열의 길이가 늘어나도 O(1)의 시간 복잡도가 걸리며

링크드 리스트, 배열로도 쓸 수 있게 만든 효율적인 자료 구조