파이썬 알고리즘 - 링크드리스트(LinkedList)에서 중복 제거하기

개발자 면접 트레이딩 - 파이썬 알고리즘 문제(6)

 

 

(1). 개발자 면접 트레이닝 - 링크드리스트에서 중복되는 노드 삭제(Delete) 알고리즘

① 링크드리스트는 다음 노드의 위치를 가르키고 있는 포인트 보유

② 파이썬 클래스 Next 변수 활용

③ 첫 번째 노드(Node)의 위치를 지정하는 것이 중요ㅛ

④ 예를들어 [3, 4, 5, 6, 7, 7, 8, 9, 9]  는 -> [3, 4, 5, 6, 7, 8, 9] 출력

 

 

(2). 소스 코드

PYTHON

#remove_dup_linkedlist.py
import unittest

class Node:
    def __init__(self, item):
        self.val = item
        self.next = None

class LinkedList:
    def __init__(self, item):
        self.head = Node(item)

    def add(self, item):
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(item)

    def delete_duplicate(self):
        cur = self.head
        dict = {}
        prev = None
        while cur is not None:
            if cur.val in dict:
                prev.next = cur.next
            else:
                dict[cur.val]= True
                prev = cur
            cur = cur.next

    def printlist(self):
        cur = self.head
        res = []
        while cur is not None:
            res.append(cur.val)
            cur = cur.next
        return str(res)

class LinkedListTest(unittest.TestCase):
    def test(self):
        ll = LinkedList(3)
        ll.add(4)
        ll.add(5)
        ll.add(6)
        ll.add(4)
        ll.add(7)
        ll.add(4)
        ll.add(6)
        ll.add(6)
        ll.delete_duplicate()
        self.assertEqual("[3, 4, 5, 6, 7]", ll.printlist())
        print(ll.printlist())

unittest.main()

 

(3). 소스 코드 분석

① 14 라인 : 헤드(Head) 노드 선언

② 19 라인 : 다음 노드의 주소(Next)가 None이 아닐 경우 다음 노드 연결

③ 30 라인 : 중복되는 Key 가 존재할 경우 중복되는 노드의 주소 연결을 건너뛴다.

④ 38 라인 : 중복 제거된 링크드리스트(LinkedList) 확인 출력

⑤ 62 라인 : assertEqula 단위 테스트 함수를 사용하여 입력 결과와 출력결과를 비교

 

LinkedList(링크드리스트) 관련 알고리즘 문제는 자주 활용, 출제 되므로 Java, C  등으로 작성해보자.

 

참고로 이 예제는 파이썬의 Set 메소드로 쉽게 해결 가능하다.

(4). 실행결과1 - 단위테스트 정상 출력(비교 같을 경우)

 

 

(5). 실행결과2 - 단위테스트 에러 출력(비교 다를 경우)