이중 연결리스트 - Doubly Linked List

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 사용해보면서 배운 점을 정리한 글입니다.

정의

단일 연결리스트 노드에서 이전 노드 참조값이 추가되었고 구조적 차이점으로 head 외에 tail도 있어 역방향 탐색이 절반만큼 유리해졌다고 보면 된다. 단일 연결리스트의 내용은 단일 연결리스트 - Singly Linked List를 참고하자.

시간복잡도

이중 연결리스트(Doubly Linked List) 구현

Node 정의

class ListNode(object):
    def __init__(self, val, prev=None, next=None):
        self.val = val
        self.prev = prev
        self.next = next

Doubly Linked List 정의

class DoublyLinkedList(object):
    def __init__(self):
        self.head = ListNode(None)
        self.tail = ListNode(None, self.head)
        self.head.next = self.tail
        self.size = 0

Doubly Linked List 사이즈 반환

    def size(self):
        return self.size

Doubly Linked List 원소 조회

    def get_node(self, idx):
        if self.size == 0: # 비어있으면 None
            return
        elif idx > self.size:
            print("ERROR: Out of Range") # 범위 초과 시 에러출력
            return
        else:
            if idx <= self.size // 2: # 절반보다 앞이면
                target = self.head # 앞에서부터 탐색
                for _ in range(idx):
                    target = target.next
                return target
            else: # 절반보다 뒤쪽이면
                target = self.tail # 뒤에서부터 탐색
                for _ in range(self.size - idx):
                    target = target.prev
                return target

Doubly Linked List 원소 우측 삽입

    def append(self, val):
        if self.size == 0: # 비어있으면 head 채움
            self.head = ListNode(val, None, self.tail)
            self.tail.prev = self.head
        else: # head가 존재하면 뒤쪽 삽입
            tmp = self.tail.prev
            tmp.next = ListNode(val, tmp, self.tail)
            self.tail.prev = tmp.next
        self.size += 1

Doubly Linked List 원소 좌측 삽입

    def appendleft(self, val):
        if self.size == 0:
            self.head = ListNode(val, None, self.tail)
            self.tail.prev = self.head
        else:
            tmp = self.head
            self.head = ListNode(val, None, tmp)
            tmp.prev = self.head
        self.size += 1

Doubly Linked List 좌표 기반 원소 삽입

    def insert(self, val, idx):
        if self.size == 0: # 비어있으면 좌측 삽입
            self.appendleft(val)
        else: # 원소가 존재 시
            target = self.get_node(idx) # idx 좌표 노드 조회
            if target == None: # None이면 - 범위초과
                target.append(val) # 우측 삽입
            elif target == self.head: # 0으로 head라면
                target.appendleft(val) # 좌측 삽입
            else: # 그 외
                target_prev = target.prev # idx-1좌표 노드 조회
                # 새로운 노드는 기존 i-1, i번 좌표 사이에 위치함
                new_node = ListNode(val, target_prev, target)
                # 이후 기존 노드 참조값 수정
                target_prev.next, target.prev = new_node, new_node
        self.size += 1

Doubly Linked List 원소 우측 삭제

    def pop(self):
        if self.size == 0:
            print("ERROR: Already Empty Linked List")
            return
        else:
            target = self.tail.prev
            if target == self.head: # 만약 head만 있으면 초기화
                self.head = ListNode(None, None, self,tail)
                self.tail.prev = self.head
            else: # 그 외에
                # 마지막 노드 양 옆의 참조 값 수정
                target.prev.next, self.tail.prev = self.tail, target.prev
            self.size -= 1
            return target

Doubly Linked List 좌표 기반 원소 삭제

    def delete(self, idx):
        if self.size == 0:
            print("ERROR: Already Empty Linked List")
        elif idx >= self.size:
            print("ERROR: Out of Range")
        else:
            target = self.get_node(idx) # 제거할 노드 조회
            if target == self.head: # 만약 head면 head 처리
                self.head = self.head.next
                self.head.prev = None
            else: # 그외엔 참조값 수정
                target.prev.next, target.next.prev = target.next, target.prev
            self.size -= 1
            del(target) # 메모리에서 제거

Doubly Linked List 원소 출력

    def print(self):
        target = self.head # 0번 노드부터 시작
        while target != self.tail: # 현재 노드가 tail이 아닐 때까지 반복
            if target.next != self.tail: # 다음 노드가 tail이 아니면
                print(f'{target.val} <=> ', end='') # 값, 화살표 출력
            else: # 다음 노드가 tail이면 이후 값 없으므로 값만 출력
                print(target.val)
            target = target.next # 다음 노드 탐색

실습 결과

foo = DoublyLinkedList()
foo.append(1)
print(foo.get_node(0).val)
foo.append(3)
foo.print()
foo.appendleft(0)
foo.print()
foo.insert(2, 2)
foo.print()
foo.append(4)
print(foo.pop().val)
foo.print()
foo.delete(1)
foo.print()