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