들어가기 전에

순차적인 데이터나 많은 양의 데이터를 정리하는 자료 구조인 연결 리스트에 대해 살펴보도록 하겠습니다.

학습 목표

연결 리스트의 정의와 그 구성 요소에 대해 설명할 수 있습니다.

핵심 단어

• 연결 리스트
• 노드
  
• 배열

강의 듣기

연결 리스트

포인터를 사용하여 여러 개의 노드를 연결하는 자료 구조를 연결 리스트라고 합니다. 

연결 리스트의 기본 구성 요소는 노드입니다. 노드에는 두 가지 정보가 들어있습니다. 첫 번째는 인접한 노드를 가리키는 next라는 이름의 포인터, 두 번째는 우리가 노드에 넣는 데이터를 가리키는 포인터입니다. (노드 D의 경우, 다음에 아무것도 없기 때문에 null을 가리킵니다)

이 리스트는 head라는 이름의 포인터에서 시작합니다. Head는 리스트의 첫 번째 노드를 가리킵니다. 힙에서는 이 연결 리스트의 head만 알고 있기 때문에, head.next 혹은 head.data 등으로 노드의 내용을 찾습니다. 하지만 연결 리스트의 길이가 매우 길 경우, 계속 head 뒤에 next를 붙일 수는 없습니다. 그래서 임시 포인터를 사용하여 탐색하는 방법을 사용합니다.

다음 수업에서는 이러한 연결 리스트를 어떻게 만들고 제거하는지 공부하도록 하겠습니다.

배열과의 차이점

배열 또한 순서대로 여러 데이터를 저장할 때 사용한다는 공통점이 있습니다. 하지만 배열은 필요한 요소보다 너무 크게 만들거나 너무 작게 만들어 배열의 크기를 조정해야 한다는 문제점이 있습니다.

배열과 다르게, 연결 리스트는 항상 맞는 크기로 만들어지도록 설계되어 있습니다. 그래서 순차적인 데이터나 많은 양의 데이터가 있을 때 자주 사용됩니다.

생각해보기

1) 일상생활에서 연결 리스트처럼 여러 물건을 연결하여 정리하는 것에는 어떤 것이 있나요?