2025-07-30 00:30
Status:
Tags: 자료구조
연결 리스트
기존 배열 이 연속된 메모리라는 이유로 고정 크기라는 문제 있음 → 실제 메모리 연속되지 않아도 다음 위치를 저장해서 찾아가면 사실상 배열과 동일한 기능 가능하지 않을까?
구조
- 노드의 연쇄
- 각 노드는 ‘데이터’와 ‘포인터’가짐
- 시작 노드 헤드 포인터
- 마지막 노드 NULL 포인터
struct Node {
int data; // 데이터
struct Node *next; // 다음 노드 주소
}종류들 많은데 보통 싱글이나 더블이 자주 쓰임
연산
배열과의 차이점은 배열은 인덱스 있으면 바로 O(1) 으로 접근 가능 반면 연결 리스트는 인덱스 있어도 해당 위치를 직접 가기위해 처음부터 포인터 타고 가야해서 O(n)
반면 배열은 중간에 삽입, 삭제 하면 다 밀어줘야 해서 O(n)인데 연결 리스트는 그냥 포인터만 바꿔주면 끝이라 O(1) 연결 리스트가 메모리 더 쓰는거 빼면 거의 완벽한 대비라 자기 사용하는 데이터 특징에 따라 고르면 될듯 예컨대 인덱스로 값 가져오는거 많으면 배열로 삽입 삭제가 많으면 연결리스트로 하는 식
파이썬에선 큐에서 썻던 deque 라이브러리 쓰면 됨 그래도 아래는 전체 직접 구현 코드 파이썬 코드