자료구조

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

Seunghyun_KO 2022. 1. 2. 09:00
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