[Python 자료구조] 연결리스트(Linked List) feat.LeetCode

💡 연결리스트(Linked List)

📌 연결리스트란?

연결리스트는 다른 추상 자료형(Abstract Data Type)을 구현할 때 기반이 되는 기초 선형 자료구조이다.
각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장한다. 연결리스트의 두드러지는 특징들을 배열과 비교해서 보면 좋다.

출처: <파이썬 알고리즘 인터뷰> p.199, 책만, 2020

📚 배열 VS 연결리스트

• 배열은 물리적인 메모리 주소가 연속적이고, 연결리스트는 물리 메모리 주소가 연속적이지 않고 랜덤이다.
• 배열은 삽입/삭제가 O(n)의 시간이 걸리지만, 동적으로 연결된 연결리스트는 삽입/삭제에 O(1)이 걸린다.
• 배열은 각 원소에 인덱스로 O(1)의 시간으로 손쉽게 접근이 가능하다. 그러나 연결리스트는 O(n)의 시간이 소요된다. (배열과 다르게 연결된 메모리가 아니기 때문에, 데이터를 찾기 위해서는 모든 노드를 거쳐서 탐색해야 한다.)

📌 연결리스트 종류

연결리스트에는 싱글 연결리스트(Singly Linked List), 더블 연결리스트(Doubly Linked List), 원형 연결리스트(Circular Linked List)가 있다.
그 중 이 글에서는 가장 기본적인 싱글 연결리스트에 대해 다룰 예정이다.

📌 싱글 연결리스트(Singly Linked List)

자료구조에 대한 구현보다는 간단하게 연결 가능한 노드만 정의해서 노드를 가지고 연결리스트의 동작을 살펴 보려한다.

자세한 구현은 파이썬으로 구현한 자료구조 - 연결 리스트 혹은 파이썬 자료구조 8-1장. 연결 리스트 글을 참고하세요.

📚 노드 정의

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

📚 연결리스트 생성

보통 헤더를 선언하여 연결리스트를 생성하고,
헤더를 통해 다른 모든 노드를 탐색하고 참조할 수 있다.
따라서, head를 직접 이동시키지 않고, node=head로 head주소를 참조하여 사용한다.
(원래 헤더는 data를 포함하고 있지 않으며, 헤더의 다음 노드부터 데이터를 가지나 편의상 임의의 값을 넣고 다음 노드부터 사용해도 되고, head노드 부터 사용해도 된다.)

head = ListNode(0)

📚 노드 추가(삽입)

#add new_node
curr_node = head

new_node = ListNode(1)
curr_node.next = new_node
curr_node=curr_node.next

curr_node.next = ListNode(2)
curr_node=curr_node.next

curr_node.next = ListNode(3)
curr_node=curr_node.next

curr_node.next = ListNode(4)
curr_node=curr_node.next

📚 전체 연결리스트 출력 (탐색)

#print all node
node=head
while node:
    print(node.val)
    node=node.next
''' 출력결과 : 0,1,2,3,4 '''

📚 노드 탐색하여 삭제

#delete node by value
node=head
while node.next:
    if node.next.val==2:
        next_node=node.next.next
        node.next=next_node
        break
    node=node.next
    
node=head
while node:
    print(node.val)
    node=node.next
''' 출력결과 : 0,1,3,4 '''

📌 연결리스트 예제풀이

📚 연결 리스트 뒤집기 LeetCode 206. Reverse Linked List

• 입력
  1->2->3->4->5->NULL
• 출력
  5->4->3->2->1->NULL

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        curr,prev = head, None
        while curr:
            next,curr.next = curr.next, prev
            prev, curr = curr, next
        return prev

curr,prev에 각각 head, None을 가르키게 하고 반복한다. 반복문에서는 curr의 다음 노드 주소를 next에 저장하고, curr의 다음 주소를 prev로 연결한다. 그럼 현재 노드 다음 차례에 prev 노드와 이하 연결된 노드들이 따라 온다. prev에 다시 curr노드 주소를 저장하고(curr 다음 노드에 prev가 연결되었으므로 curr+prev를 prev에 저장하는 것이다.) curr는 이제 원래 연결 리스트에서 가르키던 다음 노드인 next의 주소로 이동한다.

🔍 1회 반복

curr : 1->2->3->4->5
prev : None
next : 2->3->4->5

curr.next = prev
(curr : 1->None)

prev,curr = curr,next
(prev : 1->None)
(curr : 2->3->4->5)

🔍 2회 반복

curr : 2->3->4->5
prev : 1->None
next : 3->4->5

curr.next = prev
(curr : 2->1->None)

prev,curr = curr,next
(prev : 2->1->None)
(curr : 3->4->5)

(이후 반복은 동일하므로 똑같이 따라해보는 것을 추천한다.)

📚 두 정렬 리스트 병합 LeetCode 21. Merge Two Sorted Lists

• 입력
  1->2->4, 1->3->4
• 출력
  1->1->2->3->4->4

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def mergeTwoLists(self, l1, l2):
        node = ListNode(0)  
        cur = node
        while l1 and l2:  
            if l1.val <= l2.val:  
                cur.next = l1  
                l1 = l1.next  
            else:  
                cur.next = l2  
                l2 = l2.next  
            cur = cur.next  
        cur.next = l1 or l2  
  
        return node.next  

cur.next = l1 or l2 은 두 연결리스트 중 None이 아닌 연결리스트가 있다면 그 리스트를 반환 혹은 둘 다 None이라면 None을 반환하기 때문에, 연결리스트 l1과 연결리스트 l2의 길이가 다른 경우 두 리스트중 한 리스트가 먼저 소진되기 때문에, 남은 리스트를 연결해주는 코드부분이다.