배열 vs 연결리스트

배열은 연속된 메모리 공간에 데이터를 저장

연결리스트는 연속되지 않은 메모리 공간에 데이터 저장

 

배열은 삽입과 삭제에는 O(n)이 걸리고 참조에는 O(1)이 걸립니다.

 

연결리스튼 삽입과 삭제에는 O(1)이 걸리고 참조에는 O(n)이 걸립니다.

 

그렇기에 데이터추가나 삭제를 많이 하는 것은 연결 리스트가 좋으며, 그게 아니고 참조를 많이 하는 자료형이 필요하면 배열로 하는 것이 좋습니다.

 

왜 연결리스트의 삽입삭제가 O(1) O(n)인지에 대한 설명은 따로 포스팅을 해놓았습니다.

https://sudoju.tistory.com/218

Linked_List

끄읕