[자료구조] Linked List란?

**Linked List (링크드 리스트)**는 데이터를 **노드(Node)**라는 단위로 저장하는 선형 데이터 구조입니다.

각 노드는 데이터와 **다음 노드에 대한 참조(혹은 포인터)**를 가지고 있어,

데이터를 연속된 메모리 공간에 저장하는 대신,

각 노드가 다른 노드를 참조하면서 연결됩니다.

1. 구조

• **노드(Node)**는 두 가지 주요 요소로 구성됩니다:
  1. 데이터: 실제로 저장하려는 값이나 객체
  2. 다음 노드를 가리키는 포인터(혹은 참조): 리스트 내에서 다음 노드를 가리키는 참조(포인터)를 가짐
• 예시로, 각 노드는 다음과 같이 구조화됩니다:

  [데이터 | 다음 노드 포인터] → [데이터 | 다음 노드 포인터] → [데이터 | null]
  

  마지막 노드는 null을 참조하여 끝을 나타냅니다.

2. 종류

• 단일 연결 리스트 (Singly Linked List):
  • 각 노드는 하나의 포인터만 가집니다. 즉, 현재 노드가 다음 노드만을 가리키고 있습니다.
  • 마지막 노드는 null을 가리킵니다.
• 이중 연결 리스트 (Doubly Linked List):
  • 각 노드는 두 개의 포인터를 가집니다: 하나는 다음 노드를 가리키고, 다른 하나는 이전 노드를 가리킵니다.
  • 양방향으로 탐색이 가능하므로, 삽입과 삭제 시 더 효율적일 수 있습니다.
• 원형 연결 리스트 (Circular Linked List):
  • 마지막 노드가 null을 가리키지 않고, 첫 번째 노드를 가리키는 형태로 순환 구조를 이룹니다.
  • 단일 연결 리스트와 이중 연결 리스트가 원형으로 연결될 수 있습니다.

3. 특징

• 동적 크기 조정: 배열과 달리 메모리 공간을 동적으로 할당하므로, 크기를 사전에 정할 필요가 없습니다. 삽입과 삭제가 동적입니다.
• 비연속적인 메모리 할당: 배열은 연속된 메모리 공간을 사용하는 반면, 링크드 리스트는 각 노드가 다른 메모리 위치에 저장됩니다.
• 순차적 접근: 데이터에 직접 접근하려면 앞에서부터 순차적으로 탐색해야 하므로, 인덱스를 통한 빠른 접근이 불가능합니다. (O(n) 시간이 걸림)

4. 주요 연산

• 삽입 (Insertion):
  • 원하는 위치에 노드를 추가할 수 있습니다. (특히, 앞이나 중간에 삽입할 때 유리)
• 삭제 (Deletion):
  • 특정 노드를 삭제하는 연산도 빠르게 할 수 있습니다.
• 탐색 (Traversal):
  • 모든 노드를 순차적으로 탐색하면서 데이터를 확인합니다.

5. 장점과 단점

• 장점:
  • 크기 변경이 자유롭고, 동적 메모리 할당으로 메모리 낭비가 적습니다.
  • 리스트의 중간이나 맨 앞에 요소를 삽입하거나 삭제하는 데 유리합니다.
• 단점:
  • 데이터에 대한 빠른 인덱스 접근이 불가능합니다.
  • 추가적인 포인터 메모리 사용이 필요하여, 배열에 비해 메모리 오버헤드가 발생합니다.

6. 사용 예시

• **큐(Queue)나 스택(Stack)**의 구현
• **그래프(Graph)**에서 인접 리스트 형태로 사용
• 메모리 관리: 운영 체제에서 프로세스 제어 블록을 링크드 리스트로 관리하기도 함

7. 시각적 예시

• 단일 연결 리스트:

  [1 | →] → [2 | →] → [3 | →] → [4 | null]
  

• 이중 연결 리스트:

  null ← [1 | ← →] ↔ [2 | ← →] ↔ [3 | ← →] → null
  

링크드 리스트는 데이터 삽입과 삭제가 빈번하게 일어나는 경우에 유리한 자료 구조로 사용됩니다.