Python Singly Linked List 함수들

단일 연결 리스트

연결 리스트 - 위키백과, 우리 모두의 백과사전

 

만들어 볼 것

1. Magic methods ( lt, gt, pos, repr )
2. print 함수
3. add 함수 ( add([1,2,3,4,5] )
4. getNodesInArray ( head.getNodesInArray() = [1,2,3,4,5] )
5. linkedify ( [1,2,3,4,5] 배열을 받으면, 1 -> 2 -> 3 -> ...)
6. swap ( a.value, b.value = b.value, a.value)
7. reverse (뒤집기) ( 1 -> 2 -> 3을 3 -> 2 -> 1로)
8. Python sort 함수 이용 정렬
9. Bubble sort (거품 정렬)
10. Selection Sort (선택 정렬)

 

1. Magic Methods

def __repr__(self):
    # print(head) = 1 -> 2 -> 3 -> None
    return str(self.print())

def __lt__(self, b):  # a < b
    # 값 비교, less than
    return self.value < b.value

def __gt__(self, b):  # a > b
    # 단순 값 변경
    return self.value > b.value

def __pos__(self):
    '''
    head = head.next로 하는 대신
    head = +head 짧게 쓰기 위함
    '''
    return self.next

 

2. print 함수

def print(self):
    head = self
    while head is not None:
        print(head.value, end=" -> ")
        head = +head
    print("None")

# 결과
# 11 -> 3 -> 7 -> 4 -> 2 -> 10 -> 22 -> 1 -> None

 

3. add 함수

: 배열을 받음

def add(self, values):
    current = self
    while current.next is not None:
        current = +current  # current.next
    for value in values:
        current.next = LinkedList(value)
        current = +current  # current.next
    return self
    
'''
head = LinkedList(11)
head.add([3, 7, 4, 2, 10, 22, 1])
'''

 

4. getNodesInArray

: Linked List를 배열로 변환 후 출력

def getNodesInArray(self):
    nodes = []
    current = self
    while current is not None:
        nodes.append(current.value)
        current = current.next
    return nodes

# self.getNodesInArray()
# = [1, 2, 3, 4, 5]

 

5. linkedify

@staticmethod
def linkedify(array):
    head = LinkedList(array[0])
    head.addMany(array[1:])
    return head

''' 결과
lists = self.getNodesInArray()
lists.sort()
return self.linkedify(lists)  # 배열을 다시 Linked List로 변환
'''

 

6. swap

def swap(self, b):
    self.value, b.value = b.value, self.value
    
# current.swap(i) == (current.value, i.value = i.value, current.value)

 

7. reverse

def reverse(self):
    first, second = None, self
    while second is not None:
        temp = +second  # second.next
        second.next = first
        first = second
        second = temp
    return first


''' 결과
head.addMany([3, 7, 4, 2, 10, 22, 1])

print(head.reverse())  # 1 -> 22 -> 10 -> 2 -> 4 -> 7 -> 3 -> 11 -> None
'''

 

8. sort()

def sort(self):
    # Python timSort
    lists = self.getNodesInArray()
    lists.sort()
    return self.linkedify(lists)

 

9. Bubble Sort

: 단순 반복 값 변경

def bubbleSort(self):  # in-place
    temp = self
    while temp:
        current = temp
        i = temp.next
        while i:
            if current > i:
                current.swap(i)
                # current.value, i.value = i.value, current.value
            i = +i  # i.next
        temp = +temp
    return self

''' 결과
head = LinkedList(11)
head.addMany([3, 7, 4, 2, 10, 22, 1])

print(head.bubbleSort())  # 1 -> 2 -> 3 -> 4 -> 7 -> 10 -> 11 -> 22 -> None
'''

 

10. Selection Sort

: 일반 선택 정렬처럼 가장 작은 value를 찾음

def selectionSort(self):
    temp = self
    while temp:
        minNode = temp
        i = temp.next
        while i:
            if minNode > i:
                minNode = i
            i = +i

        temp.swap(minNode)
        # temp.value, minNode.value = minNode.value, temp.value
        temp = temp.next
    return self
    
''' 결과
head = LinkedList(11)
head.addMany([3, 7, 4, 2, 10, 22, 1])

print(head.selectionSort())  # 1 -> 2 -> 3 -> 4 -> 7 -> 10 -> 11 -> 22 -> None
'''

 

 

 

 

 

 

from typing import Optional


class LinkedList:
    def __init__(self, value):
        self.value = value
        self.next: Optional[LinkedList] = None

    def __repr__(self):
        return str(self.print())

    def __lt__(self, b):  # a < b
        return self.value < b.value

    def __gt__(self, b):  # a > b
        return self.value > b.value

    def __pos__(self):  # +a
        return self.next

    def print(self):
        head = self
        while head is not None:
            print(head.value, end=" -> ")
            head = +head
        print("None")

    def addMany(self, values):
        current = self
        while current.next is not None:
            current = +current
        for value in values:
            current.next = LinkedList(value)
            current = +current
        return self

    def getNodesInArray(self):
        nodes = []
        current = self
        while current is not None:
            nodes.append(current.value)
            current = current.next
        return nodes

    @staticmethod
    def linkedify(array):
        head = LinkedList(array[0])
        head.addMany(array[1:])
        return head

    def swap(self, b):
        self.value, b.value = b.value, self.value

    def reverse(self):
        first, second = None, self
        while second is not None:
            # first, second, second.next = second, second.next, first
            temp = +second
            second.next = first
            first = second
            second = temp
        return first

    # -------- Sort --------
    def sort(self):
        # Python timSort
        lists = self.getNodesInArray()
        lists.sort()
        return self.linkedify(lists)

    def insertSort(self):
        Sorted = self
        head = +self
        Sorted.next = None
        while head is not None:
            current = head
            head = +head
            if current < Sorted:
                current.next = Sorted
                Sorted = current
            else:
                search = Sorted
                while +search is not None and current > +search:
                    search = +search
                current.next = +search
                search.next = current
        return Sorted

    def bubbleSort(self):
        temp = self
        while temp:
            current = temp
            i = temp.next
            while i:
                if current > i:
                    current.swap(i)
                    # current.value, i.value = i.value, current.value
                i = +i
            temp = +temp
        return self

    def selectionSort(self):
        temp = self
        while temp:
            minNode = temp
            i = temp.next
            while i:
                if minNode > i:
                    minNode = i
                i = +i

            temp.swap(minNode)
            # temp.value, minNode.value = minNode.value, temp.value
            temp = temp.next
        return self


if __name__ == "__main__":
    head = LinkedList(11)
    head.addMany([3, 7, 4, 2, 10, 22, 1])

    print(head)

    """
    sort 후 reverse 하려면, 아래 방식으로 해야함
    head = head.sort()
    print(head.reverse())
    """
    # print(head.sort())
    # print(head.reverse())
    # print(head.insertSort())
    # print(head.bubbleSort())
    # print(head.selectionSort())

print(head) && print(head.insertSort())