[TIL] 자료구조 - 연결 리스트

※ 연결 리스트

- 포인터를 사용해 여러 노드를 연결하는 자료 구조를 연결 리스트라고 한다.

연결 리스트의 기본 구성 요소는 노드인데 여기엔 두 가지 정보가 들어있다. 첫 번째는 인접한 노드를 가리키는 next라는 이름의 포인터, 두 번째는 우리가 노드에 넣는 데이터를 가리키는 포인터이다.

 

이러한 리스트는 head라는 이름의 포인터에서 시작하고 Head는 리스트의 첫 번째 노드를 의미합니다. 힙에서는 이 연결 리스트의 head만 알고있어 head.next 나 head.data 등으로 노드의 내용을 찾는다. 하지만 연결 리스트의 길이가 긴 경우는 계속 next를 붙이는데 한계가 있어 임시 포인터를 이용해 탐색하는 방법을 사용한다.

 

※ 배열과의 차이

- 배열도 순서대로 여러 데이터를 저장할 때 사용한다는 공통점이 있으나 배열은 필요한 요소보다 너무 크게 만들거나 너무 작게 만들어 배열의 크기를 조정해야 한다는 문제가 있지만 연결 리스트는 항상 맞는 크기로 만들어지도록 설계되어 있어 순차적인 데이터나 많은 양의 데이터가 있을 때 자주 활용한다.