[프로그래머스 강의] 10강 연결리스트(Linked List) (4)

---

'어서와! 자료구조와 알고리즘은 처음이지?'

---

 

양방향 연결리스트(이중 연결리스트)

양 쪽으로 링크를 연결하여 앞으로도 (다음 Node) 뒤로도 (이전 Node) 로도 진행이 가능한 연결리스트이다. 리스트의 처음과 끝에 Dummy Node를 두어 데이터를 담고 있는 Node들이 모두 같은 모양이 되도록 한다.

 

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

 

class DoubleLinkedList:
	def __init__(self, item):
    	self.node_count = 0
        self.head = Node(None)
        self.tail = Node(None)
        self.head.prev = None
        self.tail.prev = self.head
        self.tail.next = None

 

리스트 순회

# head와 tail 이 모두 dummy 노드인 경우에도 위의  traverse() 코드가 성립한다. 

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

head와 tail이 모두 dummy 노드인 경우

 

 

리스트 역 순회

# head 와 tail 이 모두 dummy 노드인 경우에도 성립한다.

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

 

원소의 삽입

def insert_after(self, prev, new_node):
    next = prev.next
    new_node.prev = prev
    new_node.next = next
    prev.next = new_node
    next.prev = new_node
    
    self.node_count += 1
    
    return True

 

특정 원소 얻어내기

# 단일 연결리스트 get_at() 메서드와 완전히 동일 

def get_at(self,pos):
   if pos < 0 or pos > self.node_count:
       return None
    
    i = 0
    curr = self.head
    while i < pos:
    	curr = curr.next
        i += 1
    
    return curr

 

원소의 삽입( insert_after( ) )

def insert_at(self, pos, new_node):
    if pos < 1 or pos > self.node_count + 1:
    	return False
    
    prev = self.get_at(pos-1)
    
    return self.insert_after(prev, new_node)

 

리스트 마지막에 원소를 삽입하려면 단일 연결리스트에서는 prev를 구하기 위해 get_at() 로 전체를 순회 했어야 했다. 하지만 양방향 연결리스트를 사용하면 get_at()을 다음과 같이 수정하여 prev 탐색 효율을 높일 수 있다. 

 

def get_at(self, pos):
    if pos < 0 or pos > self.node_count:
    	return None
    
    if pos > self.node_count // 2:
    	i = 0
        curr = self.tail 
        
        while i < self.node_count - pos + 1:
        	curr = curr.prev
            i + =1
            
    else:
    	i = 0
        curr = self.head
        
        while i < pos :
        	curr = curr.next
            i += 1
        
    return curr

 

[ 문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):
        result = []

        # 끝에서 부터 순회 tail --> dummy node
        curr = self.tail

        # dummy node가 존재하므로 curr.prev.prev != None 인 경우까지 while문으로 순회한다. 
        while curr.prev.prev:
            curr = curr.prev
            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 solution(x):
    return 0

 

[ 문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

   # next 노드가 주어졌을 때 before 에 newNode 삽입
    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


def solution(x):
    return 0

 

[ 문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 = prev.next.next
        prev.next = next
        next.prev = prev
        self.nodeCount -= 1
        return curr.data


    def popBefore(self, next):
        curr = next.prev
        prev = next.prev.prev
        prev.next = next
        next.prev = prev
        self.nodeCount -= 1
        return curr.data

    def popAt(self, pos):
        # pos == 0: head, pos == self.nodeCount + 1 : tail 
        if pos < 1 or pos > self.nodeCount:
            raise IndexError
        else:
            prev = self.getAt(pos-1)
            return self.popAfter(prev)





def solution(x):
    return 0

[ 문4. 양방향 연결리스트의 병합 ]

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 concat(self, L):

        # l1, l2 가 각각 비어도 비어있지 않아도 head, tail 이 dummy 노드로 항상 존재하기 때문에
        # L1, l2 가 None인 예외 상황을 고려하지 않아도 된다. 원소가 존재하는 것과 똑같이 처리가 가능하다. 
        l1_last_node = self.tail.prev
        l2_first_node = L.head.next
        l1_last_node.next = l2_first_node
        l2_first_node.prev = l1_last_node

        # 기존 tail 위치 변경 
        self.tail = L.tail

        self.nodeCount += L.nodeCount


    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 solution(x):
    return 0