배열과 링크드리스트

배열과 링크드리스트의 차이는?

배열은 메모리주소를 연속해서 쓴다는 것이고

링크드리스트는 연속되지 않아도 된다는 것이다.

 

그래서 배열은 값을 찾을 때 O(1)이 걸리고, 링크드리스트는 O(n)이 걸린다.(링크를 따라가야하기 때문)

 

삽입 삭제는 배열은 연속적으로 해야하기때문에 조금 귀찮다. 한칸씩 밀거나 땡겨야하기 때문데..

대신 링크드리스트는 링크로 연결되어있기때문에 배열보다 편하게 할 수 있다.