원형 이중 연결 리스트(Circular doubly linked list)_삽입

코드

# 원형 이중 링크드 리스트
class DCLinkedList:
    # D_C_L_List에서 쓸 노드
    class Node:
        def __init__(self, v, n=None, p=None):
            self.value = v  # 저장된 데이터
            self.next = n  # 다음 노드 가리키는 변수
            self.prev = p  # 이전 노드 가리키는 변수

    # D_C_L_List에서 필요한 변수
    def __init__(self):
        self.head = None  # 첫 생성시 내부에는 노드가 없음
        self.tail = None

    # head로 삽입. v : 데이터
    def insertNodeBefore(self, v):
        # 없을 경우
        if self.head is None:
            self.head = self.Node(v)
            self.tail = self.head  # 같은 노드를 가리킴
        else:
            #기존 head.prev를 새 노드로 지정(새 노드의 prev는 tail, next는 head로 지정)
            self.head.prev = self.Node(v, n=self.head, p=self.tail)  
            self.head = self.head.prev  #head를 새 노드로 변경
            self.tail.next = self.head   #tail.next를 새 head로 업데이트

    # tail로 삽입. v : 데이터
    def insertNodeAfter(self, v):
        # 없을 경우
        if self.tail is None:
            self.tail = self.Node(v)
            self.head = self.tail  # 같은 노드를 가리킴
        else:
            #기존 tail.next를 새 노드로 지정(새 노드의 prev는 tail, next는 head로 지정)
            self.tail.next = self.Node(v, p=self.tail, n=self.head)  
            self.tail = self.tail.next  #tail을 새 노드로 변경
            self.head.prev = self.tail #head.prev를 새 tail로 업데이트
            
            
##테스트
if __name__=="__main__":
    dcl = DCLinkedList()
    dcl.insertNodeBefore('1st')  # head삽입 테스트
    dcl.insertNodeBefore('2nd')  # head삽입 테스트
    dcl.insertNodeBefore('3rd')  # head삽입 테스트
    dcl.insertNodeAfter('B1st') # tail삽입 테스트
    dcl.insertNodeAfter('B2nd') # tail삽입 테스트
    dcl.insertNodeAfter('B3rd') # tail삽입 테스트

설명

이중 연결 리스트와 동일함

저장된 노드가 있는 경우 Head 삽입

기존 head의 prev를 새 노드로 지정(새 노드의 prev는 tail, next는 head로 지정)
head를 새 노드로 변경
tail.next를 새 head로 업데이트

저장된 노드가 있는 경우 Tail 삽입

기존 tail의 next를 새 노드로 지정(새 노드의 prev는 tail, next는 head로 지정)
tail을 새 노드로 변경
head.prev를 새 tail로 업데이트