[프로그래머스 알고리즘] 10강: 양방향 연결 리스트 (Doubly Linked Lists)

양방향 연결 리스트 (Doubly Linked Lists)

한 방향으로만 연결하는 것이 아닌 양쪽으로 연결하는 리스트.

• 이전 노드, 다음 노드 방향으로 진행이 가능하다.
• Node 클래스의 생성자에 self.prev를 추가 설정해줌.
• 리스트 처음과 끝에 dummy node를 둔다 --> 데이터를 담고 있는 노드들은 모두 같은 모양을 가진다.

 

---

과제 1: 양방향 연결리스트 역방향 순회

class Node:

    def __init__(self, item):
        self.data = item
        self.prev = None
        self.next = None


class DoublyLinkedList:

    def __init__(self):
        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


    def reverse(self):
        list = []
        curr = self.tail
        while curr.prev != self.head:
            curr = curr.prev
            list.append(curr.data)
        return list


    def getAt(self, pos):
        if pos < 0 or pos > self.nodeCount:
            return None

        if pos > self.nodeCount // 2:
            i = 0
            curr = self.tail
            while i < self.nodeCount - pos + 1:
                curr = curr.prev
                i += 1
        else:
            i = 0
            curr = self.head
            while i < pos:
                curr = curr.next
                i += 1

        return curr


    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


    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)

 

과제2: 양방향 연결 리스트 노드 삽입

class Node:

    def __init__(self, item):
        self.data = item
        self.prev = None
        self.next = None


class DoublyLinkedList:

    def __init__(self):
        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


    def traverse(self):
        result = []
        curr = self.head
        while curr.next.next:
            curr = curr.next
            result.append(curr.data)
        return result


    def insertBefore(self, next, newNode):
        prev = next.prev 
        newNode.prev = prev
        newNode.next = next
        prev.next = newNode
        next.prev = newNode
        
        self.nodeCount += 1
        return True

과제3: 양방향 연결 리스트 노드 삭제

class Node:

    def __init__(self, item):
        self.data = item
        self.prev = None
        self.next = None


class DoublyLinkedList:

    def __init__(self):
        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


    def traverse(self):
        result = []
        curr = self.head
        while curr.next.next:
            curr = curr.next
            result.append(curr.data)
        return result


    def getAt(self, pos):
        if pos < 0 or pos > self.nodeCount:
            return None

        if pos > self.nodeCount // 2:
            i = 0
            curr = self.tail
            while i < self.nodeCount - pos + 1:
                curr = curr.prev
                i += 1
        else:
            i = 0
            curr = self.head
            while i < pos:
                curr = curr.next
                i += 1

        return curr


    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


    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 popAfter(self, prev):
        curr = prev.next
        next = curr.next
        prev.next = curr.next
        next.prev = prev
        self.nodeCount -= 1
        return curr.data


    def popBefore(self, next):
        curr = next.prev
        prev = curr.prev
        prev.next = curr.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)

과제4: 양방향 연결 리스트의 병합

def concat_v1(self, L):
    l1_tail = self.tail.prev
    l2_head = L.head.next
        
    if self.nodeCount == 0:
        self.head.next = l2_head
        l2_head.prev = self.head

    elif L.nodeCount == 0:
     	l1_tail.next = L.tail
        L.tail.prev = l1_tail
            
    else:
        l1_tail.next = l2_head
        l2_head.prev = l1_tail
            
    self.tail = L.tail
    self.nodeCount += L.nodeCount
    return self
    
def concat_v2(self, L):
        l1_tail = self.tail.prev
        l2_head = L.head.next
        l1_tail.next = l2_head
        l2_head.prev = l1_tail
        self.tail = L.tail
        self.nodeCount += L.nodeCount
        return self