Algorithm & Data Structure - Linked List(2)

Original Linked List

지난 시간에 만들었던 연결 리스트는 헤드가 1번 노드를 가리키는 연결 리스트로 헤드는 1번 노드, 테일은 마지막 노드(nodeCount번 노드)를 지칭하고 있었다. 그러나 이번에는 조금 변형된 연결 리스트를 만들어 볼 것이다. 변형된 연결 리스트를 만들어봄으로써 처음 노드를 1번으로 지칭하는 이유를 알아보고 전에 구현했던 연산을 좀 더 단순하게 만들어보겠다.

Modified Linked List

변형된 연결 리스트와 전 시간의 연결 리스트와의 가장 큰 차이점은 맨 앞에 Dummy Node가 있다는 것이다.
즉, Dummy Node(None / 0 - head) --> 67(1) --> 34(2) --> 56(3 - tail)
과 같은 형태로 0번 노드에 더미 노드가 추가되었다. 또한 1번 노드 앞에 더미 노드가 추가되었으므로 헤드 또한 더미 노드(0번 노드)를 지칭하게 된다.
이런 식으로 연결 리스트를 변경하게 되면 여러 연산에서 차이점을 느낄 수 있을 것이다. 전에 만든 연결 리스트의 연산 순서대로 변형된 연결 리스트의 연산을 작성해보겠다.

우선 변형된 연결 리스트를 구현하면 다음과 같이 된다.

class LinkedList:
    def __init__(self):
    	self.nodeCount = 0
        self.head = Node(None)
        self.tail = None
        self.head.next = self.tail

원래와의 차이점은 원래의 연결 리스트는 초기에 헤드와 테일이 동일했지만(None) 변형된 연결 리스트는 헤드로 더미 노드를 가지므로 둘의 시작값이 달라지게 된다.

특정 원소 참조

사실 특정 원소 참조 연산은 전 연결 리스트와 다를게 거의 없다. 코드를 보면서 비교해보자

def getAt(self, pos):
    if pos < 0 or pos > self.nodeCount:
    	return None
    i = 0
    curr = self.head
    while i < pos:
    	curr = curr.next
        i+=1
    return curr

전과의 차이점은 헤드가 0번 노드에 위치하고 있기 때문에 0 아래의 인덱스에 접근하려 하면 None을 리턴해준다는 점에서 약간의 차이가 발생했다(0번 노드, 즉 헤드 노드에도 접근은 할 수 있으나 더미 노드이기 때문에 유의미한 값은 없을 것이다).

리스트 순회

리스트 순회도 원래의 연결 리스트와 비슷하기에 우선 코드를 보고 비교해보겠다.

def traverse(self):
    arr = []
    curr = self.head
    while curr.next is not None:
    	curr = curr.next
        arr.append(curr.data)
    return arr

과 같이 구현할 수 있다. 전과 달라진 점은 반복문에서 반복 조건으로 현재의 노드를 비교하는 것이 아니라 다음의 노드가 존재하는지 확인하면서 진행하는데, 이는 헤드 노드가 존재한다는 것이 자명하고(더미 노드의 존재 때문에) 헤드 노드의 다음 노드부터 우리가 원하는 유의미한 노드이기 때문이다.

길이 얻기

길이 얻기는 굳이 설명할 필요가 없을 것이라고 생각된다. nodeCount 값은 더미 노드를 추가한다고 해도 달라지지 않으므로 전에 만든 연결 리스트에서와 같은 방식으로 구하면 된다.

원소 삽입(insertAfter)

여기서부터 변형된 연결 리스트의 강점이 보일 것이다. 원소 삽입 옆을 보면 전에 만들었던 연산과는 다른 이름을 가졌다는 것을 알 수 있는데, 여기서 전에 만들었던 insertAt을 구현하기 전에 삽입할 전 위치(3번에 삽입하고자 한다면 2번 노드를 입력)를 가지고 데이터를 삽입하는 연산을 구현해 볼 것이다.

