Doubly Linked List

Node 구현

class Node:

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

DoublyLinkedList 구현

1. __init__ 생성자

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

2. __len__

• len() 구현

def __len__(self):
    return self.nodeCount

3. traverse

• head부터 순회하면서 리스트에 값을 저장
• print를 하면 이 결과 값을 반환

def traverse(self):

    l = []
    curr = self.head.next

    while curr.next:
        l.append(curr.data)
        curr = curr.next

    return l

def __repr__(self):
    return self.traverse().__repr__()

4. reverse_traverse

• tail부터 값을 역방향으로 순회하면서 리스트에 값을 저장

def reverse_traverse(self):

    l=[]
    curr = self.tail.prev

    while curr.prev:
        l.append(curr.data)
        curr = curr.prev

    return l

5. __getitem__

• 인덱싱 구현

def __getitem__(self, idx):

    if 0 <= idx < self.nodeCount//2:
        node = self.head.next
        for _ in range(idx):
            node = node.next

    elif self.nodeCount//2 <= idx < self.nodeCount:
        node = self.tail.prev
        for _ in range(~idx + self.nodeCount):
            node = node.prev

    else:
        raise IndexError

    return node

6. insertAfter

• 지정한 노드 앞에 새로운 노드를 추가

def insertAfter(self, prev, newNode):

    prev.next.prev = newNode
    newNode.next = prev.next
    newNode.prev = prev
    prev.next = newNode

    self.nodeCount += 1

7. insertAt

• 지정한 위치에 새로운 노드를 추가

def insertAt(self, idx, newNode):

    if idx == 0:
        prev = self.head
    else:
        prev = self[idx-1]

    return self.insertAfter(prev, newNode)

8. popNode

• 지정한 노드 꺼내기

def popNode(self, node):

    node.prev.next = node.next
    node.next.prev = node.prev

    self.nodeCount -=1

    return node.data

9. popAt

• 지정한 위치에 있는 노드 꺼내기

def popAt(self, idx):
    return self.popNode(self[idx])

10. concat

• 다른 DoublyLinkedList 를 연결

def concat(self, other):

    self.tail.prev.next = other.head.next
    other.head.next.prev = self.tail.prev

    self.tail = other.tail

    self.nodeCount += other.nodeCount

소스코드 : DoublyLinkedList.py