단일 연결 리스트는 선형으로 연결된 데이터 구조로, 노드로 구성되어 있다. 각 노드는 내용이 저장된 data 변수와 다음 노드를 가리키는 pointer로 구성되어 있다. 연결 리스트는 이런 노드들의 첫 원소를 가리키는 포인터를 가지며, 연산에 걸리는 시간을 훨씬 절약하기 위해 마지막 노드를 가리키는 포인터를 가질 수도 있다. 전체 노드 수를 저장하는 length 변수를 추가할 수도 있다.
- 연결 리스트의 크기는 고정되어 있지 않다. (가변 크기)
- 배열에 비해 원소의 제거와 추가가 쉽다.
- 원소에 순차적으로 접근해야 한다. (임의 접근 불가)
- 포인터를 저장하기 위해 추가적인 메모리가 필요하다.
| 작업 | 평균 | 최악 |
|---|---|---|
| 접근 | ||
| 탐색 | ||
| 삽입 | ||
| 제거 |
class LinkedList {
<<<<<<< HEAD
Node head; // 첫 원소를 가리키는 포인터
Node tail; // (Optional) 마지막 원소를 가리키는 포인터
int length; // (Optional) 전체 노드 수
class Node {
int data; // 노드의 데이터
Node next; // 다음 노드를 가리키는 포인터
}
}