def insertAfter(self, prev, newNode):
    # prev 는 삽입할 위치의 전 노드
    # newNode 는 삽입할 노드
    newNode.next = prev.next
    if prev.next is None:
    	self.tail = newNode
    prev.next = newNode
    self.nodeCount+=1
    return True

과 같이 구현할 수 있다.
insertAt 연산도 방금 만든 insertAfter를 통해 보다 간단하게 구현할 수 있게 되는데 아래와 같이 구현할 수 있다.

def insertAt(self, pos, newNode):
    if pos < 1 or pos > self.nodeCount+1:
    	return False
    if pos!=1 and pos == self.nodeCount+1:
    	prev = self.tail
    else:
    	prev = self.getAt(pos-1)
    return self.insertAfter(prev, newNode)

과 같이 구현할 수 있다. 헤드에 더미 노드를 추가해줌으로써 고려해줄 경우의 수가 하나 줄었다고도 생각할 수 있다.
두번째 if문에서 1일때를 제외해준 이유는 빈 연결 리스트에서 1번 노드에 값을 추가하려하는 경우 self.tail에 아무런 노드가 할당되어 있지 않기 때문이다.

원소 삭제(popAfter)

원소 삭제의 경우에도 원래의 연결 리스트의 연산과 이름이 다른 것을 알 수 있다. 이 연산도 헤드에 더미 노드가 있기에 가능한 연산으로 삭제할 노드의 전 노드를 넣어 전 노드의 다음 노드(원하는 노드)를 삭제하게 하는 연산이다.
구현한 코드를 먼저 살펴보자면

def popAfter(self, prev):
    if prev.next is None:
    	return None
    curr = prev.next
    if curr.next is None:
    	self.tail = prev
    prev.next = curr.next
    self.nodeCount-=1
    return curr.data

과 같이 구현할 수 있게 된다. 코드를 보면 알 수 있듯이 헤더에 대한 예외 처리를 해줄 필요가 없어졌고, curr가 테일이어도 아니어도 prev.next = curr.next라고 지정해줄 수 있다는 것을 알 수 있다(curr가 테일이면 어차피 curr.next가 None이기 때문).
원소 삽입과 마찬가지로 이 연산을 이용해 popAt도 간단하게 구현할 수 있다.

def popAt(self, pos):
    if pos < 1 or pos > self.nodeCount:
    	raise IndexError
    prev = self.getAt(pos-1)
    return self.popAfter(prev)

위의 코드로 구현할 수 있게 되는데, 어차피 지우고자 하는 노드의 이전 노드를 찾아주므로 지우고자 하는 노드가 테일인지 아닌지는 중요하지 않게 되고, 인덱스 문제를 제외하고는 예외처리를 해 줄 필요가 없게 되어 코드가 간단해지는 것을 알 수 있다.

두 리스트 합치기

리스트 합치기는 원래의 연결 리스트와 매우매우 유사하다. 그러나 차이점이라고 한다면 앞서는 리스트의 테일의 다음 값을 뒷 리스트의 헤드로 하지 않고 뒷 리스트의 헤드의 다음 노드로 해야 한다는 차이가 있다(헤드는 더미 노드이기 때문). 테일 부분은 동일하고 nodeCount가 0일때의 처리도 동일하게 진행하면 된다.

Array List & Linked List

이렇게 단방향 연결 리스트(next만 사용해서 한 방향으로만 연결된 연결 리스트, 즉 지금까지 구현한 연결 리스트)에 대해 알아보았고 코드로 구현도 해보았다. 이번엔 배열(Array List)와 연결 리스트(Linked List)의 차이에 대해 알아보겠다. 전 포스트에서도 간단하게 배열과 연결 리스트의 차이를 표로 작성하긴 했지만 이번엔 효율 측면에서 살펴보도록 하겠다.

검색

