DLL이란?

• Singly linked list의 단점인 앞쪽 노드를 찾기 어려운것을 개선한 리스트 구조이다. 각 노드에는 뒤쪽 노드에 대한 포인터뿐만 아니라 앞쪽 노드에 대한 포인터가 주어진다.

특징

• 저장공간이 낭비되지만, 양방향 탐색으로 탐색 시간을 SLL에 비해 반으로 줄일 수 있다.
• SLL보다 포인터를 2배 더 많이 사용하고 구현이 복잡하다.

구현방법

코드 설계

• class Node
  • Node를 DLL에서 사용 할 수 있게 class를 생성해준다.
  • init함수로 생성자를 구현하여 노드를 초기화 해준다.
  • input 값으로 key속성값, prev포인터, next포인터가 입력된다.
    • key속성값에는 노드의 data가 입력된다.
    • prev포인터에 노드에서 이전 data로 가는 주소가 입력된다.
    • next포인터에 노드에서 다음 data로 가는 주소가 입력된다.
• class DLL

  • init()

    • init함수로 DLL을 생성하는 준비 작업을 수행함으로, 노드가 하나도 없는 빈 리스트를 생성한다.
    • Head - head node를 참조하기 위한 node에 None으로 초기화 한다. self.head = Node(None, None, self.tail)
    • Tail - self.tail = Node(None, self.head, None)
    • no - DLL 노드의 개수를 나타내기 위해서 사용된다.
      • insert 시에 no는 +1 이 되어, 노드의 개수가 증가함을 나타낸다.
      • delete 시에 no는 -1 이 되어, 노드의 개수가 감소함을 나타낸다.

  • len()

    • DLL의 노드 개수를 알려주는 함수이다.
      • no의 값을 return함으로써 DLL 노드의 개수를 알려준다.

  • search_Head(data)

    • Head에서 부터 Tail로 검색을 하는 함수이다.
    • idx = 0, idx 변수를 두어 data를 비교하여 실패할 때 마다 idx는 증가한다.
    • DLL에 데이터가 존재하지 않을 때,
      • "underflow"가 출력된다.(혹은 -1을 리턴한다.)
    • DLL에 데이터가 존재하여 검색에 성공하는 경우,
      • head에서부터의 data와 입력된 data를 비교한다.
      • data가 같지 않다면 차례대로 nextNode를 입력된 data와 비교한다.
      • 이때, idx가 +1 씩 추가되어 몇 번째 node가 입력된 data와 같은지 알 수 있게 한다.
      • idx를 return하여 몇 번째 node가 입력된 data와 같은지 알 수 있다.
    • DLL에 데이터가 존재하지 않아 검색에 실패한 경우,
      • -1을 return한다.

  • search_Tail(data)

    • Tail에서 부터 Head로 검색을 하는 함수이다.
    • idx = -1, idx 변수를 두어 data를 비교하여 실패할 때 마다 idx는 감소한다.
    • DLL에 데이터가 존재하지 않을 때,
      • "underflow"가 출력된다.(혹은 -1을 리턴한다.)
    • DLL에 데이터가 존재하여 검색에 성공하는 경우,
      • Tail에서부터의 data와 입력된 data를 비교한다.
      • data가 같지 않다면 차례대로 prevNode를 입력된 data와 비교한다.
      • 이때, idx가 -1씩 감소되어 뒤에서부터 몇 번째 node가 입력된 data와 같은지 알 수 있게 한다.
      • idx를 return하여 몇 번째 node가 입력된 data와 같은지 알 수 있다.
    • DLL에 데이터가 존재하지 않아 검색에 실패한 경우,
      • -1을 return한다.

  • select_Node(idx)

    • idx가 no보다 크면,
      • "index error"가 print된다.
    • idx가 0이면,
      • 선택된 노드는 head node이다. head node를 return한다.
    • idx가 no와 같다면,
      • 선택된 노드는 tail node이다. tail node를 return한다.
    • idx가 no/2의 이하 숫자라면,
      • tmp변수에 head node를 insert 한다.
      • idx의 범위만큼 for반복문을 실행한다.
        • tmp(head node) 부터 idx의 번호만큼 다음 노드를 tmp에 삽입한다. (tmp = tmp.next)
        • 마지막 tmp를 return하면, 선택하고자 하는 idx의 데이터가 return된다.
    • idx가 no/2의 초과 숫자라면,
      • tmp변수에 tail node를 insert한다.
      • 전체 no에서 idx를 뺀 수 만큼 for반복문을 실행한다.
        • tmp(tail node) 부터 idx의 번호만큼 tmp = tmp.prev를 실행한다.
        • 마지막 tmp를 return하면, 선택하고자 하는 idx의 데이터가 return 된다.

  • insert_head(data)

    • DLL의 head에 data를 추가하는 함수이다.
    • DLL에 데이터가 존재하지 않을 경우(no가 0일 경우),
      • 삽입한 데이터는 그 자체로 Head node와 Tail Node가 되며, prev값과 next값은 None을 가진다.
    • DLL에 데이터가 존재하는 경우,
      • ex, "B"라는 Head node가 존재하고, 새로운 head data "A"를 삽입하는 경우
      • Head node에 A를 삽입하기위해,
        • 존재하고 있는 Head node인 B를 tmp변수에 임시로 저장한다.
        • A의 next포인터가 tmp변수에 저장된 B를 향하게 한다.
        • B의 prev포인터는 None에서 A를 향하도록 저장된다.
        • A의 prev포인터는 Head node임으로 None으로 저장한다.
    • no가 +1 되어, DLL의 노드 갯수가 늘어남을 알 수 있다.

  • insert_tail(data)

  • insert_at(data, idx)

  • delete_head()

  • delete_tail()

  • delete_at(idx)

  • print_all()

  • is_Empty()

