[자료구조] Linked List

Linked List는 데이터를 저장하는 선형 자료구조 중 하나로, 각 요소가 다음 요소에 대한 참조(포인터)를 가지고 있어 동적으로 크기를 조정할 수 있습니다.

Linked List의 핵심 요소

• 노드(Node): Linked List의 기본 단위로, 각 노드는 두 가지 정보를 가집니다.
  • 데이터(Data): 노드가 저장하는 실제 값.
  • 포인터(Next/Pointer): 다음 노드를 가리키는 참조.
• 헤드(Head): Linked List의 첫 번째 노드를 가리키는 포인터.

Linked List의 종류

1. 단일 연결 리스트(Singly Linked List):
   • 각 노드는 하나의 포인터(Next)만 가짐.
   • 마지막 노드의 포인터 값은 null.
2. 이중 연결 리스트(Doubly Linked List):
   • 각 노드는 두 개의 포인터(Front, Next)를 가짐.
   • 이전 노드와 다음 노드를 가리킴.
   • 양방향 순회 가능.
3. 원형 연결 리스트(Circular Linked List):
   • 마지막 노드가 첫 번째 노드를 가리켜 원형 구조를 형성.

Linked List의 장점

• 동적 크기 조정: 크기가 고정되지 않아 유연하게 조정 가능.
• 효율적인 삽입과 삭제: 중간 요소의 삽입/삭제가 효율적. 포인터만 수정하면 되므로 배열보다 빠름.

Linked List의 단점

• 느린 접근 속도: 배열처럼 인덱스로 접근하지 못하고 처음부터 순차적으로 탐색해야 하므로 느림.
• 추가 메모리 사용: 각 노드는 데이터 외에 포인터를 저장하기 위한 추가 메모리를 사용.

사용 예시

Linked List는 다음과 같은 경우에 사용됩니다:

• 동적으로 크기가 변하는 데이터 구조가 필요할 때
• 삽입/삭제 연산이 빈번한 경우
• 큐(Queue)나 스택(Stack)과 같은 자료구조 구현