본문 바로가기

자료구조

[자료구조] Linked List

728x90

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)과 같은 자료구조 구현
728x90

'자료구조' 카테고리의 다른 글

[자료구조] 여러가지 배열 종류  (0) 2024.10.31
[자료구조] 큐(Queue)  (0) 2024.10.12
[자료구조] 스택(Stack) Java 예제 포함  (1) 2024.10.11
[자료구조] Array 배열  (0) 2024.08.16