1. 단일 연결 리스트
- 각 노드가 하나의 연결만을 가지고 다음 노드에 대한 참조값만 저장하여 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 구조
- 순차적으로 접근해야함
- 노드는 저장되는 데이터와 다음 노드에 접근할 수 있는 참조값을 가지고 있음
- head : 첫 번째 노드를 가리키는 노드 또는 변수.
- pointer : 노드를 탐색하기 위해 해당 노드의 참조값을 일시적으로 저장하고 있는 변수
1) 장점
- 저장되는 데이터의 개수가 예측 불가능할 때 사용 가능
- 데이터를 삽입할 때 노드를 생성하기 때문에 필요한 만큼만 메모리 공간을 사용 -> 상대적으로 메모리 절약 가능
- 데이터의 삽입/삭제가 배열보다 더 간단하고 빠름. 배열은 중간 데이터가 삭제됐을 경우 데이터의 양과 삭제하는 데이터의 위치에 따라 시간이 늘어남
2) 단점
- 노드를 찾을 때 앞에서부터 순차적으로 찾아야 함 -> 인덱스로 접근하는 배열보다 탐색 속도가 느림
- pointer는 항상 head부터 시작해야 함
- 노드 간 연결을 잘못할 시 다음 노드를 영원히 찾을 수 없음
2. 단일 연결 리스트 삽입
1) 맨 앞에 Node 삽입
- head에 접근
- 새로운 노드 생성
- head가 가리키는 다음 노드의 참조값을 새로운 노드의 다음 노드 참조값으로 저장
- head에 새로운 노드의 참조값 저장
2) 중간에 Node 삽입
- 삽입하려는 위치의 이전 노드에 접근
- 새로운 노드 생성
- 이전 노드의 다음 노드 참조값을 새롭게 생성한 노드의 다음 노드 참조값에 저장
- 이전 노드의 다음 노드 참조값에 새로운 노드의 참조값 저장
3. 단일 연결 리스트 삭제
1) 맨 앞의 Node 삭제
- 맨 앞의 노드가 가리키는 다음 노드의 참조값을 head에 저장 -> 삭제할 노드와의 연결이 끊어지고, JVM의 가비지 컬렉터의 스케줄링에 따라 메모리에서 해제됨
2) 중간에 있는 Node 삭제
삭제하려는 노드의 이전 노드에 접근
삭제할 노드의 다음 노드 참조값을 이전 노드의 다음 노드 참조값에 저장 -> 삭제할 노드와의 연결이 끊어지고, JVM의 가비지 컬렉터의 스케줄링에 따라 메모리에서 해제됨
참조
https://www.codelatte.io/courses/java_data_structure
'6. 자료구조 & 알고리즘 > 6-1. 자료구조' 카테고리의 다른 글
자료구조 - [ 이진 트리 순회 ( 깊이 우선 / 너비 우선 ) ] (0) | 2022.08.10 |
---|---|
자료구조 - [ 재귀 - 점화식 관점 / 분할 관점 / 백트래킹 관점 ] (0) | 2022.08.08 |
자료구조 - [ Queue ] (0) | 2022.08.08 |
자료구조 - [ Stack ] (0) | 2022.08.08 |
자료구조 - [ 이중 연결 리스트 ] (0) | 2022.08.06 |