[CS/Computer Science][자료구조/Data Structure] 연결 리스트

가장 자주쓰이는 기본적인 자료 구조인 배열에 이어서, 이번 포스트에서는 연결리스트에 대해 알아보도록 하겠습니다.

1. 노드(node)와 연결 리스트(Linked list)

1.1 노드

• “저장하고자 하는 데이터 + 다음 노드의 위치(메모리 상의 주소)”
  • 특정 노드에 접근할 수 있다면, 다음 노드의 위치도 알 수 있음 → 다음 노드의 데이터에 접근 가능
  • 연결 리스트의 구성 단위
    
    

1.2 연결 리스트

• 노드의 모음으로 구성된 자료구조
• 노드들이 한 쪽 방향으로 꼬리를 무는 형태로 구성
  • 연결 리스트의 첫번째 노드: 헤드
  • 연결 리스트의 마지막 노드: 꼬리
• 모든 노드들이 반드시 메모리 내에 순차적으로 저장되어 있지 않음 ⇒ 연속적 데이터를 불연속적으로 저장할 때 유용

2. 연결 리스트 내 요소 접근

2.1 요소 접근

• 앞에서부터 순차적으로 접근할 수밖에 없음
• $O(n)$
  
  

2.2 요소 추가 및 삭제

• 연결 리스트의 강점
  • 추가 / 삭제 과정에서, 요소 재정렬이 불필요하기 때문
  • 노드의 위치만 주어진다면, 빠르게 요소에 접근하여 추가 / 삭제 가능
• $O(1)$
  
  

3. 연결 리스트의 종류

3.1 싱글 연결 리스트(single linked list)

• 기본 연결리스트
  • 한 쪽 방향으로 꼬리에 꼬리를 무는 형태
  • 노드 내에 다음 노드의 위치 정보 탑재
• 단점
  • 이전 노드의 위치는 알 수 없음 → 단방향 검색만 가능
    
    

3.2 이중 연결 리스트(double linked list)

• 싱글 연결 리스트의 단점 보완
  • 이전 노드 주소에 관한 정보도 포함
  • “이전 노드 주소 + 데이터 + 다음 노드 주소”의 형태
  • 단방향 형태가 아닌 양뱡향 형태로 연결되어 양방향 탐색 가능
• 단점
  • 추가적인 메모리 공간 필요($\because$ 이전 노드 주소에 대한 메모리 추가)
    
    

3.3 환형(원형) 연결 리스트(circular linked list)

• 마지막 노드(꼬리 노드)가 맨 처음 노드(헤드 노드)를 가리키는 연결 리스트
  • 순환하는 원형 형태로 연결된 연결 리스트
  • 이중 연결 리스트도 환형 연결 리스트로 구성 가능
• 모든 노드 데이터를 여러 차례 순회해야 할 때 유용