연결리스트
연결 리스트란?
- Node : 데이터와 다음 데이터를 가리키는 주소(포인터)로 이루어져 있다.
- Pointer : 각 노드에서 다음 데이터를 가리키는 주소값을 가진다.
- Head : 링크드리스트에서 가장 시작점인 데이터를 의미한다.
- Tail : 링크드리스트에서 가장 마지막 데이터를 의미
- Next=None(또는 Null) : 다음 데이터가 없을 경우 포인터의 주소값은 None(또는 Null)이다
연결 리스트 장단점
- 장점
- 배열은 미리 데이터 공간을 할당해야 하지만 링크드리스트는 미리 할당할 필요가 없다.
- 링크드리스트 수정시 시간복잡도 O(1)을 갖는다.
- 단점
- 위 구조에서 보듯이 다음 데이터를 연결하기 위해선 별도의 주소 공간을 가져야 한다. -> 저장공간 효율이 높지 않음
- 배열은 인덱스를 통해 데이터에 접근하므로 시간복잡도 O(1)을 갖지만 링크드리스트의 경우 O(n)을 갖는다. 즉, 연결 된 정보를 찾기 위해 주소를 확인하고 다음 데이터를 탐색하는 시간이 있기 때문에 접근 속도가 느리다.
- 중간데이터를 삭제시, 앞뒤 데이터를 연결하고 재구성하는 코드가 추가로 필요하다.
Question 13: 팰린드롬 연결 리스트
입력: 1->2->1
출력: true
풀이 1: 리스트 변환
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
q: List = []
if not head:
return
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
중요 내용
- 연결 리스트를 리스트로 변환한 후 pop함수를 사용하여 팰린드롬 여부를 판별하였다.
- 리스트로 변환하고 여기서 팰린드롬 여부를 판별하므로 실행 시간이 오래 걸린다.
- 연결 리스트를 리스트로 변환하는 알고리즘을 잘 기억해 놓자!!
풀이 2: 데크를 이용한 최적화
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
q: Deque = collections.deque()
if not head:
return
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
중요 내용
- 일반 리스트로 풀이하면 pop(0)으로 첫번째 아이템을 가져올때 모든 값이 한 칸씩 시프팅되어 시간 복잡도가 O(n) 만큼 발생한다. 반면 popleft() 함수를 사용하면 시간 복잡도가 O(1) 만큼 발생한다.
- 리스트를 데크형으로 변경하는 방법은 다음과 같은 한 줄이므로 매우 간단하므로 꼭 기억하자!
q: Deque = collections.deque()
풀이 3: 런너를 이용한 풀이
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
rev = None
slow = fast = head
# 런너를 이용해 역순 리스트 구현
while fast and fast.next:
fast = fast.next.next
rev, rev.next, slow = slow, rev, slow.next
# 입력값이 홀수 일때 실행 됨
if fast:
slow = slow.next
# 팰린드롬 여부 확인
while rev and rev.val == slow.val:
slow, rev = slow.next, rev.next
return not rev
중요 내용
- 이 방법은 이전의 방법과는 달리 연결 리스트의 특징을 살린 풀이 방법이다.
- 여기서는 런너 기법 과 다중 할당 이 사용 되었다.
- 런너 기법: 빠른 런너는 두 칸씩 건너뛰고 느린 런너는 한 칸씩 건너뛴다. 빠른 런너가 연결 리스트에 끝에 도달하면 느린 런너는 연결 리스트의 중간 지점에 도달하는 방법을 이용한다.
- 다중 할당: 파이썬의 숫자는 불변 객체이기 때문에 다른 언어와는 다르게 다중 할당을 구현할 수 있다. 연결 리스트를 역순하는 알고리즘은 자주 사용되므로 꼭 숙지하자!
rev, rev.next, head = head, rev, head.next
Question 14: 두 리스트의 병합
입력: 1->2->4, 1->3->4
출력: 1->1->2->3->4->4
내 풀이
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
# 두 리스트가 None일 경우 빈 값 리턴
if (list1 or list2) is None:
return
# 연결리스트를 리스트로 만든 후 정렬
q: List = []
while list1 is not None:
q.append(list1.val)
list1 = list1.next
while list2 is not None:
q.append(list2.val)
list2 = list2.next
q.sort()
# 리스트를 연결리스트로 변경
result_node = ListNode()
for i,num in enumerate(q):
if i == 0 :
result_node.val = num
else :
node = result_node
while node.next != None:
node = node.next
node.next = ListNode(num)
return result_node
결과
Runtime: 52 ms, faster than 33.77% of Python3 online submissions for Merge Two Sorted Lists. Memory Usage: 14.3 MB, less than 62.12% of Python3 online submissions for Merge Two Sorted Lists.
- 리스트를 연결 리스트로 변경하는 코드는 내 코드가 아니다. 해당 알고리즘은 자주 사용될거 같으므로 잘 기억해 놓자!
풀이 1: 재귀 구조로 연결
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
if (not list1) or (list2 and list1.val > list2.val):
list1, list2 = list2, list1
if list1:
list1.next = self.mergeTwoLists(list1.next, list2)
return list1
중요 내용
- 이 풀이방법은 재귀적 구조를 이용하였다. list1과 list2의 첫번째 값부터 비교하면서 list1의 값이 더 크면 값을 서로 스와핑을 하고 list1이 None이 아닐때 다음 값으로 넘어간다.
- list1의 마지막에서의 처리는 다음과 같다: list1.next는 None이 되고 이것이 not list1이 True가 되면서 값이 스와핑 되어 list1의 마지막 값은 결국 4가 된다.
- 파이썬에서의 변수 스와핑은 자주 쓰이는 구문이므로 반드시 기억하자!
- self는 자기 인스턴스를 가리킨다.
a,b = b,a
Question 15: 역순 연결 리스트
입력: 1->2->4->5
출력: 5->4->2->1
내 풀이
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head:
return
rev = None
while head:
rev, rev.next, head = head, rev, head.next
return rev
결과
Runtime: 36 ms, faster than 78.18% of Python3 online submissions for Reverse Linked List. Memory Usage: 15.6 MB, less than 47.36% of Python3 online submissions for Reverse Linked List.
- 이전에 사용하였던 역순 알고리즘을 그대로 이용하였다.
풀이 1: 재귀 구조로 연결
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
def reverse(node:ListNode, prev:ListNode = None):
if node is None:
return prev
next, node.next = node.next, prev
return reverse(next, node)
return reverse(head)
중요 내용
- 최대한 어렵지 않고 단순하게 생각하려고 하자!
- 연결리스트는 사실상 next만이 사용할 수 있는 문법의 전부이기 때문에 구조가 이해가 가지 않을 때는 머리속으로 진행과정을 그리면서 따라가보자.
- 다음 그림과 같은 순서로 변수가 변경된다.
—
풀이 2: 반복 구조로 뒤집기
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
node, prev = head, None
while node:
next, node.next = node.next, prev
prev, node = node, next
return prev
중요 내용
- 재귀 구조와 구조는 큰 차이가 없다.
Question 16: 두 수의 덧셈
역순으로 저장된 연결 리스트의 숫자를 더하라
입력: (2 -> 4 -> 3) + (5 -> 6 -> 4)
출력: 7 -> 0 -> 8
내 풀이
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
if (l1 or l2) is None:
return
def ll2list(ll1: Optional[ListNode]):
q: List = []
while ll1 is not None:
q.append(ll1.val)
ll1=ll1.next
return q
def revLl(ll2: Optional[ListNode]):
rev = None
while ll2:
rev, rev.next, ll2 = ll2, rev, ll2.next
return rev
def list2ll(l3: List[int]):
result_node = ListNode()
for i,num in enumerate(l3):
if i == 0:
result_node.val = num
else:
node = result_node
while node.next != None:
node = node.next
node.next = ListNode(num)
return result_node
def list2int(l4: List[int]):
num_str = ''
for num in l4:
num_str += str(num)
return int(num_str)
def int2ll(integer):
return list2ll([i for i in str(integer)])
return revLl(int2ll(list2int(ll2list(revLl(l1)))+ list2int(ll2list(revLl(l2)))))
결과
Runtime: 127 ms, faster than 11.04% of Python3 online submissions for Add Two Numbers. Memory Usage: 14 MB, less than 99.82% of Python3 online submissions for Add Two Numbers.
- 다음과 같은 순서로 실행된다.
- 연결 리스트를 뒤집음
- 연결 리스트를 리스트로 변환
- 리스트를 정수형으로 변환한 뒤 두 정수를 더함
- 더한 정수 값을 리스트로 변환한 뒤 연결 리스트로 변환
-
연결 리스트를 뒤집음
풀이 1: 재귀 구조로 연결
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
node, prev = head, None
while node:
next, node.next = node.next, prev
prev, node = node, next
return prev
# 연결 리스트를 파이썬 리스트로 변환
def toList(self, node: ListNode) -> List:
list: List = []
while node:
list.append(node.val)
node = node.next
return list
# 파이썬 리스트를 연결 리스트로 변환
def toReversedLinkedList(self, result: str) -> ListNode:
prev: ListNode = None
for r in result:
node = ListNode(r)
node.next = prev
prev = node
return node
# 두 연결 리스트의 덧셈
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
a = self.toList(self.reverseList(l1))
b = self.toList(self.reverseList(l2))
resultStr = int(''.join(map(str,a))) + \
int(''.join(map(str,b)))
# 최종 계산 결과 연결 리스트 변환
return self.toReversedLinkedList(str(resultStr))
기억해야 할 함수
- map(function ,iterable): 함수를 반복 가능한 자료형(리스트, 튜플)에 적용한다. 반환은 함수가 적용된 반복 가능한 자료형이다.
- functools.reduce(function, iterable): 반복 가능한 자료형에 함수를 누계 적용한다.
예시: functools.reduce(lambda x,y: x+y, [1,2,3,4,5]): ((((1+2)+3)+4)+5) = 15
중요 내용
- 여기서는 내가 푼 방법과 비슷하나 풀이 방법은 더 간소화 하였다.
-
함수 이름 또한 더 직관적이다. 함수 이름을 변경되는 자료형을 기준으로 만들도록 하자.
풀이 2: 전가산기 구현
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
root = head = ListNode(0)
carry = 0
while l1 or l2 or carry:
sum = 0
# 두 입력값의 합 계산
if l1:
sum += l1.val
l1 = l1.next
if l2:
sum += l2.val
l2 = l2.next
# 가산 결과가 두 자리수가 될 경우 몫은 다음번 연산에 사용된다.
carry, val = divmod(sum + carry, 10)
head.next = ListNode(val)
head = head.next
return root.next
중요 내용
- 이 풀이는 CPU를 구성하는 회로의 작동 원리인 연산 결과의 나머지만 취하고 몫은 자리 올림수 형태로 올리는 전가산기를 응용한 풀이 방법이다.
- 연결 리스트의 값을 삽입하기 위해서는 ListNode() 함수를 사용한다.
- 변수에 다른 연결 리스트를 정의하고 그 연결 리스트에 노드를 추가하거나 정의하면 해당 변수에도 그 변화가 적용된다. 단, 그 변수의 노드의 위치는 바뀌지 않는다.
Question 17: 페어의 노드 스왑
연결 리스트를 받아 페어로 스왑하라
입력: 1->2->4->5
출력: 2->1->5->4
내 풀이
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head:
return
step = 1
rev = None
root = node = ListNode(0)
while head:
rev, rev.next, head = head, rev, head.next
if step % 2 == 0:
node.next = rev
node = node.next.next
rev = None
elif head == None:
node.next = rev
step += 1
if step == 2:
return rev
else:
return root.next
결과
Runtime: 59 ms, faster than 9.89% of Python3 online submissions for Swap Nodes in Pairs. Memory Usage: 13.9 MB, less than 98.81% of Python3 online submissions for Swap Nodes in Pairs.
- 이전에 사용하였던 역순 알고리즘을 그대로 이용하였다.
- 전가산기 구현 때 사용하였던 root = head = ListNode(0) 알고리즘을 그대로 사용하였다.
풀이 1: 값만 변경
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
cur = head
while cur and cur.next:
cur.val, cur.next.val = cur.next.val, cur.val
cur = cur.next.next
return head
중요 내용
- 연결 리스트의 구조는 그대로 유지하되 값만 서로 스와핑하는 방법이다.
- 그러나 변칙적인 풀이 방법이므로 최대한 지양해야한다.
풀이 2: 반복 구조로 스왑
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
root = prev = ListNode(None)
prev.next = head
while head and head.next:
# b가 a(head)를 가리키도록
b = head.next
head.next = b.next
b.next = head
# prev가 b를 가리키도록
prev.next = b
# 다음 번 비교를 위해 이동
head = head.next
prev = prev.next.next
return root.next
중요 내용
- b가 a, a가 b의 다음을 가리키도록 변경한다.
- 연결리스트의 구조를 변경할때는 노드가 다음노드를 가리키도록, 이전노드가 노드를 가리키도록 설정하는 것이 중요하다.
풀이 3: 재귀 구조로 스왑
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head and head.next:
p = head.next
head.next = self.swapPairs(p.next)
p.next = head
return p
return head
중요 내용
- 연결리스트에서 재귀구조는 끝나는 값이 none일때가 나올 때 어떻게 처리할지를 설정하는 것이 가장 중요하다.
Question 18: 홀짝 연결 리스트 (재풀이)
연결 리스트를 홀수 노드 다음에 짝수 노드가 오도록 재구성하라.
입력: 1->2->3->4->5
출력: 1->3->5->2->4
풀이 1: 반복 구조로 홀짝 노드 처리
class Solution:
def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head:
return
odd = head
even = head.next
even_start = head.next
while even and even.next:
odd.next, even.next = odd.next.next, even.next.next
odd, even = odd.next, even.next
odd.next = even_start
return head
중요 내용
- 홀수, 짝수 변수에 입력 연결 리스트를 부여한 후에 2칸씩 이동하며 연결 리스트를 만든다. 그리고 처음에 정의한 짝수 시작 노드를 홀수 연결 리스트에 연결한 후에 결과를 리턴한다.
- even_start를 head.next로 지정하는 것만으로 odd.next = even_start 를 했을때 연결 리스트가 서로 이어지는 것이 이해가 잘 가지 않았다.
Question 19: 역순 연결 리스트 (재풀이)
인덱스 m에서 n까지를 역순으로 만들어라. 인덱스 m은 1부터 시작한다.
입력: 1->2->3->4->5->NULL, m=2, n=4
출력: 1->4->3->2->5->NULL
풀이 1: 반복 구조로 노드 뒤집기
class Solution:
def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
if not head or left == right:
return head
root = start = ListNode(None)
root.next = head
for _ in range(left-1):
start = start.next
end = start.next
for _ in range(right - left):
tmp, start.next, end.next = start.next, end.next, end.next.next
start.next.next = tmp
return root.next
중요 내용
-
처음에 root와 start의 시작노드를 None 으로 지정하고 head를 root와 이어주는 이유는 for 문을 돌 때 left-1 만큼 돌기 위해서이다. 만약 root를 지정하지 않는다면 left-2만큼 반복문을 돌아야 하는데 그렇게 되면 left = 1 일때 해당하는 답을 구하기 위해 조건문을 다시 세워야 하므로 더 번거로워진다.
-
start와 end를 통해 역순 연결 리스트를 만드는 과정은 책 238쪽 그림에 자세하게 나타나있다.
Comments