연결리스트는 배열보다 메모리 사용량이 높다

연결리스트(Linked List)는 메모리 상 서로 떨어져있는 노드(Node)들이, 포인터로 서로 연결되는 구조를 가지고 있다. 때문에 노드는 기본적으로 자신이 가지는 값(data) 외에도 다음 노드의 위치를 가리키는 포인터(next) 또한 요소로 가지게 된다.

그러다보니 같은 개수의 데이터를 보유한 배열과 연결리스트를 비교해보면, 연결리스트가 배열보다 메모리를 더 점유하게 된다.

• 32-bit int형 원소 다섯 개를 가지고 있다고 가정
  • 배열의 경우 4 bytes * 5 = 20 bytes
  • 단반향 연결리스트의 경우 (4 bytes * 5) + (포인터 4 or 8 bytes * 5) = 40~60 bytes

만약 양뱡향 연결리스트(Doubly Linked List)라면 노드에 포인터가 하나 더 늘어나기 때문에 메모리 사용량은 더 늘어난다.

하지만 연결리스트의 경우는 필요할 때, 필요한 만큼의 노드를 가지기 때문에 실질적으로 낭비하는 공간은 없는 반면, 배열은 연속된 메모리 블럭을 미리 할당하므로, 데이터의 수가 급격히 줄거나 예상보다 적을 경우 메모리가 낭비될 수 있다.

확장 🌱

• 연결리스트의 경우 포인터 때문에 메모리 사용량이 늘어나게 되는데, 이를 줄일 수 있는 방법이 있을까?
  • Doubly linked list의 경우는 XOR 연결리스트가 있다
• 배열에서 사용하지 않는 공간을 낭비하지 않기위해 처리하는 방법이 따로 있을까
  • 원소의 개수와 배열의 크기를 비교해서 일정 수치 이하로 내려갈 경우, 배열의 크기를 반으로 줄이는 함수를 구현할 수 있다.
  • 반대로 배열을 확장해야 할 때는 한 칸씩 공간을 추가하는 것 보다, 배열 크기의 두 배로 늘리면 배열의 생성과 기존 원소의 복사 과정의 연산 횟수를 크게 줄일 수 있다.

관련 노트 📘

• 250515204930 - 시간복잡도를 알아야 프로그램의 성능을 예측할 수 있다