💫연결 리스트 (Linked List)란?

데이터를 순서대로 저장하는 자료 구조로, 각 데이터를 노드(Node)라는 단위로 나누고 각 노드는 데이터와 다음 노드를 가리키는 포인터로 구성됩니다.
각 노드는 메모리 상에서 분산되어 있고, 순차적으로 이어져 있음으로써 전체 구조를 형성합니다

노드 (Node)

• 각각의 데이터 요소를 담고 있는 기본 단위입니다.
• 노드는 데이터 필드와 다음 노드를 가리키는 링크로 구성됩니다.

헤드 (Head)

• 연결 리스트의 시작 지점을 나타내는 노드를 헤드라고 부릅니다.
• 헤드는 첫 번째 노드의 위치를 나타내며, 연결 리스트의 시작점을 제공합니다.

링크 또는 포인터

• 각 노드는 다음 노드를 가리키는 링크를 포함합니다.
• 마지막 노드는 보통 NULL이나 특별한 값으로 링크가 표시되어 연결의 끝을 나타냅니다.

종류

단일 연결 리스트 (Singly Linked List)

• 각 노드가 다음 노드를 가리키는 방식으로 이루어진 연결 리스트입니다.
• 간단하고 메모리를 효율적으로 사용하지만, 역방향으로 탐색하는 데에는 비효율적일 수 있습니다.

이중 연결 리스트 (Doubly Linked List)

• 각 노드가 이전 노드와 다음 노드를 가리키는 방식으로 이루어진 연결 리스트입니다.
• 양방향으로 탐색이 가능하며, 단일 연결 리스트보다는 메모리를 더 많이 사용합니다.

원형 연결 리스트 (Circular Linked List)

• 마지막 노드가 첫 번째 노드를 가리키는 방식으로 이루어진 연결 리스트입니다.
• 연결 리스트를 순환하는 형태를 띠고 있습니다.

연결 리스트의 장단점

장점

• 삽입 및 삭제 용이성: 중간에 노드를 추가하거나 삭제할 때 배열보다 쉽고 빠르게 수행할 수 있습니다.
• 동적 크기 조절: 동적으로 크기를 조절할 수 있어 메모리를 효율적으로 사용할 수 있습니다.
• 유연성: 다양한 종류의 연결 리스트가 있어, 특정 상황에 맞게 선택하여 사용할 수 있습니다.

단점

• 랜덤 액세스 어려움: 특정 인덱스에 직접 접근하는 데에는 추가적인 탐색이 필요하므로, 랜덤 액세스가 빈번한 경우에는 배열보다 성능이 떨어집니다.
• 메모리 소모: 각 노드가 다음 노드를 가리키는 포인터를 갖기 때문에 메모리 사용이 배열보다 많을 수 있습니다.

연결 리스트 추천 상황

• 데이터의 삽입 및 삭제가 빈번한 경우
• 동적 크기 조절이 필요한 경우
• 랜덤 액세스가 드물고 순차적인 접근이 많은 경우