728x90
반응형
이중 연결 리스트(doubly linked list)
- 양쪽 방향으로 순회할 수 있도록 노드를 연결한 리스트
- 이중 연결 리스트의 노드 구조
ㄴ 두 개의 링크 필드와 한 개의 데이터 필드로 구성
ㄴ llink(left link) 필드 : 왼쪽 노드와 연결하는 포인터
ㄴ rlink(right link) 필드 : 오른쪽 노드와 연결하는 포인터
llink | data | rlink |
● | ● |
// 노드 구조에 대한 구조체 정의
public class DblNode {
DblNode llink;
String data;
DblNode rlink;
};
- 리스트의 이중 연결 리스트 구성
1 ● |
→ | 1 | → ← |
2 | ||||
null | data1 | 2 ● |
1 ● |
data2 | null |
- 원형 이중 연결 리스트
1 ● |
➥ ☇ |
1 | → ← |
2 | → ← |
3 |
⤴ ↰ |
||||||
3 ● |
data1 | 2 ● |
1 ● |
data2 | 3 ● |
2 ● |
data3 | 1 ● |
- 이중 연결 리스트에서의 삽입 연산 과정
① 삽입할 노드를 가져온다
② 새 노드의 데이터 필드에 값을 저장
③ 새 노드의 왼쪽 노드의 오른쪽 링크(rlink)를 새 노드의 오른쪽 링크(rlink)에 저장
④ 왼쪽 노드의 오른쪽 링크(rlink)에 새 노드의 주소를 입력
⑤ 새 노드의 오른쪽 노드의 왼쪽 링크(llink)를 새 노드의 왼쪽 링크(llink)에 저장
⑥ 오른쪽 노드의 왼쪽 링크(llink)에 새 노드의 주소를 저장
삽입 전
1 ● |
→ | null | data1 | 2 ● |
→ ← |
1 ● |
data2 | null |
5 ● |
→ |
null | data5 | null |
삽입 후
1 ● |
→ | null | data1 | 5 ● |
5 ● |
data2 | null | |
↑↓ | ↑↓ | |||||||
5 ● |
→ |
1 ● |
data5 | 2 ● |
- 이중 연결 리스트에서의 삭제 연산 과정
① 삭제할 노드의 오른쪽 노드의 주소(old.rlink)를 삭제할 노드의 왼쪽 노드(old.llink)의 오른쪽 링크(rlink)에 저장
② 삭제할 노드의 왼쪽 노드의 주소(old.llink)를 삭제할 노드의 오른쪽 노드(old.rlink)의 왼쪽 링크(llink)에 저장
③ 삭제한 노드를 자유 공간 리스트에 반환
삭제 전
1 ● |
→ | null | data1 | 2 ● |
→ ← |
1 ● |
data2 | 3 ● |
→ ← |
2 ● |
data3 | null |
삭제 후
1 ● |
→ | null | data1 | 3 ● |
→ ← |
1 ● |
data3 | null |
728x90
반응형
'자료구조' 카테고리의 다른 글
[자료구조] 큐(Queue) (0) | 2022.01.09 |
---|---|
[자료구조] 스택 (Stack) (0) | 2022.01.08 |
[자료구조] 순차 자료구조 (0) | 2022.01.01 |
[자료구조] 다항식 (0) | 2022.01.01 |
[JAVA / 자바] 객체지향 프로그래밍 (0) | 2021.12.26 |