[파이썬] Double linked list 구현

아주 좋은 설명 블로그 1 링크

[Python] 더블 링크드 리스트 (이중 연결 리스트)

아주 좋은 설명 블로그 2 링크 

[파이썬] Linked List, Doubly Linked List 직접 구현하기

 

코드 구현 

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

class DList(object):
    def __init__(self):
        self.head=Node(None,None,None)
        self.tail=Node(None,self.head,None)
        self.head.next=self.tail
        self.size=0
    
    def listSize(self):
        return self.size
    
    def is_empty(self):
        if self.size==0:
            return True
        else:
            return False
    
    def selectNode(self,idx): # 삽입하거나 삭제할때 몇번째에 삽입하거나 삭제하므로 idx를 입력받아 노드를 찾아야함
        if idx>self.size:       # 찾는 위치가 리스트 사이즈보다 크면 
            print('Overflow: Index Error')  
            return None
        if idx==0:              # 가장 앞은 head 그대로 
            return self.head
        if idx==self.size:      # 가장 뒤는 tail 그 자체 
            return self.tail
        if idx<=self.size//2:   # 찾는 위치가 리스트 절반 앞이면 
            target=self.head    # 리스트의 가장 앞 head에서 시작해서 
            for _ in range(idx):    # idx 크기 만큼
                target=target.next  # head의 다음 위치의 다음 위치의 다음...에서 idx순서를 찾으면 됨 
            return target           # 그때의 노드 
        else:                       # 찾는 위치가 리스트 절반 뒤면 
            target=self.tail        # 꼬리부터 시작해서 
            for _ in range(self.size-idx):  # 리스트 전체크기-찾는위치 크기만큼
                target=target.prev          # 꼬리의 앞 위치의 앞 위치의 앞...에서 idx순서를 찾으면 됨 
            return target   # 그때의 노드 
    
    def appendleft(self,value):
        if self.is_empty():         # 현재 리스트가 비었다면 
            self.head=Node(value,None,None)   # 헤드는 그 값을 갖는 그자체 이전 이후 값은 디폴트로 None
            self.tail=Node(None,self.head,None)
            self.head.next=self.tail            # 연결: 현재 생긴 head 다음은 비어있는 tail
        else:
            old_head=self.head
            self.head=Node(value,None,self.head)    # value라는 값을 갖는 노드는 prev엔 아무것도 없고 next에 현재 head 연결
            old_head.prev=self.head         # 이전 head의 앞에는 이제 새로운 현재 헤드를 연결 
        # append를 하면 size가 증가함 
        self.size+=1
        
    def append(self,value):
        if self.is_empty():
            self.head=Node(value,None,None)
            self.tail=Node(None,self.head,None)
            self.head.next=self.tail
        else:
            # appendleft는 맨 앞에 넣으면 자동으로 Null이 앞에 생기지만 
            # append는 중간에 넣는 느낌으로 해야함 
            old_tail=self.tail.prev
            new_Node=Node(value,old_tail,self.tail)
            old_tail.next=new_Node
            self.tail.prev=new_Node                      
        self.size+=1
    
    def insert(self,value,idx):
        if self.is_empty():
            self.head=Node(value,None,None)
            self.tail=Node(None,self.head,None)
            self.head.next=self.tail
        else:
            target_idx=self.selectNode(idx) # 넣고싶은 위치 
            if target_idx==None:
                return
            if target_idx==self.head:  # 원하는 위치가 head위치면 
                self.appendleft(value)      # head 앞에 넣음
            elif target_idx==self.tail:    # 원하는 위치가 tail위치이면 
                self.append(value)          # tail 뒤에 넣음 
            else:                           # 원하는 위치가 head도 tail도 아닌 그 중간 어디면 
                target_idx_prev=target_idx.prev
                new_Node=Node(value,target_idx_prev,target_idx)
                target_idx_prev.next=new_Node
                target_idx.prev=new_Node
        self.size+=1
        
    def delete(self,idx):
        if self.is_empty():
            print('Underflow: index Error')
            return 
        else:
            target_idx=self.selectNode(idx)
            if target_idx==None:
                return
            elif target_idx==self.head:
                target_idx=self.head        # 지울 노드 
                self.head=self.head.next
            elif target_idx==self.tail:
                target_idx=self.tail
                self.tail=self.tail.prev
            else:
                target_idx.prev.next=target_idx.next
                target_idx.next.prev=target_idx.prev
            del (target_idx)
            self.size-=1
    
    def printlist(self):
        target = self.head
        while target != self.tail:
            if target.next != self.tail:
                print(target.data, '<=> ', end='')
            else:
                print(target.data)
            target = target.next
            
if __name__=="__main__":
    mylist = DList()            # 빈 head와 빈 tail을 만들음
    mylist.append('A')
    mylist.printlist()
    mylist.append('B')
    mylist.printlist()
    mylist.append('C')
    mylist.printlist()
    mylist.insert('D', 1)
    mylist.printlist()
    mylist.appendleft('E')
    mylist.printlist()
    print(mylist.listSize())
    mylist.delete(0)
    mylist.printlist()
    mylist.delete(3)
    mylist.printlist()
    mylist.delete(0)
    mylist.printlist()
    mylist.appendleft('A')
    mylist.printlist()

 

결과

A
A <=> B
A <=> B <=> C
A <=> D <=> B <=> C
E <=> A <=> D <=> B <=> C
5
A <=> D <=> B <=> C
A <=> D <=> B
D <=> B
A <=> D <=> B