[자료구조] LinkedList (feat. python)

단방향 연결 리스트

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

    def __str__(self):
        return str(self.key)


class SinglyLinkedList:
    def __init__(self):
        self.head_node = Node()
        self.size = 0

    def __len__(self):
        return self.size

    def __iter__(self):
        v: Node = self.head_node
        while v is not None:
            yield v
            v = v.next

    def search_by_key(self, key):
        if len(self) == 0: return None

        v: Node = self.head_node
        while v is not None:
            if v.key == key:
                return v
            v = v.next
        return None

    def search_by_index(self, index):
        if len(self) == 0 or index < 0 or len(self) < index:
            return None

        i = 0
        v: Node = self.head_node
        while i != index:
            v = v.next
            i += 1
        return v


    def push_front(self, key):
        new_node = Node(key)
        new_node.next = self.head_node
        self.head_node = new_node
        self.size += 1

    def push_back(self, key):
        new_node = Node(key)
        if len(self) == 0:
            self.head_node = new_node
        else:
            tail: Node = self.head_node
            while tail.next is not None:
                tail = tail.next
            tail.next = new_node
        self.size += 1

    def pop_front(self):
        if len(self) == 0:
            return None

        target: Node = self.head_node
        self.head_node = target.next
        self.size -= 1

        key = target.key
        del target
        return key

    def pop_back(self):
        if len(self) == 0:
            return None

        prev: Node = None
        tail: Node = self.head_node
        while tail.next is not None:
            prev, tail = tail, tail.next

        if len(self) == 1:
            self.head_node = None
        else:
            prev.next = None
        self.size -= 1
        key = tail.key
        del tail
        return key

    def insert(self, index, key):
        if len(self) == 0 or index < 0 or len(self) < index:
            # raise IndexError('Index Error')
            return None
        new_node = Node(key)
        i = 0
        prev: Node = None
        target: Node = self.head_node
        while i != index:
            prev, target = target, target.next
            i += 1
        prev.next = new_node
        new_node.next = target
        self.size += 1


    def remove(self, index):
        if len(self) == 0 or index < 0 or len(self) < index:
            # raise IndexError('Index Error')
            return None
        i = 0
        prev: Node = None
        target: Node = self.head_node
        while i != index:
            prev, target = target, target.next
            i += 1
        prev.next = target.next
        key = target.key
        self.size -= 1
        del target
        return key


#==========================이하 테스트 코드==========================
ll = SinglyLinkedList()
for i in range(10):
    ll.push_back(i)

print('INIT: ')
for v in ll:
    print(f'{v}', end=' ')
print()

popped = ll.pop_back()
print(f'popped: {popped}')

searched = ll.search_by_index(2)
print(f'search_by_index - 2: {searched}')

searched = ll.search_by_key(4)
print(f'search_by_key - 4: {searched}')

removed = ll.remove(2)
print(f'removed - 2: {removed}')

ll.push_front(100)

print('PUSH-F: ')
for v in ll:
    print(f'{v}', end=' ')
print()

ll.insert(100, 3)
# expected Index Error

print('INSERT: ')
for v in ll:
    print(f'{v}', end=' ')
print()

양방향 연결 리스트

class Node:
    def __init__(self, key=None):
        self.key = key
        self.prev, self.next = self, self

    def __str__(self):
        return str(self.key)

class CircularDoublyLinkedList:
    def __init__(self):
        self.head_node = Node()
        self.size = 0

    def __len__(self):
        return self.size

    def __iter__(self):
        if len(self) == 0:
            return
        v = self.head_node.next
        while v is not self.head_node:
            yield v
            v = v.next

    def splice_list(self, a: Node, b: Node, x: Node):
        a_prev, b_next, x_next = a.prev, b.next, x.next

        # [a .. b] 까지 자른 후, a_prev 와 b_next 를 봉합
        a_prev.next = b_next    # a_prev 의 다음 노드는 b_next
        b_next.prev = a_prev    # b_next 의 이전 노드는 a_prev

        # 이하 x - [a .. b] - x_next 를 위한 코드
        # x 와 a 를 봉합
        x.next = a              # x 의 next link 는 a
        a.prev = x              # a 의 prev link 는 x

        # b 와 x.next 를 봉합
        b.next = x_next         # b 의 next link 는 x_next 로 설정
        x_next.prev = b         # x_next 의 prev link 는 b 로 설정

        # 즉, 아래의 1번 상황에서 2번 상황으로 변경됨
        # 1. x - x_next - .. - a_prev - [ a .. b ] - b_next
        # 2. x - [ a .. b ] - x_next - .. - a_prev - .. - b_next

    def search_by_key(self, key):
        if len(self) == 0:
            return None

        v = self.head_node.next
        while v is not self.head_node:
            if v.key == key:
                return v
            v = v.next
        return None

    def search_by_index(self, index):
        if len(self) == 0 or index < 0 or len(self) < index:
            return None

        i = 0
        v = self.head_node.next
        while i != index:
            v = v.next
            i += 1
        return v

    def move_after(self, a, x):
        self.splice_list(a, a, x)

    def move_before(self, a, x):
        self.splice_list(a, a, x.prev)

    def insert_after(self, key, x):
        self.move_after(Node(key), x)
        self.size += 1

    def insert_before(self, key, x):
        self.move_before(Node(key), x)
        self.size += 1

    def insert_using_index(self, index, key):
        target = self.search_by_index(index)
        self.insert_before(key, target)

    def push_front(self, key):
        self.insert_after(key, self.head_node)

    def push_back(self, key):
        self.insert_before(key, self.head_node)

    def remove(self, x: Node):
        if x is None or x == self.head_node:
            return None
        x_prev, x_next = x.prev, x.next

        x_prev.next = x_next
        x_next.prev = x_prev
        key = x.key
        self.size -= 1

        del x
        return key

    def pop_front(self):
        if len(self) == 0:
            return None
        return self.remove(self.head_node.next)

    def pop_back(self):
        if len(self) == 0:
            return None
        return self.remove(self.head_node.prev)

    def remove_using_index(self, index):
        target = self.search_by_index(index)
        return self.remove(target)


#==========================이하 테스트 코드==========================
ll = CircularDoublyLinkedList()
for i in range(10):
    ll.push_back(i)

print('INIT:')
for v in ll:
    print(f'{v}', end=' ')
print()

print(f'POP_FRONT: {ll.pop_front()}')

for v in ll:
    print(f'{v}', end=' ')
print()

print(f'REMOVE_USING_INDEX: {ll.remove_using_index(3)}')

for v in ll:
    print(f'{v}', end=' ')
print()

searched = ll.search_by_key(3)
print(f'SEARCH_KEY: {searched}')

searched = ll.search_by_index(7)
print(f'SEARCH_INDEX: {searched}')