Python 단 방향 링크 실현 (하): 통합 식 추가 삭제 및 검사 작업 실현

파 이 썬 단 방향 링크 구현 (상): 15 가지 추가 삭제 및 검사 작업
전에 코드 를 써 서 단 방향 링크 의 조작 을 실현 했다.소 백 으로 비교적 비대 하 게 썼 다.또 첨삭 검사 등 유사 한 조작 을 통합 시 켰 는데, 이곳 의 코드 는 전편 의 것 보다 약간 간결 하 다
대체적인 사고 방식.
지난 편의 사고 와 마찬가지 로 두 가지 유형 을 쓴다.
  • Node 클래스: 노드 를 만 들 고 노드 를 메모리 주소
  • 대신 알 아 볼 수 있 는 문자열 로 출력 합 니 다.
  • LinkedList 류: 이런 방법 에서 변경 되 었 습 니 다.이 종 류 는 각 노드 를 링크 로 연결 하고 링크 를 조작 하 는 방법
  • 을 실현 하 는 데 사용 된다.
    노드 클래스 만 들 기:
    class Node:
        def __init__(self, data, next=None):
            self.data = data #   ,       
            self.next = None #   ,       
    
        def __repr__(self): #            
            return "NodeValue({})".format(self.data)
    

    호출 테스트:
    n = Node(1)
    print(n) #     __repr__  ,      Node(1),       
    

    LinkedList 클래스 만 들 기:
    준비 작업: 초기 화 방법 & 문자열 인쇄 방법 이 원 하 는 출력 효 과 는 NodeValue (1) -- > NodeValue (3) -- > NodeValue (4) -- > END 와 유사 합 니 다.
    class LinkedList:
        def __init__(self):
            self.head = None #       
            self.tail = None #       
            self.size = 0 #        
    
        ##     
        def __repr__(self):
            cursor = self.head
            string_repr = ""
            while cursor:
                #  f  ,              python   
                string_repr += f"{cursor} --> "
                cursor = cursor.next
            return string_repr + "END"
    

    다음은 실현 방법의 코드 입 니 다.
    1. get (index) 에서 색인 을 전송 하고 이 색인 위치 에 있 는 결점 을 되 돌려 줍 니 다.
    #     ,           
        def get(self, index):
            """
            :param index:   ,    0  ,    -1  
            """
            #                 
            if index >= 0:
                leftindex = index
            else:
                leftindex = index + self.size
            #     
            current = self.head
            for i in range(leftindex):
                current = current.next
            return current
    

    2. insert (index, data) 는 링크 에 지정 한 위치 에 노드 를 삽입 합 니 다.
        def insert(self, index, data):
            #                 
            if index < 0:
                # leftindex    1,    self.size
                leftindex = self.size + index + 1
            else:
                leftindex = index
    
            new_node = Node(data)
    
            if (index >= 0 and index > (self.size)) or (index < 0 and leftindex > self.size):  #          ,  
                self.size -= 1
                raise Exception("Index out of range")
    
            elif self.size == 0:  #           
                self.head = new_node
                self.tail = new_node
                self.size += 1
    
            elif index == 0 or (index < 0 and leftindex == 1):  #            
                new_node.next = self.head
                self.head = new_node
                self.size += 1
    
            elif index == (self.size-1) or index == -1:  #            
                print("    ")
                self.tail.next = new_node
                self.tail = new_node
                self.size += 1
    
            else:  #            
                if index >= 0:
                    pre = self.get(index - 1)
                    new_node.next = pre.next
                    pre.next = new_node
                    self.size += 1
                else:
                    pre = self.get(leftindex - 1)
                    new_node.next = pre.next
                    pre.next = new_node
                    self.size += 1
    

    3. remove (index, data) 링크 에서 지정 한 위치의 노드 삭제
        def remove(self, index):
            #                 
            if index < 0:
                #    leftindex    0,    self.size
                #          
                leftindex = index + self.size
            else:
                leftindex = index
    
            if leftindex < 0 or leftindex >= self.size: #          ,  
                raise Exception("Index out of range")
    
            if leftindex == 0: #           
                remove_node = self.head
                self.head = self.head.next
    
            elif leftindex == (self.size-1): #           
                pre = self.get(leftindex-1)
                remove_node = pre.next
                pre.next = None
                self.tail = pre
    
            else: #          
                pre = self.get(leftindex-1)
                remove_node  = pre.next
                pre.next = pre.next.next
    
            self.size -= 1
            return remove_node.data
    

    4. reverse () 반전 링크
        def reverse(self):
            if self.size == 0 or self.size == 1:
                return self
            else:
                current = self.head
                pre = None
                while current:
                    #               
                    next_node = current.next
                    #                   
                    current.next = pre
                    #      
                    pre = current
                    #       
                    current = next_node
                #      
                self.head = pre
                self.tail = next_node
            return self
    

    Info
    Author: Shanshan Yan
    Wechat: shanshan700224
    Copyright: All rights reserved

    좋은 웹페이지 즐겨찾기