Array와 Linked List

[Array]

1. 배열은 크기가 정해진 데이터의 공간. 한 번 정해지면 바꿀 수 없음

2. 배열은 각 원소에 즉시 접근 가능. 원소의 순서는 0부터 시작, 인덱스라고 부름

   -> "즉시 접근 가능하다" : 상수 시간 내에 접근할 수 있음을 의미함. O(1)의 시간복잡도

3. 배열은 원소를 중간에 삽입 또는 삭제하려면 모든 원소를 다 옮겨줘야함

   최악의경우 배열의 길이 N 만큼 옮겨야하기 때문에 O(N)의 시간복잡도를 가짐

4. 원소를 새로 추가하려면 새로운 공간을 할당해야함. 아주 비효율적인 자료구조임

---

 

[Linked List] (like 화물열차..)

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

   포인터(like 연결고리..)로 이어주기만하면 자유자재로 늘어날 수 있음

2. 리스트는 특정 원소에 접근하려면 연결 고리를 따라 탐색해야함

   최악의 경우 모든 노드(like 화물칸..)를 탐색해야 하기 때문에 O(N)의 시간복잡도를 가짐

   연결고리는 포인터, 각 화물칸은 노드

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

   원소 삽입/삭제를 O(1)의 시간복잡도 안에 할 수 있음

---

경우	Array	Linked List
특정 원소 조회	O(1)	O(N)
중간에 삽입/삭제	O(N)	O(1)
데이터 추가	모든 공간이 다 차버리면 새로운 공간을 할당받아야함	모든 공간이 다 찼어도 맨 뒤의 노드만 동적으로 추가하면 됨
정리	데이터에 접근하는 경우가 빈번하다면 Array를 사용합시다	삽입/삭제가 빈번하다면 LinkedList를 사용하는 것이 더 좋음

---

" 파이썬의 배열은 list라고 부르고 append를 하는데, 파이썬의 배열은 list인가요 array인가요? "

: 파이썬의 list는 array로 구현되어 있음

" append 메소드를 쓰면 새로운 배열을 생성해서 안좋은거 아닌가요?? "

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

  파이썬의 배열은 Linked List로 쓸 수 있고, 배열로도 쓸 수 있게 만든 효율적인 자료구조이다

  라고 생각하면 됨