링크드리스트란?

• Linked List란, 파이썬의 기본 리스트(array)의 사촌지간입니다.
• 리스트 내부에 있는 value 들을 조회하고, 새로운 value를 삭제하고, 삽입할 수 있게 해줍니다.
• 그러나, head와 data(value), next의 개념을 추가하여 array와의 장단이 있습니다.

조회

특정 노드의 인덱스를 바탕으로 값을 조회하는 것에는 어레이가 좋습니다.

array: O(1)

• arr[3] 등으로 특정 인덱스의 값을 바로 확인할 수 있습니다.

linkedlist: O(n)

• head를 기점으로 하나씩 next로 넘어가며, 해당하는 값을 조회해야 하기에 O(n)의 시간 복잡도를 가집니다.

삽입 및 삭제

• 리스트(array)의 경우 삽입할 때, 하나씩 다 옮기고 나서 칸을 비우고 해당 칸에 넣어야합니다.
• 그러나 링크드 리스트는 삽입할 때 화살표만 옮기면 끝입니다.

어레이는 O(n), 링크드리스트는 O(1)

• 데이터 추가의 경우 array의 경우 모든 공간이 다 차버렸다면 새로운 메모리 공간을 할당 받아야합니다.
  그러나 링크드의 경우 모든 공간이 다 찼어도 맨 뒤의 노드만 동적으로 추가하면 됩니다.

요약

array

• 파이썬의 리스트, 접근 쉬움, 삽입 어려움

연결 리스트

• 파이썬 내장으로 구현이 되어 있지 않기에 직접 구현을 해야함.
• 접근이 어렵지만, 삽입이 쉬움

정리

• 데이터에 접근하는 경우가 빈번하다면 Array
• 삽입과 삭제가 빈번하다면 LinkedList를 사용하면 됩니다.

구현

linked_list.py

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, val):
        # 헤드가 없을 때
        if not self.head:
            # 헤드로 지정
            self.head = ListNode(val, None)
            return

        # node를 head로 설정한 다음, next가 없을 때까지 계속 node를 한 칸씩 이동 시킴
        node = self.head
        while node.next:
            node = node.next
        # next가 없는 마지막 노드에 도착했다면, 마지막 노드의 next를 ListNode로 지정하여, 새로운 마지막 노드를 추가함
        node.next = ListNode(val, None)
# ln = LinkedList()
# ln.append(3)
# ln.append(5)
# ln.append(7)
#
# print(ln)

간단 예제: 팰린드롬 연결 리스트

• 팰린드롬이란? 거꾸로 읽어도 똑같은 문자열을 의미합니다. 예를 들어 pap, paap등이 팰린드롬입니다.
• 링크드리스트를 이용하여 팰린드롬인지 확인하는 코드를 작성해보겠습니다.

test.py

• 테스트 코드입니다.

from linked_list import LinkedList
from prac import isPalindrome

l1 = LinkedList()
for num in [1, 2, 2, 1]:
    l1.append(num)

l2 = LinkedList()
for num in [1, 2]:
    l2.append(num)


# testcase
# assert는 기본값이 true
assert isPalindrome(l1)
assert not isPalindrome(l2)

• assert를 이용해서 테스트 케이스 2가지를 만들었습니다.

prac.py

# 팰린드롬 연결 리스트: 주어진 리스트가 팰린드롬인지 판별하는 프로그램을 작성하세요.
def isPalindrome(ln):
    arr = []
    head = ln.head

    if not head:
        return True
    # head가 없다면, list 안에 없는 것이기때문에 True를 바로 반환합니다.

    node = head
    # 링크드 리스트를 구현합니다.
    while node:
        arr.append(node.val)
        node = node.next

	# pop을 이용하여, arr 안에 아무런 값이 남지 않을 때까지 맨 앞과 뒤에서 하나씩 빼며 팰린드롬 여부를 판정합니다.
    while len(arr) > 1:
        first = arr.pop(0)
        last = arr.pop()
        if first != last:
            return False

    return True