[자료구조] 이중 연결 리스트

이중 연결 리스트(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