[python] Linked List 구현 - 단순 연결 리스트

python으로 Linked List 구현을 해보았다.

c언어로 구현하다가 파이썬으로 구현하려니 헷갈리고 어색하다

 

1. Link에 대한 구현

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

head=Node(3)
next_node=Node(5)
head.next=next_node

 

2. 단순 연결리스트

 

- 단순 연결리스트의 경우 head가 필요하므로 생성, 길이를 계산하는 것보단 길이를 가지고 있는게 좋을 것 같아서 길이를 추가하였다

* 성능 : O(n) < O(1) 이기 때문

 

class Node:
    def __init__(self,data):
        self.data=data
        self.next=None
        
    #입력받은 객체의 문자열 버전을 반환    
    def __str__(self):
        return str(self.data)

class SingleLinkedList:
    #초기화
    def __init__(self,data):
        newnode=Node(data) #노드 생성
        self.head=newnode
        self.size=1
        
    #출력
    def __str__(self):
        p='['
        ptr=self.head
        
        while (1):
            p+=str(ptr.data)
            if ptr.next==None:
                break
            ptr=ptr.next
            p+=','
        p+=']'
        return p
                    
        
    #첫번째 부분에 삽입    
    def insert_first(self,data):
        newnode=Node(data)
        ptr=self.head
        self.head=newnode
        self.head.next=ptr
        
        self.size+=1
    
    #마지막 부분에 삽입
    def insert_last(self,data):
        newnode=Node(data)
        ptr=self.head
        
        while ptr.next !=None:
            ptr=ptr.next
        
        ptr.next=newnode
        self.size+=1
            
    #중간 부분에 삽입(data와 삽입할 부분)    
    def insert_mid(self,num,data):
        newnode=Node(data)
        
        #삽입할 노드 전까지 이동
        ptr=self.head
        
        for i in range(num-1):
            ptr=ptr.next
        
        newnode.next=ptr.next
        ptr.next=newnode
        
        self.size+=1
        
    #노드 삭제
    def delete_node(self,num):
        ptr=self.head
        
        if num==0: #첫번째 노드를 삭제하려할때
            self.head=ptr.next
            del ptr
            return
        
        else:   
            for i in range(num-1):
                ptr=ptr.next
                
            delnode=ptr.next
            ptr.next=ptr.next.next
            
            del delnode
    
    
                    
#test
if __name__ == "__main__":
    m_list = SingleLinkedList(1)
    m_list.insert_last(5)
    m_list.insert_last(6)
    print('LinkedList :', m_list)
    #print('LinkedList Size() :', m_list.size())
 

    m_list.insert_mid(1, 15)
    print('LinkedList Insert Middle(1, 15) :', m_list)
    m_list.insert_first(100)
    print('LinkedList Insert First(100) : ', m_list)

    m_list.delete_node(0)
    print('LinkedList Delete Node(0) : ', m_list)
    m_list.delete_node(1)
    print('LinkedList Delete Node(1) : ', m_list)