[알고리즘] 연결 리스트 (4)

문제

연결 리스트에서 특정한 데이터 값을 갖는 노드의 개수를 계산하는 함수를 작성하라. (python)

소스코드

class Node:
    def __init__(self, elem, link=None):
        self.data = elem  # 데이터 필드 생성 및 초기화
        self.link = link  # 링크 필드 생성 및 초기화

class LinkedList:
    def __init__(self):
        self.head = None
    
    def isEmpty(self): return self.head == None
    
    def display(self, msg='LinkedList:'):
        print(msg, end=' ') #메시지를 먼저 출력 
        node = self.head
        while not node == None:
                print(node.data, '-> ', end='')
                node = node.link
        print('None')
    
    # 원하는 데이터를 가진 노드 찾기 
    def find_cnt(self, data):
        node = self.head;
        cnt = 0
        while node is not None:
            if node.data == data : cnt = cnt+1
            node = node.link
        return cnt
    
    # pos 번째 노드 반환
    def getNode(self, pos):
        if pos < 0 : return None
        node = self.head;
        while pos > 0 and node != None: #pos번 반복 
            node = node.link # 다음 노드로 이동 
            pos -= 1 # 남은 반복 횟수 줄임 
        return node
    
    # 삽입 
    def insert(self, pos, elem):
        before = self.getNode(pos-1) # before 노드를 찾음 
        if before == None : # 맨앞에 삽입하는 경우 
            self.head = Node(elem, self.head) # 멘 앞에 삽입함 
        else : 
            node = Node(elem, before.link) #  노드 생성하고 N이 C를 가리키게함 
            before.link = node # B가 N을 가리키게 함 

q = LinkedList()
# 데이터 입력 
q.insert(0,5); q.insert(1,5); q.insert(2,7)
q.display()
# 탐색 데이터 입력 
search = int(input("탐색할 값을 입력하시오 : "))
cnt = q.find_cnt(search)

print("%s는 연결리스트에서 %s번 나타납니다." %(search, cnt))

실행 결과