배열과 리스트

 

배열

배열 : 크기가 정해진 데이터의 공간, 한 번 정해지면 바꿀 수 없다.

 

배열은 원소에 즉시 접근할 수 있다. 그 배열의 'Index'를 통해 접근한다.

* 즉시 접근 가능 :  O(1) = 상수 시간 내에 접근이 가능

 

그러나 배열은 수정, 삭제 시 모든 원소를 다 옮겨야 한다.

최악의 경우에는 모든 원소를 다 옮기면서 시간복잡도가 O(N)까지 증가할 수 있다.

 

크기가 정해진 데이터의 공간이기 때문에 원소를 추가할 시, 새로운 배열을 만들어야 하므로 수정에 있어 비효율적

 

---

 

리스트

리스트 = Linked List : 크기가 정해지지 않은 데이터의 공간, 연결고리만 주어진다면 바꿀 수 있다.

 

리스트는 특정 원소에 접근하려면 연결고리를 따라 접근해야 한다.

최악의 경우에는 모든 원소에 다 접근해야 하기 때문에 시간복잡도가 O(N)까지 증가할 수 있다.

 

연결고리 : 포인터

각 원소 : 노드

 

리스트는 수정, 삭제 시 앞과 뒤의 연결고리(포인터)만 변경하면 되기 때문에

시간복잡도가 상수이다.(즉시 변경 가능)

 

---

 

결론

배열 : 데이터에 접근하는 경우가 빈번할 시 사용하면 유리

리스트 : 데이터를 변경, 삭제하는 경우가 많을 시 유리

 

한 것으로 정리를 했으나..

 

애초에 파이썬에서 배열은 리스트 형식으로 나타나고,

시간 복잡도 역시 걱정하지 않아도 된다.

 

'동적 배열'이라는 사기적인 능력이 파이썬의 기능으로 존재하기 때문이다.

 

그래서 append 같은 함수를 사용해도 전혀 문제되지 않았던 것..

 

혹시나 다른 C언어 공부하게 된다면 참조해야지

파이썬 만세..