[CS / Array vs Linked List] ep03. Linked List에 대해서 설명해주세요.

🤔 면접 질문

Q1. Linked List에 대해서 설명해주세요.

 

A1.  Linked List는 Node라는 구조체로 이루어져 있는데, Node는 데이터 값과 다음 Node의 address(주소)를 저장합니다. Linked List는 물리적인 메모리상에서는 비연속적으로 저장이 되지만 Linked List를 구성하는 각각의 Node가 next Node의 address를 가리킴으로써 논리적인 연속성을 가진 자료구조입니다.

 

 

 

💡 면접 tip

: Linked List는 tree, graph등 다른 자료구조를 구현할 때 자주 쓰이는 기본 자료구조이다. 면접에서 Linked List를 설명할 때에는 메모리상에서 불연속적으로 데이터가 저장되는 점과 Node의 Next address를 통해 불연속적인 데이터를 연결하여 논리적 연속성을 보장한다는 점을 중심으로 설명하면 된다. 또한, 데이터가 추가되는 시점에서 메모리를 할당하기 때문에 메모리를 좀 더 효율적으로 사용할 수 있다는 장점도 답변으로 구성하면 좋다.

 

 

 

1️⃣ 논리적 연속성

 

각 Node들은 다음 주소(Next Address, 다음 언급부터 '다음 주소'로 치환)정보를 가지고 있기 때문에 논리적으로 연속성을 유지하면서 연결되어 있다. Array의 경우 연속성을 유지하기 위해 물리적 메모리 상에서 순차적으로 저장하는 방법을 사용했고, Linked List에서는 메모리에서 연속성을 유지하지 않아도 되기 때문에 메모리 사용이 좀 더 자유로운 대신, 다음 주소를 추가적으로 저장해야 하기 때문에 데이터 하나당 차지하는 메모리가 더 커지게 된다.

 

 

 

2️⃣ 시간 복잡도

 

Array의 경우 중간에 데이터를 삽입/삭제하게 되면 해당 인덱스의 뒤에 있는 모든 원소들은 Shift를 해야만 했다. 그러다보니 O(n)의 시간복잡도를 갖게 되었다. 하지만 Linked list를 물리적으로 옮길 필요 없이, 다음 주소가 가리키는 주소값만 변경하면 되기 때문에 O(1)의 시간복잡도로 삽입/삭제가 가능하다.

 

	Linked list
access	O(n)
search	O(n)
insertion	O(1)
deletion	O(1)