Algorithm

single linked list

algorithm, python, single linked list
  • Node = data + link
  • head(list의 첫번째 노드를 가리킴)
  • d_size(list의 요소 개수) 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    class Node:

        def __init__(self, data = None):
            self.__data = data   # 노드 안에 데이터 변수
            self.__link = None   # 노드를 가리키기 위한 변수
            
        # 소멸자
        # 객체가 사라지기 전에 반ㄷ시 한번 호출하는 것을 보장한다.
        # 객체가 언제 소멸하는지를 알아보기 위해 적용
        def __del__(self):
            print(f"node[{self.__data}] deleted!!")
            
        @property
        def data(self):
            return self.__data
        
        # setter를 지정할 땐 getter와 함수 이름을 같게 한다.
        @data.setter
        def data(self, data):
            self.__data = data
            
        @property
        def link(self):
            return self.__link
        
        @link.setter
        def link(self, link):
            self.__link = link


    class SLinkedList:

        def __init__(self):
            self.head = None  # 리스트의 첫번째 노드를 가리키는 변수
            self.d_size = 0   # 리스트의 요소 개수
            
        def empty(self):
            if self.d_size == 0:
                return True           # 리스트의 요소 개수가 0이면 True
            else:
                return False          # 0이 아니면 False
           
        def size(self):
            return self.d_size        # 리스트의 요소 개수 반환
        
        def add(self, data):
            new_node = Node(data)
            new_node.link = self.head # 새로운 노드가 head를 가리키게 함
            self.head = new_node      # head가 새로운 노드를 가리키게 함
            self.d_size += 1          # 잊지 말고 1을 더해줘야 함
            
        def search(self, target):
            cur = self.head
            
            while cur:
                if cur.data == target:
                    return cur        # target과 같다면 노드 객체 자체를 받음
                else:
                    cur = cur.link    # 헷갈리면 link를 next로 보자.                    
            return cur
        

        def delete(self):
            
            if self.empty():
                return
            
            # head를 head.next로 가리키게 하면 기존 head가 가리키고 있는
            # 노드 객체는 reference count가 0이 되어 자동으로 사라진다.
            self.head = self.head.link
            self.d_size -= 1       # 잊지 말고 1을 빼준다.
        
        # 리스트 출력을 보기 위해 만든 함수
        def show(self):
            cur = self.head
            
            for _ in range(self.size()):
                print(cur.data, end = " ")
                cur = cur.link
            print("")


    if __name__ == "__main__":
       
        sll = SLinkedList()
       
        sll.add(1)
        sll.add(3)
        sll.add(4)
        sll.add(6)
        sll.add(8)
        sll.add(11)
        
        sll.show()
        
        target = 7
        
        result = sll.search(target)
        
        if result:
            print(f'searched data : {result.data}')
        else:
            print('there is no such data')
            
        sll.delete()
        
        print("*"*20)  # 객체 소멸 시기를 알기 위해 기준점 역할

    >> 11 8 6 4 3 1
       there is no such data
       node[11] deleted!!
       ********************
       node[1] deleted!!
       node[3] deleted!!
       node[4] deleted!!
       node[6] deleted!!
       node[8] deleted!!
Share