문과생이 이해한 파이썬 연결리스트1(삽입/삭제/출력/탐색/역순)

<c언어로 쉽게 풀어쓴 자료구조>를 파이썬 코드로 바꿈

 

class Node:
    def __init__(self, data):
        self.data=data
        self.link=None
        
class LinkedList:
    def __init__(self, data):
        new_node=Node(data)
        self.head=new_node
        
    def insert_first(self, data):
        new_node=Node(data)
        new_node.link=self.head
        self.head=new_node
        
    def insert_last(self, data):
        new_node=Node(data)
        node=self.head
        while node.link is not None:
            node=node.link
        node.link=new_node
        
    def search(self, data):
        node=self.head
        leading=None
        while True:
            if node==None:
                print('x')
                return 
            
            if node.data==data:
                return leading, node
            else:
                leading=node
                node=node.link
    
    def delete(self, data):
        if self.head==None:
            print("리스트가 비어있습니다.")
        
        leading_node, delete_node=self.search(data)
        if leading_node==None:
            self.head=delete.node.link
        else:
            leading_node.link=delete_node.link
        
    def reverse(self):
        left=None
        target=self.head
        right=target.link
        while target.link is not None:
            target.link=left
            left=target
            target=right
            right=right.link
        target.link=left
        self.head=target
            
    def __str__(self):
        print_list='['
        node=self.head
        while True:
            if node==None:
                break
            print_list+=node.data
            print_list+=', '
            node=node.link
        print_list+=']'
        return print_list
        
fruit_list=LinkedList('APPLE')
fruit_list.insert_first('BLUEBERRY')
fruit_list.insert_first('CHERRY')
fruit_list.insert_last('MANGO')
print(fruit_list)

 

 

 

 방학에도 쉴 수 없는 즐거운 영구실 생활....

 

 

---

 

#__init__

 

 23번째 줄부터 실행하자. fruit_list라는 객체를 선언하고 인자값으로 'APPLE'을 보내면 7줄의 초기화 메소드가 자동으로 실행 된다. 

 

 

 요로코롬. 참고로 객체가 선언되면 객체 안에 인스턴스 변수(self.head 등 self가 붙은 변수) 및 메소드 등. class 안에 들어있는 요소들이 다 들어간다. __가 앞 뒤로 있는 건 특수 메소드로 어떤 연산을 진행했을 때 자동으로 메소드가 실행된다. ex) 객체를 print할 때나 처음 객체 선언할 때.

 

 

 

 초기화 메소드에서는 다시 Node 클래스의 new_node라는 객체를 선언한다. 이 부분은 C의 구조체 부분과 유사하쥬? 

 

 

---

딴 소리인데 C에서도 구조체 내 구조체가 가능한지 모르겠다. 근데 파이썬에서는 클래스 내 클래스 가능ㅇㅇ

 요로케해도 되는 거 보고... 와 이래서 파이썬~파이썬~ 하는구나 싶었다. 암튼 연결리스트 같이 노드가 필요한 경우 클래스 내 클래스로 표현하는게 더 좋을 것 같다는 생각

 

---

 

 연력리스트의 헤드가 될 self.head에 new_node를 저장하면 초기화 메소드 끗

 

 

---

#insert_first

 

 insert_first는 head 앞에 새로운 노드를 추가한다. 그래서 저대로 실행하면 

 

 요로코롬 체리도 실횅하면 아래와 같이 되겠쥬?

 

 

---

#insert_last

 

 다음은 insert_last. 노드의 가장 마지막에 노드를 넣는 연산이다.

 

 17, 18줄까지 실행하고. while문을 통해 node.link가 None이 아닐 때까지 반복한다. 10'까지 이동하면 10'의 link를 new_node로 바꿔줌 끗

 

 

 

---

#__Str__

 

 이것도 초기화 메소드와 마찬가지로, 객체를 print하면 자동으로 실행되는 특수 메소드이다. 

(여기는 새로 만들기 귀찮으므로 전에 만들었던 발표 자료를 첨부...ㅎㅎㅎ)

 

 

 일단 객체를 print한다. __str__은 이름에서 알 수 있듯 문자열만 반환하기 때문에, 연결리스트를 순회하여 얻은 데이터들은 문자열로 변환하여 저장해야 한다. (지금은 data가 문자열이지만 정수를 저장할 때는 str(node.data) 이런 식으로 저장해야 됨)

 

 

 

 반환할 문자열의 처음에 대괄호를 넣어주고, 순회노드인 node에 self.head를 저장한다. 

 

 그리고 여기서는 node가 None이 아닐 때까지 반복하며, print_list문자열에 데이터들을 저장한다. 그리고 link필드를 통해 다음 노드로 이동하는 식으로 oo

 

 그리고 연결리스트의 모든 데이터를 담은 문자열 print_list를 넘겨주면 완벽...!!!

 

 

 

(APPLE뒤에 콤마가 불편하면 코드를 좀만 수정하면 된다...)

 

 

---

#delete

 

특정 노드를 삭제할 거다.

 여기서 search 메소드는 탐색할 때 그 search 메소드와 다른 메소드다. delete_node는 삭제할 노드고 leading_nodes는 그를 뒤따라가는 노드로, 노드를 삭제하고 뒤의 노드와 연결하기위해 leading_node를 만들었다. 

 

 

 무한 반복문 안에서 28줄은 해당 연결리스트 안에서 원하는 데이터 값을 찾지 못했을 경우에 실행할 코드이다. 

 

 32줄의 if문은 원하는 데이터를 찾았을 때, else문은 찾지 못했지만 node가 None이 아닐 때 다음 노드로 이동하기 위한 코드를 작성했다.

 

 

 일단 else문을 실행하고 나면 현재 node가 가리키는 data와 사용자가 찾으려는 data가 똑같은 것을 알 수 있다. 

 

 

 여기서 leading_node가 None이라는 것은 search 메소드에서 초기화한 상태와 동일하다는 의미이다. 즉, 찾으려는 노드가 self.head에 저장되어있는 상태! 따라서 head에 delete_node.link를 저장해준다.

 

 

 그러나 지금은 lead_node가 None이 아니므로 else문을 실행한다. 

 

 

 

---

#search

 

 

 탐색은 아까전에 delete할 때와 비슷하긴 하다. 다만 return하는게 조금 다를 뿐.

 

---

#reverse

 

연결리스트를 역순으로 바꾸기 위해서는 3개의 변수가 필요하다. ㅍ

 

 

 while문의 조건에 맞추면서 각 변수들을 다음 노드로 이동시킨다. 

 

 그리고 왜 target.link에서 멈추냐면. right가 None이기 때문에 더이상 갈 수 가 없음... 마지막 노드가 연결이 안 되 있는게 보일텐데 이건 while문 밖에서 다시 연결해준다. 마지막으로 self.head에 마지막 노드를 저장하면 끗.

 

 

 

 

 

 

---

 이건 교재 코드를 내가 쌩으로 옮긴거라서 사실 더 좋은 코드가 잇을 수도 잇다...! 찾아보니까 파이썬으로 구현한 자료구조 책도 있는데. 책을 새로 살 돈으로 차라리 술먹으려고 실력향상을 위해 C코드를 파이썬으로 옮기고 잇다