[자료구조] Linked List 클래스 정의

스쿼드 숙제!

 

연결리스트 클래스를 정의하는 예제 코드 해석해보기

연결리스트 덕질한다는 기분으로 한줄한줄 주석 작성했다.

class Node:                                             # Node 클래스를 만들어보겠습니다.
    def __init__(self, data):                           # 초기화. 클래스를 인스턴스화 해서 객체를 생성할 수 있음. data를 인자로 받아오기.
        self.data = data                                # 노드가 저장할 데이터
        self.next = None                                # 다음 노드를 가리키는 참조, 초기값은 None
        
        
class LinkedList:                                       # LinkedList 클래스를 만듭미다.
    def __init__(self):                                 # 초기화. 이 클래스로 객체 만들 수 있음.
        self.head = None                                # head 변수 선언. 리스트의 첫 노드를 의미하며, 초기값은 없음(None).


    """리스트의 끝에 새 노드를 추가하는 함수 append"""
    def append(self, data):                             # 노드를 추가하고 싶다는 건 노드에 넣고싶은 data가 있다는 것일테니 그 data 받아오기.
        new_node = Node(data)                           # 일단 새로운 노드 new_node 변수 선언. Node 클래스의 속성에 data값을 저장해준 객체인 노드.
        if self.head is None:                           # new_node를 추가할려했는데 head(첫 노드)조차 없는 경우!!(=리스트가 비어있는경우)
            self.head = new_node                        # new_node가 첫 데이터 일테니 head로 지정해준다.
            return                                      # 할 일 끝났으니 append() 함수 종료시킴.
        
                                                        # if문 종료. 이후는 '만약 head가 있는경우(=리스트가 비어있지 않은경우)' 에 해당함.
        last_node = self.head                           # 끝노드 last_node 변수 선언. 초기값=head 부터 하나씩 따라가서 last를 찾아볼려고 일단 last=head 지정.(숫자세기할때 일단 count=0 지정하는것처럼?)
        while last_node.next:                           # 노드의 next 주소가 존재하는 동안에는 계속 반복할건데(=다음노드가 없을 때까지)
            last_node = last_node.next                  # 뭘 반복하냐면, 노드의 next가 가리키는 다음 노드로 계속 이동해줄거임. 결과는! 리스트의 끝 노드를 찾아냄!
        last_node.next = new_node                       # 그렇게 찾아낸 끝노드가 가리키는 다음 주소에 new_node를 할당해주면, 리스트 끝에 새 노드 추가 완성!


    """리스트의 모든 요소를 출력하는 함수 print_list"""
    def print_list(self):
        current_node = self.head                        # current_node 현재노드 변수 선언. 아까처럼 초기값=head 부터 시작해보자
        while current_node:                             # 현재노드가 존재하는 동안에는 계속 반복(=끝까지 가서 Null차례가 올 때까지)
            print(current_node.data, end=' ')           # 현재 노드의 data값 출력 후, 공백도 출력해주기
            current_node = current_node.next            # 다음 노드로 이동.(노드를 하나씩 거쳐가면서 각 노드의 data 출력하려고)
        print()                                         # 그냥 줄바꿈?


    """리스트의 시작 부분에 노드를 추가하는 함수 prepend"""
    def prepend(self, data):                            # 추가하고 싶은 data 받기
        new_node = Node(data)                           # new_node 새로운노드 변수 선언. Node 클래스의 속성에 data값 저장한 객체인 노드.
        new_node.next = self.head                       # 새로운 노드의 다음 주소를 head 노드로 설정. (=첫노드 앞에 새노드를 집어넣음)
        self.head = new_node                            # 이제 리스트의 시작은 새로운노드가 차지했으니, head 값을 갱신해주기


    """키에 해당하는 노드를 찾아 삭제하는 함수 delete_node"""
    def delete_node(self, key):                         # 찾고싶은 key 받기
        current_node = self.head                        # 현재노드 변수(key에 해당할 노드) 선언. 마찬가지로 일단 head부터 시작해서 찾자
        
        if current_node and current_node.data == key:   # head의 데이터가 key랑 일치한다면(=head가 바로 삭제할 노드였다면)
            self.head = current_node.next               # 현재노드의 다음 노드를 head로 지정해준다.
            current_node = None                         # 그리고 현재노드(변경전의 head) 삭제하기.
            return                                      # 할일 끝났으니 함수 종료

        prev_node = None                                # prev_node 이전노드 변수 선언. 초기값은 None.
        while current_node and current_node.data != key:# 현재노드(head부터)의 데이터가 key와 불일치하는 동안은 계속 반복:
            prev_node = current_node                    # prev노드는 현재노드로 변경해주고,
            current_node = current_node.next            # 현재노드는 다음노드로 이동. while 결과는! key와 일치하는 현재최종노드(=삭제할노드) 발견

        if current_node is None:                        # while을 끝낸 현재노드(=삭제할노드)가 none인 경우(=key에 해당하는 노드가 애초에 없는경우)
            return                                      # 함수 그냥 종료함

        prev_node.next = current_node.next              # prev노드의 next 주소를 현재노드(=삭제할노드)의 next 주소로 설정.(=한칸 건너뛰기)
        current_node = None                             # 그리고 현재노드(=삭제할노드)는 삭제해버리기.

 

끝!

 

 

 

 

 

---