3. 연결 리스트(Linked list ADT) 파이썬

리스트에는 단점이 있습니다. 
마지막이 아닌 부분에 데이터를 추가하거나 삭제할 때 뒤 요소들을 모두 이동해야 하는 점이죠. 

 

연결 리스트의 장점은 중간에 추가 삭제 시 요소를 이동할 필요가 없기 때문에 좀 더 빠르게 처리할 수 있습니다.
단점은 요소의 임의 접근을 지원하지 않는다는 점이죠. 

 

연결 리스트 추상 자료형의 설계

연결 리스트는 노드를 기본으로 하는 자료형입니다. 
노드는 요소(엘리먼트)와 다른 노드를 참조하는 링크로 구성되어 있습니다. 

 

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

 

새로운 노드를 추가할 때는 링크만 수정하면 됩니다. 

 

 

연결 리스트에서는 어디서부터 시작할 지에 대한 문제가 있습니다. 
그래서 보통 헤드라고 부르는 특수(?) 노드를 이용해 시작을 표현합니다. 

 

삽입을 하려면 기존 노드를 찾아야 합니다. 
find 메서드를 만듭니다. 

 

확인을 위한 show 메서드도 만듭니다.

 

작동을 확인할 수 있을 만큼만 코딩을 했습니다. 

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

    def find(self, item):
        cur_node = self.head
        while cur_node.element != item:
            cur_node = cur_node.next
        return cur_node

    def insert(self, current, new):
        new_node = Node(new)
        cur_node = self.find(current)
        new_node.next = cur_node.next
        cur_node.next = new_node

    def show(self):
        cur_node = self.head
        while cur_node.next is not None:
            print(cur_node.element, end=' -> ')
            cur_node = cur_node.next
        print(cur_node.element)


boo = LinkedList()
boo.insert('head', '1')
boo.insert('1', '2')
boo.insert('2', '3')
boo.insert('3', '4')
boo.show()

# head -> 1 -> 2 -> 3 -> 4

 

이제 노드를 삭제해 보겠습니다. 
삭제를 하기 위해서도 삭제 바로 이전의 노드를 찾아야 합니다. 
삭제 이전 노드의 next 프라퍼티를 삭제하려는 노드의 다음 노드로 설정해야 하기 때문입니다. 

 

완성된 코드는 다음과 같습니다. 

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


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

    def find(self, item):
        cur_node = self.head
        while cur_node.element != item:
            cur_node = cur_node.next
        return cur_node

    def insert(self, current, new):
        new_node = Node(new)
        cur_node = self.find(current)
        new_node.next = cur_node.next
        cur_node.next = new_node

    def show(self):
        cur_node = self.head
        while cur_node.next is not None:
            print(cur_node.element, end=' -> ')
            cur_node = cur_node.next
        print(cur_node.element)

    def find_previous(self, item):
        cur_node = self.head
        while cur_node.next.element != item:
            cur_node = cur_node.next
        return cur_node

    def remove(self, item):
        prev_node = self.find_previous(item)
        prev_node.next = prev_node.next.next


boo = LinkedList()
boo.insert('head', '1')
boo.insert('1', '2')
boo.insert('2', '3')
boo.insert('3', '4')
boo.show()
boo.remove('2')
boo.remove('3')
boo.show()

# head -> 1 -> 2 -> 3 -> 4
# head -> 1 -> 4

 

리스트에 없는 요소를 지우려고 할 때는 에러가 발생합니다.

이에 대비해서 아래와 같이 조건문을 추가해도 좋겠습니다. 

    def find_previous(self, item):
        cur_node = self.head
        while (cur_node.next is not None) and (cur_node.next.element != item):
            cur_node = cur_node.next
        return cur_node

    def remove(self, item):
        prev_node = self.find_previous(item)
        if prev_node.next is not None:
            prev_node.next = prev_node.next.next