[핵심 답변]
Linked List는 Node라는 구조체로 이루어져 있는데, Node는 데이터 값과 다음 Node의 address를 저장합니다. Linked List는 물리적인 메모리상에서는 비연속적으로 저장이 되지만 Linked list를 구성하는 각각의 Node가 next Node의 address를 가리킴으로써 논리적인 연속성을 가진 자료구조입니다.
[면접 TIP]
Linked List는 tree, graph등 다른 자료구조를 구현할 때 자주 쓰이는 기본 자료구조 입니다. 면접에서 Linked list를 설명할 때에는 메모리상에서 불연속적으로 데이터가 저장되는 점과 Node의 next address를 통해 불연속적인 데이터를 연결하여 논리적 연속성을 보장한다는 점을 중심으로 설명하면 됩니다.
또한, 데이터가 추가 되는 시점에서 메모리를 할당하기 때문에 메모리를 좀 더 효율적으로 사용할 수 있다는 장점도 답변으로 구성하면 좋습니다.
물리적 메모리 관점에서 본 Linked list - 비연속적
논리적 연속성
각 Node들은 next address정보를 가지고 있기 때문에 논리적으로 연속성을 유지하면서 연결되어 있습니다. Array의 경우 연속성을 유지하기 위해 물리적 메모리 상에서 순차적으로 저장하는 방법을 사용하였고, Linked list에는 메모리에서 연속성을 유지하지 않아도 되기 때문에 메모리 사용이 좀 더 자유로운 대신, Next address를 추가적으로 저장해야 하기 때문에 데이터 하나당 차지하는 메모리가 더 커지게 됩니다.
(1) 그림에서 링크드리스트가 연속적으로 저장된것처럼 보이지만 실제 메모리상에서는 (2)와 같다
(1) 논리적 연속성
(2) 물리적 불연속성
시간복잡도
Array의 경우 중간에 데이터를 삽입/삭제하게 되면 해당 인덱스의 뒤에 있는 모든 원소들은 shift를 해야만 했습니다. 그러다 보니 의 시간복잡도를 갖게 되었습니다. 하지만 Linked list를 물리적으로 옮길 필요없이 next address가 가리키는 주소값만 변경하면 되기 때문에 의 시간복잡도로 삽입/삭제가 가능합니다.
Linked list | |
access | |
search | |
insertion | |
deletion |