[Python]Array or LinkedList

파이썬은 배열과 링크드 리스트 두가지 종류의 배열(?)이 있다고 한다 ㅎㅎ...후

1. Array 

특징은 이러하다

[0] - [1] - [2] - [3] - [4] - [5] - [6] - [7]
8개의 배열에서 +1개를 더 추가 하려고 하면 
[] - [] - [] - [] - [] - [] - [] - [] - []
0     1     2    3     4    5    6    7    8 
9개의 방을 만들어준 후 복사 이동 해야 한다.

한번 만들어진 배열은 새로 추가 하려면 새로운 배열을 만든 후 이동 해야 한다 

2. Linked List

# 처음 상태                       내 위치
train_compartments = ["기관실"] -> ["시멘트"] -> ["자갈"] -> ["밀가루"] -> ["우편"]
# 1번 이동                                                내 위치
train_compartments = ["기관실"] -> ["시멘트"] -> ["자갈"] -> ["밀가루"] -> ["우편"]
# 2번 이동                                                                     내 위치
train_compartments = ["기관실"] -> ["시멘트"] -> ["자갈"] -> ["밀가루"] -> ["우편"]
# 3번 이동                                                                                         내 위치
train_compartments = ["기관실"] -> ["시멘트"] -> ["자갈"] -> ["밀가루"] -> ["우편"]
# 4번 이동                                                                                                            내 위치
train_compartments = ["기관실"] -> ["시멘트"] -> ["자갈"] -> ["밀가루"] -> ["우편"]

이렇게 마지막 "우편"칸 까지접근하려면 모든 요소들을 지나 우편으로 향해야 한다.
하지만 Array 의 상황처럼 한가지 요소를 추가 해주려고 할땐 일이 Array 보단 수월하다

예를 들어 자갈칸과 밀가루칸사이에 흑연칸을 추가로 생성해주려고 하면
자갈과 밀가루사이의 연결고리를 끊고 그 포인터를 새로운 흑연칸에 연결 시켜주면 되는 것이다. 
# 처음 상태
["기관실"] -> ["시멘트"] -> ["자갈"] -> ["밀가루"] -> ["우편"]
                              ["흑연"] 을 중간에 넣어야 합니다

# 1. 자갈 칸의 연결고리를 흑연 칸으로 연결하고,
["자갈"] -> ["흑연"]   ["밀가루"] -> ["우편"]

# 2. 흑연 칸으로 연결고리를 밀가루 칸으로 연결합니다. 
["자갈"] -> ["흑연"] -> ["밀가루"] -> ["우편"]

정리

특정원소 조회 : Array O(1) 사용
중간에 삽입삭제 : LinkedList  O(1)사용