확실히 알고가야 하는 자료구조, 알고리즘 개념 (1) : Linked List

Linked List

 

컴퓨터에 자료를 저장하는 자료구조 중 하나입니다.

 

일렬로 연결된 데이터를 저장할 때 사용합니다.

 

데이터, 그 안에 다음 순서의 데이터 주소를 저장해 놓습니다.

 

 

 

---

배열과의 비교

 

배열은 만들어질 때, 방을 만듭니다.

 

이 때, 방은 크기를 줄이거나 늘일 수 없습니다.

 

---

삽입 시,

 

Linked List의 경우, 앞선 노드에 저장되어 있는 다음 노드의 주소를 자신의 것으로 가져오는 형태입니다.

 

 

제거 시,

 

Linked List의 경우, 삭제되어야 하는 노드의 주소를 다음 노드의 주소로 변경해주는 형태입니다.

 

(이 때, 삭제된(실제로는 해당 노드로 향하는 주소가 저장되어있지 않아 삭제된 것 처럼 보이는) 노드는  JAVA에선 자동으로 삭제를 해줍니다. 허나 C#, C++에선 안쓰겠다고 반드시 명시를 해야 삭제가 됩니다. 저장 공간 확보 차원에서 필수적이겠죠.)

 

---

검색 속도 측면에서,

 

Linked List는 주소를 하나하나 찾아다녀야 하기에, Array보다 느릴 수 있습니다.

 

허나,

 

삽입 제거 수정 등에서는 Linked List가 Array보다 빠릅니다.

 

즉, 길이가 정해져 있지 않은 데이터를 Handling할 때에는 Linked List를 이용하는 것이 좋습니다.