개발/Python

Linked List

Velody 2020. 7. 6. 19:23
# Node 클래스 정의
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


# LinkedList 클래스 (자료구조) 정의
class LinkedList:
    # 초기화 메소드
    def __init__(self):
        dummy = Node("dummy")
        self.head = dummy
        self.tail = dummy

        self.current = None
        self.before = None

        self.num_of_data = 0

    # Head Insert
    def append_head(self, data):
        new_node = Node(data)
        new_node.next = self.head.next
        self.head.next = new_node

        self.num_of_data += 1

    # Index노드 앞로 삽입
    # Range 초과, 미만 확인결과 정상 작동
    def append_index_before(self, data, index):
        # if index is out of list range
        if self.is_out_of_range(index):
            return

        # if index is 0, insert_head
        if index <= 0:
            self.append_head(data)
            return

        self.first()
        new_node = Node(data)

        # Pointer Jump
        for i in range(0, index-1):
            self.next()

        # Actual insertion starts here
        new_node.next = self.current.next
        self.current.next = new_node

        self.num_of_data += 1

    # Index노드 뒤로 삽입
    # Range 초과, 미만 확인결과 정상 작동
    def append_index_next(self, data, index):
        # if index is out of list range
        if self.is_out_of_range(index):
            return

        self.first()
        new_node = Node(data)

        # Pointer Jump
        for i in range(0, index):
            self.next()

        # Actual insertion starts here
        new_node.next = self.current.next
        self.current.next = new_node

        self.num_of_data += 1

    # Tail Insert
    def append_tail(self, data):
        new_node = Node(data)
        self.tail.next = new_node
        self.tail = new_node

        self.num_of_data += 1

    # 기본 Delete
    def delete(self):
        pop_data = self.current.data

        if self.current is self.tail:
            self.tail = self.before

        self.before.next = self.current.next
        self.current = self.before # 중요 : current가 next가 아닌 before로 변경된다.

        self.num_of_data -= 1

        return pop_data

    # 특정 문자 삭제
    def delete_string(self, str):
        self.first()
        # Try to delete first node
        if self.num_of_data != 0 and self.current.data == str:
            self.delete()

        # delete rest of the nodes
        while True:
            self.next()
            if self.current.data == str:
                self.delete()
            elif not self.current.next:
                break

    # 특정 인덱스 삭제
    def delete_index(self, index):
        self.first()
        # if index is greater than actual length of list
        # end the process
        if self.is_out_of_range(index):
            return

        for i in range(0, self.num_of_data):
            if index == i:
                self.delete()
                return
            self.next()

    # 여러 인덱스 삭제
    # 아직은 중복 인덱스에대해선 처리를 하지 못한다
    def delete_multiple_index(self, index):
        new_array = []

        # check if any of indices are out of range
        # leave only indices in correct range
        for i in index:
            if not self.is_out_of_range(i):
                new_array.append(i)
        new_array = sorted(new_array, reverse=True)

        # perform deleting with indices from new_array
        for i in new_array:
            self.delete_index(i)

    # 인덱스가 리스트보다 크거나 0보다 작은가
    def is_out_of_range(self, input):
        return (input+1 > self.num_of_data or input < 0)


    # first 메소드 (search1 - 맨 앞의 노드 검색, before, current 변경)
    def first(self):
        if self.num_of_data == 0: # 데이터가 없는 경우 첫번째 노드도 없기 때문에 None 리턴
            return None

        self.before = self.head
        self.current = self.head.next

        return self.current.data

    # next 메소드 (search2 - current 노드의 다음 노드 검색, 이전에 first 메소드가 한번은 실행되어야 함)
    def next(self):
        if self.current.next == None:
            return None

        self.before = self.current
        self.current = self.current.next

        return self.current.data

    def size(self):
        return self.num_of_data

# print method
def print_list(data):
    if data:
        print(data, end=' ')
        while True:
            data = l_list.next()
            if data:
                print(data, end= ' ')
            else:
                print()
                break

if __name__ == "__main__":
    l_list = LinkedList()
    l_list.append_tail(5)
    l_list.append_tail(2)
    l_list.append_tail(1)
    l_list.append_tail(2)
    l_list.append_tail(7)
    l_list.append_tail(5)
    l_list.append_tail(2)
    l_list.append_tail(11)
    l_list.append_head(30)
    l_list.append_head(20)

    print_list(l_list.first())

    # test string delete
    print()
    l_list.delete_string(5)
    print_list(l_list.first())

    # test index delete
    print()
    l_list.delete_index(9)
    print_list(l_list.first())

    # test multiple index delete
    print()
    l_list.delete_multiple_index([-1, 2, 3, 6, 7, 8, 9])
    print_list(l_list.first())

    # test insert next
    print()
    l_list.append_index_next(31, 3)
    print_list(l_list.first())

    # test insert next
    print()
    l_list.append_index_before(18, 3)
    print_list(l_list.first())