연결리스트(Linked List)
각 노드가 데이터와 다음 노드를 가리키는 포인터를 가지고 있으며 포인터로 연결되어 있는 자료구조이다.
- 데이터를 링크로 연결해서 관리하는 자료구조
- 자료의 순서는 정해져 있지만, 메모리상 연속성이 보장되지는 않음
- 노드: data와 다음 노드를 가리키는 포인터를 포함한다.
- 처음 노드는 head, 마지막노드는 tail
장점
- 데이터공간을 미리 할당할 필요 없음
- 데이터 추가/삭제 용이
단점
- 연결구조를 위한 별도 데이터 공간 필요(링크정보 저장)
- 연결정보를 찾는시간 필요(메모리상 연속되어있지 않아 느림)
- 데이터 추가, 삭제시 앞뒤 데이터의 연결을 재구성하는 작업 필요
연결리스트의 종류
단일 연결리스트: 각 노드에 다음 노드를 가리키는 포인터가 있다.
양방향 연결리스트: 각 노드에 이전노드를 가리키는 포인터와 다음노드를 가리키는 포인터가 있다.
원형 연결리스트: tail의 다음 노드가 head가 되는 구조로 끝이 없고 순환되는 구조이다.
'STUDY > 자료구조' 카테고리의 다른 글
| [Java] 힙(Heap) 자료구조 (1) | 2023.10.23 |
|---|---|
| [Java] HashMap 정리 (1) | 2023.10.20 |
| 선형자료구조 - Array (4) | 2023.10.19 |
| 큐(Queue) 자료구조 정리 (0) | 2023.10.17 |
| 스택(Stack) 정리 (0) | 2023.10.17 |