1.arrays and linked list

유다시티 수업 datastructure and algorithm의 study note입니다.

 

 

Arrays and python lists

array와 list의 가장 큰 차이점은 둘은 array의 경우 index가 있고, list는 없다는 것이다.

실제로 메모리를 할당받을때도 array는 메모리공간의 바로 옆에 데이터가 할당되고, list는 아무 공간에나 저장이 된다.

 

array의 경우 adding 이나 deleting 하는게 time complexity가 좋지 않다. (인덱스를 다 조정해주어야 하기 때문에)

 

*python에서는 list도 index를 갖기 때문에 그 구분이 애매하다.

 

Linked list

각각의 element가 다음 element에 대한 reference가 있다.

따라서 insertion이나 deleting할대 time complexity가 constant하다.

(모든 element를 iterate할 필요가 없고, reference만 pointing을 바꿔주면 되기 때문에)