[Python] LinkedList

Array VS Linked List

Array 

• 각 원소에 인덱스로 즉시 접근할 수 있다. -> 시간 복잡도 O(1)
• 원소를 중간에 삽입/삭제를 하려면 모든 원소를 다 옮겨야 한다. -> 시간 복잡도 O(N)

Linked List

• 특정 원소에 접근하려면 연결 고리를 따라 탐색해야 한다. -> 시간 복잡도 O(N)
• 원소를 중간에 삽입/삭제하기 위해서는 앞 뒤의 포인터만 변경하면 된다. -> 시간 복잡도 O(1)

결론

• 조회가 자주 발생한다면? Array 
• 수정이 자주 발생한다면? LinkedList

Linked List 구현

LinkedList는 데이터(data)를 가지고 있고 다음 Node를 가리킬 pointer(next)가 있는 Node가 필요하다.

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

# 3을 가진 Node 를 만드려면 아래와 같이 하면 됩니다!
node = Node(3) # 현재는 next 가 없이 하나의 노드만 있습니다. [3]

이제 Node 클래스를 이용해서 LinkedList를 구현한다.

LinkedList는  반드시 Head 노드를 가져야 한다. 그러니 LinkedList의 생성자에서 무조건 Head 노드가 생성되도록 한다.

class LinkedList:
    def __init__(self, value):
        self.head = Node(value)  # head 에 시작하는 Node 를 연결합니다.


linked_list = LinkedList(5)
print(linked_list.head.data) # 5가 출력됩니다!

삽입(가장 뒤에 append) 구현

...
    def append(self, value):  # LinkedList 가장 끝에 있는 노드에 새로운 노드를 연결합니다.
        if self.head is None: # 헤드노드 없는 경우 추가되는 노드가 헤드노드가 되도록 처리
            self.head = Node(value)
            return
            
        cur = self.head         
        while cur.next is not None: # cur의 다음이 끝에 갈 때까지 이동합니다. 
            cur = cur.next          
        cur.next = Node(value)
...

조회(get) 구현

...
    def get_node(self, index):
        node = self.head
        count = 0
        while count < index:
            node = node.next
            count += 1
        return node
...

추가(중간에 add) 구현

...
   def add_node(self, index, value):
        new_node = Node(value)
        if index == 0:
            new_node.next = self.head
            self.head = new_node
            return

        node = self.get_node(index - 1)
        next_node = node.next
        node.next = new_node
        new_node.next = next_node
...

삭제(delete) 구현

...
   def delete_node(self, index):
      if index == 0:
         self.head = self.head.next
         return
        
      node = self.get_node(index - 1)
      node.next = node.next.next
...

[스파르타 코딩 클럽] 알고 보면 알기 쉬운 알고리즘