배열과 연결 리스트 모두 어떤 값을 찾거나 순회하려면 첫번째 값부터 끝까지 모든 칸(셀)을 확인하므로 효율성이 같다.
이는 배열/연결 리스트의 길이에 비례하는 O(N)으로 표기할 수 있다.

삽입 / 삭제

요소를 삽입하고 삭제하는 과정은 그 작업을 진행하고자 하는 위치(인덱스)에 따라 달라지는데 우리는 첫번째 인덱스, 중간 인덱스(첫, 마지막 인덱스 제외), 마지막 인덱스로 구분해서 확인해보겠다.

1. 첫번째 인덱스(배열의 0, 연결 리스트의 1)

배열과 연결 리스트의 차이가 가장 극명하게 나는 부분으로, 결과 먼저 말하자면 배열은 O(N), 연결 리스트는 O(1)로 표기할 수 있다.
배열의 경우 맨 앞 인덱스에 값을 추가하면 원래의 위치에서 모두 한칸씩 뒤로(삭제의 경우 한칸씩 앞으로 당겨진다) 옮겨져야 하므로 배열의 길이만큼의 단계를 거쳐야 한다.
그러나 연결 리스트의 경우 배열처럼 값들이 연속되게 위치하지 않고 뒷 노드가 무엇인지의 정보만 담고있고 각자 독립적인 위치에 존재하므로, 첫번째 인덱스에 값을 추가하기 위해 추가하는 노드의 next 정보(삭제할 경우 헤드 정보만)와 연결 리스트의 헤드 정보만 수정해주면 1단계만으로 작업을 완료할 수 있다.

2. 중간 인덱스(맨 처음 / 맨 끝 X)

중간 인덱스의 경우엔 배열과 연결 리스트 모두 O(N)이다.
배열의 경우 추가(삭제)하고자 하는 인덱스에 접근하는 것은 바로(1단계로) 가능하지만 그 인덱스의 요소를 추가(삭제)하면 그 뒤 요소들을 뒤로(앞으로) 1칸씩 밀어야(당겨야) 하므로 배열의 길이에 비례해 O(N)이 된다.
연결 리스트의 경우 배열과는 반대의 이유로 O(N)이 되는데, 추가(삭제) 하는 과정은 next 정보를 통해(노드끼리의 연결 정보) 1단계로 작업을 완료할 수 있지만, 추가(삭제)하고자 하는 노드까지의 이동이 O(N)만큼 걸리기에 O(N)이게 된다.
즉 중간 인덱스의 요소를 추가(삭제)하는 작업의 효율은 배열과 연결 리스트가 비슷하다.

3. 마지막 인덱스

마지막 인덱스에 요소를 추가할때 배열은 상황에 따라 O(1)이 되거나 O(N)이 되고, 연결 리스트는 O(N)을 갖는다.
배열의 경우 만약 배열이 할당된 크기를 다 채우지 않은 경우 가장 마지막 인덱스(배열의 길이 활용)에 접근해 그 옆(다음)에 값을 추가하면 되므로 O(1)을 갖지만, 배열이 할당된 크기를 다 채워놓은 상태일 경우 배열의 위치를 재할당하고 모든 값을 복사하고 마지막에 추가하고자 하는 요소를 추가해야 하므로 O(N)이 된다. 그리고 값을 삭제할 경우에도 인덱스로 바로 접근해 삭제하면 되므로 O(1)을 갖는다.
연결 리스트의 경우 우리가 만든 단방향 연결 리스트에서는 마지막 노드의 전 노드를 가져와서 그 노드의 next 값을 수정해줘야 하기 때문에 마지막 노드의 전 노드까지 가는 과정이 O(N)이기에 O(N)이 된다. 그러나 다음에 다룰 양방향 연결 리스트를 사용하면 연결 리스트 테일의 전 노드를 찾아가면 되므로 O(1)로도 구현이 가능할 것이다.

예제 알고리즘 문제

연결 리스트에 대해 알아봤으니 이를 활용한 알고리즘 문제 하나를 살펴보도록 하겠다.

Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.

---

