내일배움캠프 - Day 43 - Array. LinkedList

오늘 배운 것:

배열

• 배열은 각 원소에 즉시 접근할 수 있다.
• 즉시 접근 가능하다는 말은 상수 시간 내에 접근할 수 있음을 의미함.
• 배열은 중간에 원소를 삽입/삭제를 하려면 모든 원소를 다 옮겨야 함.
• 최악의 경우 배열의 끝과 끝에서 옮겨야 하면 배열의 길이 N만큼 옮겨야 함.
• 최악의 경우 O(N)만큼 시간 복잡도를 가짐.
• 배열은 원소를 추가하려면 새로운 공간을 할당해야 하므로 매우 비효율적인 자료구조임. 

 

Linked List (List)

• Linked List는 크기가 정해지지 않은 데이터 공간임. 연결 고리로 이어주기만 하면 자유자재로 늘어날 수 있음.
• List는 특정 원소에 접근하려면 연결 고리를 따라 탐색해야 함.
• 최악의 경우에는 모든 화물 칸을 탐색해야 하므로 O(N)의 시간 복잡도를 가짐.
• 연골고리가 pointer이고, 공간이 node이다.
• 리스트는 원소를 중간에 삽입/삭제 하기 위해서는 앞 뒤의 포인터만 변경해주면 됨. 따라서 원소 삽입/삭제는 O(1)의 시간 복잡도를 가짐. 즉 상수 시간 내에 할 수 있음.  

 

파이썬은 내부적으로 동적 배열이라는 걸 사용해서, 배열의 길이가 늘어나도 O(1)의 시간 복잡도가 걸리도록 설계함. 

그래서 파이썬의 배열은 LinkedList로 쓸 수 있고, 배열로도 쓸 수 있는 효율적인 자료구조임. 

 

출처: https://spartacodingclub.kr/online/algo

스파르타코딩클럽 [알고보면 알기쉬운 알고리즘]

박현준 튜터 강의에서.