CS 공부일지[자료구조]-(1)연결 리스트

📝 자료구조 - (1) 연결 리스트

• 선형 자료 구조
• 각 노드가 다음 노드를 가리키는 포인터(pointer)로 구성되어 있는 구조

• 장점
  • 크기를 동적으로 조정 가능
  • 삽입/삭제가 상대적으로 빠름 [ 삽입/삭제 시간 복잡도 O(1) ]
  • 배열과 달리 임의 접근 가능
  • 노드 단위 메모리 사용

• 단점
  • 순차 접근 시 배열보다 느릴 수 있음
  • 랜덤 엑세스 지원 X
  • 포인터 오류 발생 가능성 있음
  • 포인터를 추가적으로 저장하기에 더 많은 메모리 사용량

⌗ 랜덤 엑세스를 지원하지 않는 단점 극복을 위해 일부 개선된 연결 리스트
--> 트리플 링크드 리스트(Triple linked list)

• 단일 연결 리스트 (Python)

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

• 트리플 링크드 리스트 (Python)

class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

--> 기본 연결 리스트와 달리 이전 노드의 주소를 추가로 저장하기에 양방향으로 탐색

⌗ 메모리 낭비 줄이기 위해 연결 리스트의 노드를 미리 할당해두고 필요할 때 마다 사용
--> 메모리 풀(Memory pool)