Example 1:

Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]

---

Example 2:
Input: l1 = [], l2 = []
Output: []

---

Example 3:
Input: l1 = [], l2 = [0]
Output: [0]

---

출처: LeetCode - 21. Merge Two Sorted Lists

문제를 읽어보면 연결 리스트를 잘 사용하면 간단하게 풀릴 것 같다는 생각이 들 것이다.

(아닌데...?)

한번 차근차근 살펴보자.

먼저 LeetCode에서 만들어놓은 연결 리스트의 형태를 살펴보자

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

연결 리스트의 형태를 살펴보면 self.val에 노드의 값이 들어가고 self.next에 다음 노드가 들어가는 형태인데, 잘 살펴보니 리스트이면서 노드인 형태(?)를 보인다.
즉, 노드(val: n, next: 노드(val: n, next: 노드(~~)))
와 같이 노드 안에 노드 안에 노드.... 같은 형태인 것이다.

이렇게 생긴 형태라고 생각할 수 있을 것이다.

이제 리스트들을 합치고 정렬하는 과정을 생각해보자.
필자는 연결 리스트의 키워드가 연결(Linked)이라고 생각해 노드들을 하나씩 살펴보며 노드들의 연결 관계를 재정의 해주면서 정렬하는 것이 좋겠다고 생각했다.
즉 결과값을 저장할 ListNode를 하나 만들고 입력값으로 들어온 두 ListNode의 헤드들의 값을 비교해 더 작은 헤드를 결과값에 추가해주고(연결) 그 헤드를 가지고 있던 연결 리스트에서 헤드를 제거하며 이 과정을 반복한다.
그러다가 둘 중 한 리스트(혹은 모두)가 비게 되면, 남은 리스트를 모두 결과를 담는 리스트에 추가해준다(입력으로 들어오는 리스트 2개가 모두 각각 정렬된 상태이기 때문).

그림을 참고하면 f라는 결과를 담는 리스트(노드)를 만들어주고 두 리스트의 헤드를 비교하면서 작은 값을 가진 헤드 노드를 결과 노드에 연결하고 그 리스트의 헤드를 제거한다. 그리고 다시 두 리스트의 헤드를 비교해가며 이 과정을 반복하는 것이다.
또한 LeetCode에서 제공하는 ListNode는 인스턴스 자체가 헤드이고 테일은 존재하지 않기 때문에 결과를 담는 ListNode의 가장 마지막 노드를 담는 임시 변수 last를 두어 결과 ListNode의 테일 정보를 담아두도록 하겠다.

이 모든 과정을 코드로 구현하면

class Solution:
    def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
    	if l1 is None:
            return l2
        if l2 is None:
            return l1
        result = ListNode() # default val = 0, next = None
        last = result # 결과 리스트에 노드가 하나뿐이기 때문
        
        # 둘 중 하나라도 비게 된다면 반복문 정지
        while l1 is not None and l2 is not None:
            if l1.val > l2.val:
            	# l1의 헤드가 l2보다 크면 둘을 바꾸어 l1으로만 작성하기 위함
            	l1, l2 = l2, l1
            last.next = l1 # 전 노드와 더 작은 헤드 노드를 연결
            last = l1 # 방금 연결한 노드가 무엇인지 기록
            l1 = l1.next # 헤드를 연결했으므로 리스트에서 헤드 제거
        # 둘 중 하나의 리스트가 비어(또는 둘 다) 반복문이 종료되었으므로
        # 아직 비지 않은 리스트가 있을 시 결과 리스트 뒤에 추가
        if l1 is not None:
            last.next = l1
        elif l2 is not None:
            last.next = l2
        # 결과 리스트의 첫번째 값은 빈 더미 노드이기 때문에 다음 값부터 반환
        return result.next
            

과 같이 구현할 수 있다.

구현한 알고리즘의 전반적인 로직은 위에서 설명했으므로 코드에 대한 자세한 설명은 주석으로 달아두도록 하겠다.