양방향 연결 리스트(Doubly Linked Lists)
-
한 쪽으로만 링크를 연결하지 말고, 양쪽으로!
→ 앞으로도(다음 node), 뒤로도(이전 node) 진행 가능
노드의 확장
class Node:
def __init__(self, item):
self.data = item
self.prev = None
self.next = None-
리스트 처음과 끝에 dummy node를 두자
→ 데이터를 담고 잇는 node들은 모두 같은 모양
양방향 연결 리스트의 구조
-
리스트의 처음과 끝에 dummy node를 둔다.
-
데이터를 담고있는 node들이 모두 같은 모양이 된다.
-
코드를 작성하는데 있어 상당히 편안해지게 된다.
class DoublyLinkedList:
def __init__(self, item):
self.nodeCount = 0
self.head = Node(None)
self.tail = Node(None)
self.head.prev = None
self.head.next = self.tail
self.tail.prev = self.head
self.tail.next = None리스트 순회
- while문 안에서 현재 노드의 다음.다음이 유효할 때까지 반복한다.
- 리스트가 비어있는 경우에서도 유효한 코드가 된다.
def traverse(self):
result = []
curr = self.head
while curr.next.next:
curr = curr.next
result.append(curr.data)
return result리스트 역순회
def reverse(self):
result = []
curr = self.tail
while curr.prev.prev:
curr = curr.prev
result.append(curr.data)
return result원소의 삽입
def insertAfter(self, prev, newNode):
next = prev.next
newNode.prev = prev
newNode.next = next
prev.next = newNode
next.prev = newNode
self.nodeCount += 1
return True특정 원소 얻어내기
- 지난 연결 리스트(Linked List)와 동일
def getAt(self, pos):
if pos < 0 or pos > self.nodeCount:
return None
i = 0
curr = self.head
while i < pos:
curr = curr.next
i += 1
return curr원소의 삽입
def insertAt(self, pos, newNode):
if pos < 1 or pos > self.nodeCount + 1:
return False
prev = self.getAt(pos - 1)
return self.insertAfter(prev, newNode)
def insertBefore(self, next, newnode):
prev = next.prev
newNode.next = prev.next
newNode.prev = prev
prev.next = newNode
next.prev = newNode
self.nodeCount += 1
return True
- 리스트 마지막에 원소를 삽입하려면
# 마지막 원소 삽입 수정 본 getAt()을 수정
# 특정 원소 얻어내기
def getAt(self, pos):
if pos < 0 or pos > self.nodeCount:
return None
# pos가 오른쪽으로 치우쳐있는 경우 tail쪽에서 계산
if pos > self.nodeCount // 2:
i = 0
curr = self.tail
while i < self.nodeCount - pos + 1:
curr = curr.prev
i += 1
# pos가 왼쪽으로 치우쳐 있는 경우 head에서 계산
else:
i = 0
curr = self.head
while i < pos:
curr = curr.next
i += 1
return curr원소의 삭제
def popAfter(self, prev):
curr = prev.next
prev.next = curr.next
curr.next.prev = prev
self.nodeCount -= 1
return curr.data
def popBefore(self, next):
curr = next.prev
prev = curr.prev
prev.next = next
next.prev = prev
self.nodeCount -= 1
return curr.data
def popAt(self, pos):
if pos < 1 or pos > self.nodeCount:
raise IndexError
prev = self.getAt(pos - 1)
return self.popAfter(prev)두 리스트의 병합
# 두 리스트의 병합
def concat(self, L):
self.tail.prev.next = L.head.next
L.head.next.prev = self.tail.prev
self.tail = L.tail
self.nodeCount += L.nodeCount[실습_1] 양방향 리스트 역방향 순회
문제
어서와! 자료구조와 알고리즘은 처음이지? 10강 실습: (1)양방향 연결 리스트 역방향 순회
문제 설명
제 10 강에서 소개된 추상적 자료구조 DoublyLinkedList 에 대하여, 또한 강의 내용에서 언급한 reverse() 메서드를 구현하세요.
이 reverse() 메서드는 양방향 연결 리스트를 끝에서부터 시작해서 맨 앞에 도달할 때까지 (tail 방향에서 head 방향으로) 순회하면서, 방문하게 되는 node 에 들어 있는 data item 을 순회 순서에 따라 리스트에 담아 리턴합니다.
예를 들어, DoublyLinkedList L 에 들어 있는 노드들이 43 -> 85 -> 62 라면, 올바른 리턴 값은 [62, 85, 43] 입니다.
이 규칙을 적용하면, 빈 연결 리스트에 대한 역방향 순회 결과로 reverse() 메서드라 리턴해야 할 올바른 결과는 [] 입니다.
나의 풀이
- 최종 리턴 데이터 초기값 선언
- result = []
- 현재 노드는 tail로 지정
- tail부터 거꾸로 차례대로 result에 append함
solution.py
def reverse(self):
result = []
curr = self.tail
while curr.prev.prev:
curr = curr.prev
result.append(curr.data)
return result실행 결과
정확성 테스트
테스트 1 〉 통과 (0.05ms, 10.7MB)
테스트 2 〉 통과 (0.04ms, 10.8MB)
채점 결과
정확성: 100.0
합계: 100.0 / 100.0[실습_2] 양방향 연결 리스트 노드 삽입
문제
어서와! 자료구조와 알고리즘은 처음이지? 10강 실습: (2)양방향 연결 리스트 노드 삽입
문제 설명
제 10 강에서 소개된 추상적 자료구조 DoublyLinkedList 의 메서드로 insertBefore() 를 구현하세요.
이 insertBefore() 메서드에는 두 개의 인자가 주어지는데, next 는 어느 node 의 앞에 새로운 node 를 삽입할지를 지정하고, newNode 는 삽입할 새로운 node 입니다.
강의 내용에서 소개된 insertAfter() 메서드의 구현과 매우 유사하게 할 수 있습니다.
나의 풀이
solution.py
def insertBefore(self, next, newNode):
prev = next.prev
newNode.next = prev.next
newNode.prev = prev
prev.next = newNode
next.prev = newNode
self.nodeCount += 1
return True실행 결과
정확성 테스트
테스트 1 〉 통과 (0.06ms, 10.9MB)
채점 결과
정확성: 100.0
합계: 100.0 / 100.0[실습_3] 양방향 연결 리스트 노드 삭제
문제
어서와! 자료구조와 알고리즘은 처음이지? 10강 실습: (3)양방향 연결 리스트 노드 삭제
문제 설명
제 10 강에서 소개된 추상적 자료구조 DoublyLinkedList 에 대하여 node 의 삭제 연산에 관련한 아래와 같은 메서드들을 구현하세요.
popAfter() popBefore() popAt()
popAfter(prev) 는 인자 prev 에 의하여 주어진 node 의 다음에 있던 node 를 삭제하고, popBefore(next) 는 인자 next 에 의하여 주어진 node 의 이전에 있던 node 를 삭제합니다. 그리고 삭제되는 node 에 담겨 있던 data item 을 리턴합니다.
popAt(pos) 는 인자 pos 에 의하여 지정되는 node 를 삭제하고 그 node 에 담겨 있던 data item 을 리턴하는데, 위 popAfter() 또는 popBefore() 를 호출하여 이용하는 방식으로 구현하세요. 또한, 만약 인자 pos 가 올바른 범위 내에 있지 않은 경우에는 raise IndexError 를 이용하여 IndexError exception 을 일으키도록 구현하세요.
테스트 케이스 1-3 은 각각 (1) popAfter(), (2) popBefore(), (3) popAt() 메서드의 올바른 동작을 검증하는 케이스입니다.
나의 풀이
solution.py
def popAfter(self, prev):
curr = prev.next
prev.next = curr.next
curr.next.prev = prev
self.nodeCount -= 1
return curr.data
def popBefore(self, next):
curr = next.prev
prev = curr.prev
prev.next = next
next.prev = prev
self.nodeCount -= 1
return curr.data
def popAt(self, pos):
if pos < 1 or pos > self.nodeCount:
raise IndexError
prev = self.getAt(pos - 1)
return self.popAfter(prev)실행 결과
정확성 테스트
테스트 1 〉 통과 (0.08ms, 10.7MB)
테스트 2 〉 통과 (0.07ms, 10.8MB)
테스트 3 〉 통과 (0.07ms, 10.9MB)
채점 결과
정확성: 100.0
합계: 100.0 / 100.0[실습_4] 양방향 연결 리스트의 결합
문제
어서와! 자료구조와 알고리즘은 처음이지? 10강 실습: (4)양방향 연결 리스트의 병합
문제 설명
제 10 강에서 소개된 추상적 자료구조 DoublyLinkedList 에 대하여 두 개의 양방향 연결 리스트를 앞뒤로 이어 붙이는 메서드 concat() 을 구현하세요.
예를 들어, 양방향 연결 리스트 L1 에는 1 -> 2 -> 3 의 원소가 순서대로 들어 있고, 또다른 양방향 연결 리스트 L2 에는 4 -> 5 의 순서로 원소가 들어 있을 때, 메서드 호출 L1.concat(L2) 의 결과로 L1 은 1 -> 2 -> 3 -> 4 -> 5 의 양방향 연결 리스트가 됩니다. 물론, L1 또는 L2 또는 둘 다가 비어 있는 양방향 연결 리스트인 경우도 고려되도록 코드를 작성해야 합니다.
나의 풀이
solution.py
def concat(self, L):
self.tail.prev.next = L.head.next
L.head.next.prev = self.tail.prev
self.tail = L.tail
self.nodeCount += L.nodeCount실행 결과
정확성 테스트
테스트 1 〉 통과 (0.05ms, 10.8MB)
테스트 2 〉 통과 (0.05ms, 10.7MB)
테스트 3 〉 통과 (0.05ms, 10.8MB)
채점 결과
정확성: 100.0
합계: 100.0 / 100.0