코드 구현

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

class DLL(object):
    def __init__(self):
        self.head = Node(None)
        self.tail = Node(None, self.head, None)
        self.no = 0

    def len(self):
        return self.no

    def is_Empty(self):
        if self.no == 0:
            return True
        else:
            return False

    def search_Head(self, data):
        idx = 0
        tmp = self.head
        if tmp is None:
            print("underflow")
        else:
            while tmp.data is not data:
                tmp = tmp.next
                idx += 1
            return idx
        return " "

    def search_Tail(self, data):
        idx = 0
        tmp = self.tail
        if tmp is None:
            print("underflow")
        else:
            while tmp.data is not data:
                tmp = tmp.prev
                idx -= 1
            return idx
        return " "

    def print_all(self):
        ptr = self.head
        while ptr is not None:
            print(ptr.data, end="  ")
            ptr = ptr.next
        print()

    def select_Node(self, idx):
        if idx > self.no:
            print("overflow")
        elif idx == 0:
            return self.head
        elif idx == self.no:
            return self.tail
        elif idx <= (self.no // 2):
            tmp = self.head
            for _ in range(idx):
                tmp = tmp.next
            return tmp
        else:
            tmp = self.tail
            for _ in range(self.no - idx):
                tmp = tmp.prev
            return tmp

    def insert_head(self, data):
        if self.is_Empty():
            self.head = Node(data)
            self.tail = Node(None, self.head)
            self.head.next = self.tail
        else:
            tmp = self.head
            self.head = Node(data, None, tmp)
            tmp.prev = self.head
        self.no += 1

    def insert_tail(self, data):
        if self.is_Empty():
            self.insert_head(data)
        else:
            tmp = self.tail
            self.tail = Node(data, tmp, None)
            tmp.next = self.tail
            self.tail.prev = tmp
        self.no += 1

    def insert_at(self, data:int, idx:int):
        if self.is_Empty():
            self.insert_head(data)
        else:
            if idx == 0:
                self.insert_head(data)
            elif idx == self.no:
                self.insert_tail(data)
            else:
                tmp = self.select_Node(idx)
                tmp_prev = tmp.prev
                newNode = Node(data, tmp_prev, tmp)
                tmp_prev.next = newNode
                tmp.prev = newNode
        self.no += 1

    def delete_head(self):
        if self.is_Empty():
            print("underflow")
        else:
            self.head = self.head.next
            self.head.prev = None
        self.no -= 1

    def delete_tail(self):
        if self.is_Empty():
            print("underflow")
        else:
            self.tail = self.tail.prev
            self.tail.next = None
        self.no -= 1

    def delete_at(self, idx):
        if self.is_Empty():
            print("underflow")
        else:
            if self.no == 1:
                self.delete_head()
            elif self.no >= 2:
                tmp = self.select_Node(idx)
                if tmp is self.head:
                    self.delete_head()
                elif tmp is self.tail:
                    self.delete_tail()
                else:
                    tmp.prev.next = tmp.next
                    tmp.next.prev = tmp.prev
        self.no -= 1

dll = DLL()
# dll.insert_head(1)
# dll.insert_head(2)
# dll.insert_head(3)
# dll.insert_tail(4)
# dll.insert_tail(5)
# dll.print_all()
# print()
# print(dll.search_Head(3))
# print(dll.search_Tail(1))
# dll.insert_at(6, 2)
# dll.insert_at(7, 0)
# dll.insert_at(8, 8)
# dll.print_all()
# print()
# dll.delete_head()
# dll.print_all()
# print()
# dll.delete_tail()
# dll.delete_tail()
# dll.print_all()
# print()
# print("*****")
# dll.delete_at(1)
# dll.print_all()
# print()
# print(dll.len())
# print()
# print("******************")
dll.insert_head(1)
dll.insert_head(2)
dll.insert_head(3)
dll.insert_head(4)
dll.insert_head(5)
dll.insert_head(6)
dll.delete_tail()
dll.print_all()
dll.insert_tail(7)
dll.print_all()
dll.delete_at(6)
dll.print_all()

시간복잡도

O(n)의 시간 복잡도를 가진다.

insert_at(self, data, int)에서 tmp = serach_Head(data)부분 오류발생. 이유는 search_Head(data)에서 data가 존재하지 않는 값이 새로운 data이기 때문에 search가 불가능해서 error가 발생한다.

idx로 검색하면 data를 부를 수 없는 줄 착각 하고 있었다. 그러나 data, idx, next, prev 넷 다 하나의 node로써 불러올 수 있어 상관이 없었다.

delete_at(self, idx)에서 head와 tail 삭제는 잘 되지만 중간값 삭제가 제대로 되지 않음.