해당 시리즈는 [ 파이썬 알고리즘 인터뷰 ] 를 통해 학습한 내용을 정리한 글입니다.
연결리스트는 배열과 함께 사용되는 기본적인 선형 자료구조이다.
장점
- 동적으로 새로운 노드를 삽입하거나 삭제하기가 간편하다.
- 연결 구조를 통해 물리 메모리를 연속적으로 사용하지 않아도 된다.
- 데이터를 구조체로 묶어서 포인터로 연결하기때문에 여러가지 방법으로 활용 가능하다.
컴퓨터 물리 메모리에는 구조체 각각이 서로 연결된 형태로 구성되어 있고, 메모리 어딘가에 여기저기 흩뿌려진 형상을 띤다.
⭐ 연결리스트는 배열과 달리 특정 인덱스를 접근하려면 전체를 순서대로 읽어야한다.
따라서 상수 시간에 접근할 수 없다.
⭐ 탐색 : O(n),
⭐ 시작과 끝 지점에 아이템을 추가, 삭제, 추출 : O(1)
역순 연결 리스트
https://leetcode.com/problems/reverse-linked-list/
연결 리스트를 뒤집어라
[ 재귀 구조 ]
- 현재 노드 node와 다음 노드 next를 파라미터로 지정한 함수를 계속해서 호출해준다.
- node.next를 이전 prev 노드로 연결한다.
- 현재 노드 node가 None이 될 때까지 호출을 하면 거꾸로 연결된다.
#재귀 구조
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
def reverse(node: ListNode, prev:ListNode = None):
if not node:
return prev
next,node.next = node.next, prev
return reverse(next,node)
return reverse(head)[ 반복구조 ]
- node.next 이전 prev 노드로 계속 연결한다.
#반복 구조
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
#현재 노드 = head, 이전 노드 = none
node,prev=head,None
while(node):
#다음 노드 = 현재 노드의 다음 노드 / 현재노드.next = 이전 노드
#이전 노드 = 현재 노드 / 현재 노드 = 다음 노드
next,node.next = node.next,prev
prev, node = node, next
return prev➢ 둘다 비슷한 속도를 보이기때문에 어느 방식으로 풀어도 큰 문제는 없다.
다만 반복이 재귀보다 조금 더 적은 메모리를 차지해 공간 복잡도가 더 낮고, 실행 속도도 조금 더 빠르다.
두 수의 덧셈
https://leetcode.com/problems/add-two-numbers/
역순으로 저장된 연결 리스트의 숫자를 더하라
[연결리스트 사용]
#자료형 반환
#연결리스트->문자열->숫자->연결리스트
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)
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(str(e) for e in a)) + int(''.join(str(e) for e in b))
#최종 계산 결과를 연결리스트로 변환
return self.toReversedLinkedList(str(resultStr))[전가산기 사용]
⭐ 자료형을 변환하여 자리수별로 더하는 문제가 있을 때
전가산기 구조를 이용한 방법으로 문제를 풀면 더 빠르게 풀 수 있다.
논리회로의 전가산기와 비슷한 형태로 구현을 해보자
자리 수 별로 계산을 하고, 자리 올림수도 구할 수 있다.
입력값 A,B, 이전의 자리올림수 Cin 을 입력값으로, Sum과 다음 자리 올림수 Cout을 결정한다.
이 문제에서는 연산 결과로 나머지를 취하고,
몫은 자리 올림수로 올리는 전가산기의 전체적인 구조만 참고해 풀이해보자.
두 입력값의 합을 구하는 코드이다.
l1, l2는 A,B와 같은 역할이다.
sum = 0
if l1:
sum += l1.val
l1 = l1.next
if l2:
sum += l2.val
l2 = l2.next두 입력값의 연산을 수행했으니, 다음과 같이 자릿수가 넘어갈 때 자리 올림수를 선정하자
⭐ 가산 결과가 두 자릿수가 되면 몫은 자리올림수로, 나머지는 연산값으로 취한다.
carry, val = divmod(sum + carry, 10)-
divmod는 몫과 나머지를 반환하는 함수이다.
divmod(a,b)는 a//b , a%b 와 같다.
#전가산기 구조이용
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution():
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> 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