동적배열과 링크드리스트에 대해 알아보기

동적배열

일반적으로 배열은 정해진 원소크기만을 넣을 수 있다. 하지만 동적배열의 경우 배열을 다 채운 상황에서도 원소를 추가하면 배열의 크기가 늘어나게 된다. 하지만 동적배열의 경우 약간 눈가림에 불가하다고 생각될 수 있는데 실제로는 메모리에 원소 10칸의 공간을 할당받아 놓고 사용자에게 보여지는 배열의 크기를 작게 표시하는 것이다. 즉 사용자가 동적배열 6칸을 선언해도 실제로 사용하는 메모리는 10칸의 메모리다. 따라서 동적배열이 사용하는 용량은 사용하는 동적배열의 크기보다 크게 된다. 만약 동적배열에 할당된 10칸의 메모리를 다채우게 되면 새롭게 20칸의 메모리를 할당받고 11칸의 동적배열이 생겨나게 된다. 이 때 기존의 10칸에 있던 원소들을 새롭게 20칸의 배열로 옮기는 과정에서 배열에 크기에 비례하는 선형시간이 걸리게 된다. 

링크드리스트(연결리스트)

링크드리스트는 원소가 다음 원소의 메모리 주소를 가지고 있는 것이다. 링크드리스트의 특징을 비유하자면 10칸짜리 지하철있는데 6~8칸을 제거하고 싶다면 5칸에 바로 9칸을 연결하면 된다. 실제 링크드리스트에서는 5칸에서 다음 칸의 주소를 9칸의 주소로 변경해 주면 된다. 링크드 리스트는 이런 특징으로 인해 중간에 여러 개의 원소를 한 번에 제거하거나 추가하는 것을 매우 간단하게 할 수 있다.  만약 이렇게 중간에 삽입과 삭제를 하지 않는다면 동적배열을 쓰는 것이 좋다.