저번 시간에 이어 Linked List는 배열과 같은 기능을 하는 것으로 보이지만, 내부 구조와 작동 방법이 다릅니다. 이번 시간엔 Linked List의 특징과 Array와 다른 점이 무엇인지 알아보겠습니다.
Q: Linked List에 관해서 설명해 주세요.
Node라는 구조체로 이루어져 있는데, Node는 데이터 값과 다음 Node의 address로 구성됩니다. Linked List는 물리적인 메모리상에서는 비연속적으로 저장 되지만, 각각의 Node가 다음 Node의 address를 가리킴으로써 논리적인 연속성을 가진 자료구조입니다.
메모리 할당이 데이터 추가 시 이루어지기 때문에, 메모리를 좀 더 효율적으로 사용할 수 있으며 물리적 연속성을 유지하지 않아도 되는 이유로 메모리 사용이 자유로운 대신, Next address를 추가적으로 저장해야 하기 때문에 데이터 하나당 차지하는 메모리가 더 커지게 됩니다.
Q: Linked List의 시간복잡도는 어떻게 되나요?
| Linked List | |
|---|---|
| access | O(n) |
| search | O(n) |
| insertion | O(1) |
| deletion | O(1) |
Q: Linked List를 Array와 비교하여 설명해 주세요.
Array와 다르게 Linked List는 물리적 메모리상으로 연속적이지 않지만, 메모리 주소값을 저장함으로써 논리적 연속성을 띕니다. 저장할 데이터의 크기를 모르는 상태에서 Array보다 좋은 performance를 발휘하며 삽입, 삭제가 빈번한 상황에서 권장됩니다.
마치며
오늘은 Linked List에 대해 간단하게 알아보았는데요. 자료구조의 특징 외에도 작동 방법을 비교해가며 설명할 수 있어야 합니다. 모두 장, 단점이 존재하니 쓰임새도 다릅니다. 어떤 기능에서 사용되는지에 대한 답변도 준비해보시길 바랍니다.
다음 시간에는 Queue 자료구조에 대해 알아보겠습니다.
답글 남기기