[10강] 양방향 연결 리스트(Doubly Linked Lists)

황인용·2020년 7월 10일
0
post-thumbnail

양방향 연결 리스트(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
profile
dev_pang의 pang.log

0개의 댓글