이번에 쓸 내용은 연결리스트라는 녀석인데 정말 나를 많이 괴롭힌 녀석 중 하나이다. 이해도 힘들고 지금도 내가 이해를 하고 있는지 조차 모르는 녀석이다.

-연결리스트는 데이터 요소의 선형 집합으로, 데이터의 순서가 메모리에 물리적인 순서대로 저장되지 않는다.

※ 연결 리스트는 컴퓨터과학에서 배열과 함께 가장 기본이 되는 대표적인 선형자료구조 중 하나로 다양한 추상 자료형 구현의 기반이 된다.
동적으로 새로운 노드(Nond)를 삽입하거나 삭제하기가 간편하며, 연결 구조를 통해 물리 메모리를 연속적으로 사용하지 않아도 되기 때문에 관리도 쉽다. 또한 데이터를 구조체로 묶어서 포인터로 연결한다는 개념은 여러가지 방법으로 다양하게 활용이 가능하다. 실제로 컴퓨터의 물리 메모리에는 구조체 각각이 서로 연결된 형태로 구성되어 있으며, 메모리 어딘가에 여기저기 흩뿌려진 형상을 띤다.

＊ 연결리스트는 배열과는 달리 특정 인덱스에 접근하기 위해서는 전체를 순서대로 읽어야 하므로 상수 시간에 접근할 수 없다. 즉 탐색에는 O(n)이 소요된다. 반면, 시작 또는 끝 지점에 아이템을 추가하거나 삭제, 추출하는 작업은 O(1)에 가능하다.

연결리스트의 종류

• 모든 리스트의 코드를 구현하지는 않는다!

Singly linked list (일방향 연결 리스트)

일방향 연결 리스트는 노드에 포인터(다음 노드를 가리키는 링크)가 한 개인 연결 리스트인데요, 이 리스트의 장점은 노드당 포인터 데이터를 4 바이트만 차지해서 이중 연결 리스트보다 데이터를 아낄 수 있다는 점입니다. 다만 일방향이기 때문에 현재 노드는 이전 노드로 돌아가는 법을 모릅니다. 오직 직진만이 있을 뿐.

Doubly linked list (이중 연결 리스트)

노드에 포인터가 두 개 있는 이중 연결 리스트인데요, 일방향 연결 리스트와 똑같지만 앞서 말한 것처럼 노드에 포인터가 두 개 있다는 점이 다른데요, 이 두 개의 포인터는 전과 후를 가리키고 있기 때문에 일방향과는 달리 이전으로 갈 수도, 이후로도 갈 수도 있습니다. 포인터가 두 개가 생겼으니 데이터도 두 배로 먹겠죠. 8 바이트를 차지합니다.

Circular linked list (환형 연결 리스트)

연결 리스트에 있는 헤드와 테일이 붙여져 있어, 원의 모양과 같다고 하여 환형 리스트인데요. 테일의 포인터가 null을 가리키고 있는 것이 아닌 head를 가리키고 있는 것입니다. 노드 6 번에 있다가 4 번으로 가야 된다면, 일방향 리스트는 다시 시작해야 되지만 환형 리스트는 7, 8, 9, 10을 지나 다시 0, 1, 2, 3, 4로 갈 수 있겠죠? 순회할 때 좋은 연결 리스트입니다.

연결 리스트의 method

＊ 어디서든 추가와 삭제가 가능하지만 끝에만 추가하는 것으로 구현해 봅니다.

• addToTail(value): 연결 리스트의 마지막에 데이터를 추가합니다.

• getNodeAt(index): 인덱스를 넣었을 때, 그 인덱스가 어떠한 값을 가지고 있는지 반환합니다.

• contains(value): 해당 값이 연결 리스트에 있는지 true와 false로 반환합니다.

• indexOf(value): 해당 값이 어떤 인덱스에 있는지, 인덱스 값과 -1로 반환합니다.

• remove(value): 해당하는 연결 리스트의 값을 지웁니다.

• size(): 연결 리스트의 사이즈를 반환합니다.

-이제 연결리스트에 대한 문제를 풀어보도록 하죠 ~.

1. 팰린드롬 연결 리스트 (leetcode: 234. Palindrome Linked List)

: 연결리스트가 팰린드롬 구조인지 판별하라.

-입력
: 1 -> 2
-출력
: false

---

-입력
: 1 -> 2 -> 2 -> 1
-출력
: true

★ 이 문제에 대한 풀이는 <리스트로 변환해서 풀이하는 방법>과 <데크를 이용해서 리스트보다 가속성을 늘려주는 풀이법> 2가지를 설명해보려 한다.

< 리스트 변환 풀이>

# class ListNode:
#     def __init__(self, val):
#         self.val = val
#         self.next = None
# 
# class LinkedList:
#     def __init__(self):
#         init = ListNode(1)
#         self.head = init
#         self.tail = init
# 
#         self.현재노드 = None
#         self.데이터수 = 0
# 
#     def append(self, data):
#         NewNode = ListNode(data)
#         self.tail.next = NewNode
#         self.tail = NewNode
#         self.데이터수 += 1

def isPalindrome(head: ListNode) -> bool:
    q = [] # 노드를 담을 그릇(리스트)

    if not head: # head 값이 존재하지 않아도 팰린드롬으로 간주한다.
        return True

    node = head
    # 리스트 변환
    while node is not None: # 노드가 없을 때까지 반복
        q.append(node.val)
        node = node.next # 계속 노드를 다음으로 이동시킨다.

    # 팰린드롬 판별
    while len(q) > 1:
        if q.pop(0) != q.pop():
            return False
    return True

＃.문자열 조작에서 다룬 팰린드롬 문제랑 다른 부분은 ListNode를 리스트에 담는 부분 뿐이다.

< 데크를 이용한 최적화 >

# class ListNode:
#     def __init__(self, val):
#         self.val = val
#         self.next = None
# 
# class LinkedList:
#     def __init__(self):
#         init = ListNode(1)
#         self.head = init
#         self.tail = init
# 
#         self.현재노드 = None
#         self.데이터수 = 0
# 
#     def append(self, data):
#         NewNode = ListNode(data)
#         self.tail.next = NewNode
#         self.tail = NewNode
#         self.데이터수 += 1

import collections
from typing import Deque

def isPalindrome(head: ListNode) -> bool:
    q: Deque = collections.deque()

    if not head:
        return True

    node = head
    # 리스트 변환
    while node is not None:
        q.append(node.val)
        node = node.next

    # 팰린드롬 판별
    while len(q) > 1:
        if q.popleft() != q.pop():
            return False
    return True

＃.데크를 이용한 풀이 방법은 위에 리스트 변환 풀이 방법과 비슷하지만 앞서 문자열 조작에서도 말했지만 데크가 먼저 들어온 데이터를 뽑는 속도는 리스트보다 빠르기 때문에 이러한 방식으로 풀 땐 데크를 이용한 방식이 더 용이하다고 할 수 있다.