양방향 연결리스트(Double LinkedList)

Double LinkedList

reference

어서와! 자료구조와 알고리즘은 처음이지? | 프로그래머스

앞서 살펴본 단뱡향 연결리스트와 달리 이번에는 양방향 연결리스트로 링크가 한쪽방향이 아닌 양방형으로 연결된 Double LinkedList에 대해서 살펴볼려고 한다.

 

말 그대로, 양방향 연결 리스트에서는 노드들이 앞/뒤로 연결되어 있습니다. 즉, 인접한 두 개의 노드들은 앞의 노드로부터 뒤의 노드가 연결되어 있을뿐만 아니라, 뒤의 노드로부터 앞의 노드도 연결되어 있습니다. 한 노드의 입장에서 보자면, 자신보다 앞에 오는 노드를 연결하는 링크와 자신보다 뒤에 오는 노드를 연결하는 링크를 둘 다 가진다.

또한 양방향 연결리스트는 기존 단방향 연결리스트와 달리 HEAD, TAIL노드에 Dummy인 빈 노드가 초기화 되어 있는 연결리스트이다.

장단점

 

단점

1. 메모리 사용량 증가.
2. 원소 삽입 / 삭제하는 연산 코드량 증가.(앞 / 뒤 링크 조절 필요)

장점

1. 원소 방문 용이(앞/뒤로 접근 가능)

   → 실제로 (제 7 강에서 언급한 바와 같이) 컴퓨터 시스템의 주요 구성 요소의 하나인 운영체제 (operating system) 등에서는 리스트를 대상으로 앞/뒤로 왔다 갔다 하면서 작업을 행하는 일들이 빈번히 요구되고, 따라서 양방향 연결 리스트가 많이 이용도고 있다.

Methods

1. getLength() 2. traversal()
3. getAt() 4. insertAfter(prev)
5. insertAt(pos, newNode) 6. insertBefore(next, newNode)
7. popAfter(prev) 8. popAt(pos)
9. popBefore(next) 10. cancat(L) 11. reverse()

코드 구현

https://github.com/NDjust/python_data_structure/blob/master/DoublyLinkedList/DoublyLinkedList.py

class Node:
    '''
    extends self.prev variable at LinkedList
    '''

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


class DoublyLinkedList:
    '''
    extends reverse, before methods at LinkedList
    extends member variable at LinkedList
    '''

    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 __repr__(self):
        if self.nodeCount == 0:
            return 'LinkedList: empty'

        s = ''
        curr = self.head
        while curr.next.next:
            curr = curr.next
            s += repr(curr.data)
            if curr.next.next is not None:
                s += ' -> '
        return s

    def getLength(self):
        return self.nodeCount

    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 += [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 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

    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