티스토리 뷰
[한빛아카데미] 자바로 배우는 쉬운 자료구조 책으로 학습한 내용을 정리한 것입니다.
* 연결 자료구조/비순차 자료구조(Linked Data Structure/Nonsequential Data Structure)
- 순차 자료구조 방식에서의 연산 시간에 대한 문제와 저장 공간에 대한 문제를 개선한 자료 표현 방식
- 순차 자료구조 방식에서처럼 원소의 논리적인 순서와 물리적인 순서가 일치할 필요 없음
- 각 원소에 저장되어있는 다음 원소의 주소에 대한 참조에 의해 연결되는 방식으로, 물리적인 순서를 맞추기 위한 오버헤드 발생X
- 여러 개의 작은 공간을 연결하여 전체를 표현하므로 크기 변경이 유연하고, 조금 더 효율적으로 메모리 사용할 수 있음
* 노드(Node)
- 연결 자료구조 방식에서<원소 = 데이터 필드(Data Field), 주소 = 링크 필드(Link Field)> 단위로 저장함
- 위와 같은 단위구조를 노드라고 함
- 링크/참조(Reference) : 링크 필드는 메모리 참조 변수를 사용하여 주소에 대한 참조값을 저장하는 것
* 연결 리스트(Linked List)
- 순차 리스트의 원소를 찾기 위해 다음 원소에 대한 정보 필요 -> 포인터 변수 이용, 추가 기억공간 요구
- 포인터를 사용함으로써 노드의 삽입/삭제 용이함
- 연속적인 기억공간이 없어도 저장 가능함
* 연결 리스트의 단점
- 알고리즘 구현(프로그램 복잡성)이 복잡함
- 노드 탐색 시 무한 루프 가능성 있음
- 주소 저장으로 인한 용량 낭비
- 처음부터 연결을 따라 추적하여 임의의 원소를 처리함 -> 오버헤드 발생할 수 있음
- 데이터가 메모리 곳곳에 저장되어 있고, 주소로 연결했기 때문에 데이터 캐싱 적합X -> 처리 속도 느려짐
[연결 리스트 구조]
[연결 리스트 원소 삽입]
[연결 리스트 원소 삭제]
* 원형 연결 리스트(Circular Linked List)
- 단순 연결 리스트에서 선행 노드에 접근하기가 어렵다는 점 개선하여 구성
- 마지막 노드가 리스트의 첫번째 노드를 가리키게 하여 리스트의 구조를 원형으로 만든 연결 리스트
[원형 연결 리스트 구조]
* 이중 연결 리스트(Doubly Linked List)
- 원형 연결 리스트에서 현재 노드의 바로 이전 노드에 접근하려면 전체 리스트를 한바퀴 순회해야 하는 점을 개선하여 구성
- 양쪽 방향으로 순회할 수 있도록 연결한 리스트
[이중 연결 리스트 구조]
'개인공부 > 자료구조|알고리즘' 카테고리의 다른 글
| [자료구조] 트리(Tree) (0) | 2023.11.20 |
|---|---|
| [자료구조] 큐(Queue) (0) | 2023.11.20 |
| [자료구조] 스택(Stack) (0) | 2023.11.20 |
| [자료구조] 리스트(List) (0) | 2023.11.20 |
| [자료구조] 자료구조의 분류 (0) | 2023.11.20 |