[Vector/List]19. Double Linked List 구현

목차

1. class Node

2. class D_linked_list

3. insert()

4. erase

5. 테스트

 

1. class Node

class Node:
    def __init__(self, e: object):
        self.element = e # node가 저장하는 element
        self.front = None # 앞에 있는 node의 주소 저장
        self.back = None # 뒤에 있는 node의 주소 저장

 

2. class D_linked_list

class D_linked_list:
    def __init__(self):
        self.head = Node('head') # head역할을 하는 node 지정
        self.tail = Node('tail') # tail역할을 하는 node 지정
    
    def empty(self)-> bool: # list의 비었는지 여부를 반환하는 함수
        if self.head.back==None and self.tail.front==None:
            return 1
        else:
            return 0
    
    def size(self)-> int: # list의 크기를 반환하는 함수
        tmp = 1
        cur_node = self.head.back
        
        if self.empty(): # list가 비어있다면
            return 0
        else:
            while True:
                if cur_node.back.back==None:
                    break
                else:
                    cur_node = cur_node.back
                    tmp += 1
            return tmp
    
    def begin(self)-> object: # list의 앞의 element 반환
        if self.empty():
            return None
        else:
            return self.head.back.element
    
    def end(self)-> object: # list의 뒤의 element 반환
        if self.empty():
            return None
        else:
            return self.tail.front.element

 

3. insert()

    def insert(self, i: int, e: object): # list의 index i에 element e 삽입
        node = Node(e)
        pre_node = self.head
        next_node = self.head.back
        tmp = 0
        
        if i>self.size() or i<0: # 찾고자 하는 index가 size보다 크거나, 0보다 작은 경우
            print('out of index')
        elif self.empty() and i==0: # list가 비어있을 경우
            self.head.back = node
            self.tail.front = node
            node.front = self.head
            node.back = self.tail
        else:
            while True:
                if tmp==i:
                    break
                else:
                    pre_node = pre_node.back
                    next_node = next_node.back
                    tmp += 1
            pre_node.back = node
            next_node.front = node
            node.front = pre_node
            node.back = next_node

 

4. erase

    def erase(self, i: int)-> object: # list의 index i에 위치하는 element e 제거
        cur_node = self.head.back
        tmp = 0
        
        if i>=self.size() or i<0: # index가 size보다 크거나 같거나, 0보다 작은 경우
            print('out of index')
            return None
        elif self.empty(): # list가 비어있을 경우
            print('list is empty')
            return None
        else:
            while True:
                if tmp==i:
                    break
                else:
                    cur_node = cur_node.back
                    tmp += 1
            tmp_el = cur_node.element
            pre_node = cur_node.front
            next_node = cur_node.back
            pre_node.back = next_node
            next_node.front = pre_node
            return tmp_el

 

5. 테스트

if __name__ == "__main__":
    d_list = D_linked_list()
    print('made d_list')
    print(f'd_list.empty(): {d_list.empty()}')
    print(f'd_list.size(): {d_list.size()}')
    print(f'd_list.begin(): {d_list.begin()}')
    print(f'd_list.end(): {d_list.end()}')
    print()
    
    d_list.insert(0, 1)
    print('insert (0, 1)')
    print(f'd_list.empty(): {d_list.empty()}')
    print(f'd_list.size(): {d_list.size()}')
    print(f'd_list.begin(): {d_list.begin()}')
    print(f'd_list.end(): {d_list.end()}')
    print()
    
    d_list.insert(1, 2)
    d_list.insert(2, 3)
    print('insert (1, 2), (2, 3)')
    print(f'd_list.empty(): {d_list.empty()}')
    print(f'd_list.size(): {d_list.size()}')
    print(f'd_list.begin(): {d_list.begin()}')
    print(f'd_list.end(): {d_list.end()}')
    print()
    
    d_list.insert(1, 10)
    print('insert (1, 10)')
    print(f'd_list.empty(): {d_list.empty()}')
    print(f'd_list.size(): {d_list.size()}')
    print(f'd_list.begin(): {d_list.begin()}')
    print(f'd_list.end(): {d_list.end()}')
    print()
    
    print(f'd_list.erase(1): {d_list.erase(3)}')
    print(f'd_list.empty(): {d_list.empty()}')
    print(f'd_list.size(): {d_list.size()}')
    print(f'd_list.begin(): {d_list.begin()}')
    print(f'd_list.end(): {d_list.end()}')
    print()

 

예상 출력:

'''
made d_list
d_list.empty(): 1
d_list.size(): 0
d_list.begin(): None
d_list.end(): None

insert (0, 1)
d_list.empty(): 0
d_list.size(): 1
d_list.begin(): 1
d_list.end(): 1

insert (1, 2), (2, 3)
d_list.empty(): 0
d_list.size(): 3
d_list.begin(): 1
d_list.end(): 3

insert (1, 10)
d_list.empty(): 0
d_list.size(): 4
d_list.begin(): 1
d_list.end(): 3

d_list.erase(1): 3
d_list.empty(): 0
d_list.size(): 3
d_list.begin(): 1
d_list.end(): 2

'''

 

전체 코드는 github에 올려주었습니다.

github.com/imgzon3/algorithm/blob/main/Linked_LIst/double_linked_list.py

imgzon3/algorithm