자료구조 연결 리스트(SLL,DLL,CLL) -(2)DLL
이중연결리스트(Doubly Linked List,DLL)
“이중연결리스트(DLL)” 이란,
각 노드가 두 개의 레퍼런스를 가지고 각각 이전 노드와 다음 노드를 가리키는 연결리스트이다.
앞서 다룬 SLL과 비슷하지만,
큰 차이점은 “두 개의 레퍼런스” 이다.
앞 뒤의 레퍼런스가 각 노드마다 존재하기 때문에,
탐색이 양방향으로 다 가능하다(역출력도 마찬가지.)
SLL과 같이 삽입,삭제 연산에 대해 알아보자.
코드는 python으로 작성하였다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class DList:
class Node:
def __init__(self, item, prev, link): # 노드 생성자. value / 이전 노드 위치 / 연결시킬 노드 위치
self.item = item #value
self.prev = prev #이전 노드 레퍼런스
self.next = link #다음 노드 레퍼런스
def __init__(self): #DLL 생성자 head,tail 생성 및 더미노드 2개(아무것도 저장하지 않음)
self.head = self.Node(None, None, None)
self.tail = self.Node(None, self.head, None)
self.head.next = self.tail #이 리스트에는 head , tail 노드 밖에 존재하지 않음!(기본 생성자)
self.size = 0 #DLL 생성 = 요소 0개
def size(self): #리스트의 요소 출력
return self.size
def is_empty(self): #리스트가 비어있는가?
return self.size == 0 #비어 있다면 True
def insert_before(self, p , item): # p 노드 이전에 새 노드 삽입
t = p.prev #p 이전 노드 = t
n = self.Node(item, t, p) # t가 이전노드, p가 다음노드인 노드 n(t => n => p 관계)
p.prev = n #노드 n을 p 이전 노드 레퍼런스 연결
t.next = n #노드 n을 t 다음 노드 레퍼런스 연결
self.size += 1 #요소 추가니까 리스트 요소 개수 증가
def insert_after(self, p , item): # p 노드 다음에 새 노드 삽입
t = p.next #p 다음 노드 = t
n = self.Node(item, p, t) #p가 이전노드,t가 다음노드인 노드 n(p => n = > t 관계)
t.prev = n #노드 n을 t 이전 노드 레퍼런스 연결
p.next = n #노드 n을 p 다음 노드 레퍼런스 연결
self.size += 1 #요소 추가니까 리스트 요소 개수 증가
def delete(self, x): # x 노드 삭제 함수
f = x.prev # x의 이전 노드 = f
r = x.next # x의 다음 노드 = r (f => x => r)
f.next = r # f의 다음 노드 = r
r.prev = f # r의 이전 노드 = f (f => r, x에 대한 레퍼런스 갱신 = x에 대한 레퍼런스 연결 해제 = x 노드 삭제/ x 노드는 가비지 컬렉션에 의해 처리됨.)
self.size -= 1 #요소 삭제니까 리스트 요소 개수 감소
return x.item #삭제 확인, 삭제가 됬다면 None값이 나올것?
def print_list(self): # 리스트 요소 출력
if self.is_empty(): #true 라면, 리스트가 비어있다는 뜻.
print('리스트 비어있음!')
else: #false라면, 비지 않은 리스트 => 출력!
p = self.head.next #head 다음 노드 = p
while p != self.tail: #head 다음 노드가 tail 노드가 아닐 때 ~순차적 탐색
if p.next != self.tail: #p 다음 노드가 tail 노드가 아닐 때 => 출력
print(p.item, ' => ', end ='')
else: #p 다음 노드가 tail 노드 일 때,마지막 노드 => 출력
print(p.item)
p = p.next #p 다음 노드에 대한 순차적 탐색
class EmptyError(Exception): #underflow 에러 처리
pass
우선, 첫 번째로 삽입 연산이다.
insert_before() 와 insert_after() 함수를 사용하여
각 지정한 노드 이전/이후 에 삽입 연산을 실행 할 수 있다.
중요한 것은, 각각 노드 앞 뒤 관계를 선언 후,
새 노드를 삽입 했을 때 그 노드의 앞 뒤 레퍼런스를 연결해줘야 한다.
example) A => B => C 리스트 존재하고,
insert_before(B,D) 실행 시, B 노드 이전에 D value를 가진 노드를 추가하겠다는 의미.
그렇다면, A = B.prev 선언하고,
N = self.Node(D,A,B) 라고 D value를 가진 새 노드를 선언 및 관계를 나타냄.
그 다음, 앞 뒤 레퍼런스를 연결해주기만 하면 됨.
A.next = N
B.prev = N
후 요소 추가
self.size += 1
… 와 같이 가장 중요한것은 DLL은 앞 뒤 레퍼런스 연결이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
def insert_before(self, p , item): # p 노드 이전에 새 노드 삽입
t = p.prev #p 이전 노드 = t
n = self.Node(item, t, p) # t가 이전노드, p가 다음노드인 노드 n(t => n => p 관계)
p.prev = n #노드 n을 p 이전 노드 레퍼런스 연결
t.next = n #노드 n을 t 다음 노드 레퍼런스 연결
self.size += 1 #요소 추가니까 리스트 요소 개수 증가
def insert_after(self, p , item): # p 노드 다음에 새 노드 삽입
t = p.next #p 다음 노드 = t
n = self.Node(item, p, t) #p가 이전노드,t가 다음노드인 노드 n(p => n = > t 관계)
t.prev = n #노드 n을 t 이전 노드 레퍼런스 연결
p.next = n #노드 n을 p 다음 노드 레퍼런스 연결
self.size += 1 #요소 추가니까 리스트 요소 개수 증가
두 번째로, 삭제 연산이다.
삭제연산은 지우고 싶은 노드의 앞 뒤 레퍼런스를
그 이전/이후의 레퍼런스와 연결시키기만 하면 끝이다.
example) A => B => C 라는 리스트가 존재할 때,
delete(B) 를 실행,
A = B.prev
C = B.next
와 같이 A,B,C의 리스트 관계를 삭제할 노드 기준으로 선언,
A.next = C
C.prev = A
삭제할 노드의 레퍼런스를 건너 뛰고 앞 뒤 노드의 레퍼런스를 서로 연결한다.
1
2
3
4
5
6
7
def delete(self, x): # x 노드 삭제 함수
f = x.prev # x의 이전 노드 = f
r = x.next # x의 다음 노드 = r (f => x => r)
f.next = r # f의 다음 노드 = r
r.prev = f # r의 이전 노드 = f (f => r, x에 대한 레퍼런스 갱신 = x에 대한 레퍼런스 연결 해제 = x 노드 삭제/ x 노드는 가비지 컬렉션에 의해 처리됨.)
self.size -= 1 #요소 삭제니까 리스트 요소 개수 감소
return x.item #삭제 확인, 삭제가 됬다면 리턴값 없음.
아래는 실행 파일 및 실행 결과 이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
from Doubly_Linked_List import DList
if __name__ == '__main__':
d = DList()
d.insert_after(d.head, 'apple') # 헤드 뒤 apple 노드 추가
d.insert_before(d.tail, 'orange') # 테일 앞 orange 노드 추가 (apple => orange)
d.insert_before(d.tail, 'cherry') # 테일 앞 cherry 노드 추가 (apple => orange => cherry)
d.insert_after(d.head.next, 'pear') # 헤드 앞 노드 뒤 pear 노드 추가 (apple => pear => orange => cherry)
d.print_list()
print('마지막 노드 삭제 후:\t', end='') # (apple => pear => orange)
d.delete(d.tail.prev)
d.print_list()
print('맨 끝에 grape 노드 삽입 후:\t', end='') #(apple => pear => orange => grape)
d.insert_before(d.tail, 'grape')
d.print_list()
print('첫 노드 삭제 후:\t', end='') #(pear => orange => grape)
#더미노드 2개를 생성했다는 것을 기억하자.
d.delete(d.head.next)
d.print_list()
print('첫 노드 삭제 후:\t', end='') #(orange => grape)
d.delete(d.head.next)
d.print_list()
print('첫 노드 삭제 후:\t', end='') #(grape)
d.delete(d.head.next)
d.print_list()
print('첫 노드 삭제 후:\t', end='') #(리스트가 비었습니다!)
d.delete(d.head.next)
d.print_list()
실행 결과 =
1
2
3
4
5
6
7
apple => pear => orange => cherry
마지막 노드 삭제 후: apple => pear => orange
맨 끝에 grape 노드 삽입 후: apple => pear => orange => grape
첫 노드 삭제 후: pear => orange => grape
첫 노드 삭제 후: orange => grape
첫 노드 삭제 후: grape
첫 노드 삭제 후: 리스트 비어있음!
#plus
1.DLL의 삽입 삭제 연산은 SLL보다 레퍼런스가 하나 더 많고, 복잡하긴 해도
각각 O(1)개의 레퍼런스만을 갱신함으로 O(1)시간에 수행된다.
2.탐색 연산의 시간복잡도는 O(N).
여기서 N은 실제 항목을 저장하고 있는 노드 수이다.
그리고, 순차적탐색이지만 탐색방향은 두 레퍼런스가 있기에 양방향 다 가능하다.
3.이중연결리스트(DLL) 은
Deque 구현,Binominal Heap,Fibonacci Heap과 같은 우선순위 큐을 구현하는데 부분적으로 사용된다.