Singly-Linked List
singly-linked list 선언
class ListNode:
def __init__(self, val=None):
self.val = val
self.next = None- 위에서 선언한 단일 연결 리스트가 어떻게 연결되는지 확인해보자.
ListNode를 통해 단일 연결 리스트들을 생성한다.- 내용물을 눈으로 확인하기 위해
print_linked_list함수를 만들어 활용하였다.
class ListNode:
def __init__(self, val=None):
self.val = val
self.next = None
def print_linked_list(head):
current = head
while current is not None:
if current.next:
print(f"val: {current.val} / next: {current.next.val}", end=" -> ")
print()
else:
print(f"val: {current.val} / next: None")
current = current.next
# 단일 연결 리스트 생성 (100 -> 200 -> -> 300 -> 500)
head = ListNode(100)
head.next = ListNode(200)
head.next.next = ListNode(300)
head.next.next.next = ListNode(500)
# 위에서 생성한 단일 연결 리스트의 마지막에 요소 추가
node = head
while node:
if node.next is None:
node.next = ListNode(4)
break
node = node.next
# 위에서 생성한 단일 연결 리스트의 맨 처음에 요소 추가
node = ListNode(0)
node.next = head
head = node
print(print_linked_list(head))
>>> val: 0 / next: 100 ->
val: 100 / next: 200 ->
val: 200 / next: 300 ->
val: 300 / next: 500 ->
val: 500 / next: 4 ->
val: 4 / next: None
None- 위 코드를 통해 알 수 있듯이, 단일 연결 리스트에 요소를 추가하는 것은 굉장히 쉽다.
head를 통해 추가할 수도 있고, 맨 마지막 요소를 찾아 해당 요소 뒤에.next를 달아 추가할 수도 있다.- 자료의 양이 정해져 있지 않거나, 추가 혹은 삭제가 빈번하다면 우리가 자주 사용하는
list(배열)보다 효율적일 수 있다.- 연결리스트의 특징
- 동적 배열
- 삽입과 삭제가 쉽다.
- 스택(stack), 큐(queue) 등의 자료 구조를 만들 때 사용한다.
- 연결리스트의 특징
- 자료의 양이 정해져 있지 않거나, 추가 혹은 삭제가 빈번하다면 우리가 자주 사용하는
활용
class Node:
def __init__(self, val=None):
self.val = val
self.next = None
class LinkedList:
def __init__(self):
self.head = self
self.length = 0
def __len__(self):
return self.length
def __str__(self):
if not self.head:
return "no linked list"
else:
node = self.head
output = ""
while node.next: # 마지막 요소 전까지 프린트
output += f"{str(node.val)} -> "
node = node.next
output += str(node.val) # 맨 마지막 요소 프린트
return output
def append_head(self, val=None):
node = Node(val)
if not self.head:
self.head = node
else:
node.next = self.head
self.head = node
self.length += 1
def append_tail(self, val=None):
node = Node(val)
if not self.head:
self.head = node
else:
prev_node = self.head
while prev_node.next:
prev_node = prev_node.next
prev_node.next = node
self.length += 1
def search(self, target=None):
node = self.head
while node:
if node.val == target:
return "여기 있네 임마"
node = node.next
return "그런거 없어 임마"
def pop_head(self):
if not self.head:
return None
node = self.head
self.head = node.next
self.length -= 1
return node.val
def pop_tail(self):
if not self.head:
return None
node = self.head
if not node.next:
node = None
else:
while node.next:
prev = node
node = node.next
prev.next = None
self.length -= 1
return node.val
def insert_element(self, index, val):
if index <= 0:
self.append_head(val) # 길이를 증가시키는 코드가 포함됨
elif index >= self.length:
self.append_tail(val) # 길이를 증가시키는 코드가 포함됨
else:
prev_node = self.head
for _ in range(index-1):
prev_node = prev_node.next
node = Node(val)
node.next = prev_node.next
prev_node.next = node
self.length += 1
def remove_element(self, target=None):
if self.head.val == target:
self.pop_head()
return f"{target} 삭제 완료"
prev_node = self.head
while prev_node.next:
if prev_node.next.val == target:
prev_node.next = prev_node.next.next
self.length -= 1
return f"{target} 삭제 완료"
prev_node = prev_node.next
return "삭제할 요소 없음"
def reverse_element(self):
if self.length <= 1:
return "뒤바꿀 요소 없음"
prev = self.head
cur = prev.next
prev.next = None
while cur:
self.head = cur
cur = cur.next
self.head.next = prev
prev = self.head
# linked_list 생성
linked_list = LinkedList()
linked_list.append_head(0)
linked_list.append_head(1)
linked_list.append_tail(2)
linked_list.append_head(10)
linked_list.append_tail("fuck")
linked_list.append_tail("2")
linked_list.append_head("추가된 head")
linked_list.append_tail("추가된 tail")
print(f"생성된 linked_list의 총 길이 : {linked_list.__len__()}")
print("<linked_list>")
print(linked_list)
print()
# 요소 검색
print("[linked_list 안의 특정 요소 검색 결과]")
print(f"{linked_list.search('fuck')} -> fuck")
print(f"{linked_list.search(9)} -> 9")
print()
# linked_list의 head 및 tail 제거
print("[head 및 tail 제거]")
print(f"제거된 head : {linked_list.pop_head()}")
print(f"제거된 tail : {linked_list.pop_tail()}")
print(f"linked_list의 총 길이 : {linked_list.__len__()}")
print("<linked_list>")
print(linked_list)
print()
# linkde_list에 요소 추가 및 삭제
print("[linked_list에 요소 추가]")
linked_list.insert_element(2, "중간추가")
linked_list.insert_element(-2, "맨앞추가")
linked_list.insert_element(10, "맨뒤추가")
print(f"linked_list의 총 길이 : {linked_list.__len__()}")
print("<linked_list>")
print(linked_list)
print("[linked_list에 있는 요소 삭제]")
print(linked_list.remove_element("맨앞추가"))
print(linked_list.remove_element("중간추가"))
print(linked_list.remove_element("맨뒤추가"))
print(linked_list.remove_element("2"))
print(f"linked_list의 총 길이 : {linked_list.__len__()}")
print("<linked_list>")
print(linked_list)
print()
# linked_list의 요소 뒤집기
print("[linked_list 요소 뒤집기]")
linked_list.reverse_element()
print("<linked_list>")
print(linked_list)
>>> 생성된 linked_list의 총 길이 : 8
<linked_list>
추가된 head -> 10 -> 1 -> 0 -> 2 -> fuck -> 2 -> 추가된 tail
[linked_list 안의 특정 요소 검색 결과]
여기 있네 임마 -> fuck
그런거 없어 임마 -> 9
[head 및 tail 제거]
제거된 head : 추가된 head
제거된 tail : 추가된 tail
linked_list의 총 길이 : 6
<linked_list>
10 -> 1 -> 0 -> 2 -> fuck -> 2
[linked_list에 요소 추가]
linked_list의 총 길이 : 9
<linked_list>
맨앞추가 -> 10 -> 1 -> 중간추가 -> 0 -> 2 -> fuck -> 2 -> 맨뒤추가
[linked_list에 있는 요소 삭제]
맨앞추가 삭제 완료
중간추가 삭제 완료
맨뒤추가 삭제 완료
2 삭제 완료
linked_list의 총 길이 : 5
<linked_list>
10 -> 1 -> 0 -> 2 -> fuck
[linked_list 요소 뒤집기]
<linked_list>
fuck -> 2 -> 0 -> 1 -> 10실습
- 단일 연결 리스트는 리트코드의 문제들을 풀다가 좀 더 알아보게 되었다.
21. Merge Two Sorted Lists
Problems
두 개의 정렬된 연결 리스트인 list1과 list2의 헤드(head)가 주어집니다.
이 두 리스트를 하나의 정렬된 리스트로 병합해야 합니다. 새로운 리스트는 첫 번째 두 리스트의 노드를 연결하여 만들어져야 합니다.
병합된 연결 리스트의 헤드를 반환해야 합니다.
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
Input: list1 = [], list2 = []
Output: []
Input: list1 = [], list2 = [0]
Output: [0]Idea
- 맨 처음 예제를 보면 두 개의 단일 연결 리스트를 연결하면서 안의 요소들을 크기에 따라 소팅한 것을 볼 수 있다. 따라서 두 개의 연결 리스트를 비교해가면서 작은 요소가 앞으로 가도록 Output을 생성하였다.
- 두 개의 리스트가 들어오지만 각 리스트이 길이는 다르다. 따라서
while문을 통해 두 개의 리스트가 모두 존재할 때 Output에 각 요소들을 넣어준다. 그리고 남은 요소를 next에 붙여주었다.
Code
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
cur = dummy = ListNode() # val = 0, next = None
while list1 and list2:
# 작은 것이 앞으로 갈 수 있도록 작은 값이 next에 붙는다.
if list1.val < list2.val:
# 작은 값이 cur의 next가 된다.
cur.next = list1
# list1이 현재 가장 작은 값이 되며, list1에는 list1.next가 붙는다.
list1, cur = list1.next, list1
else:
cur.next = list2
list2, cur = list2.next, list2
# while 문이 끝난 후 남아있는 요소가 있다면 추가해준다.
if list1 or list2:
cur.next = list1 if list1 else list2
return dummy.next83. Remove Duplicates from Sorted List
83. Remove Duplicates from Sorted List
Problems
정렬된 연결 리스트의 헤드(head)가 주어집니다.
이 연결 리스트에서 중복된 요소를 모두 제거해야 합니다. 각 요소는 한 번만 나타나도록 해야 합니다. 제거된 후의 연결 리스트는 여전히 정렬된 상태여야 합니다.
정렬된 연결 리스트를 반환해야 합니다.
Idea
- 해당 문제가 위에서 확인했던 단일 연결 리스트의 정의와 제일 비슷하다고 본다.
- 따라서 각 노드의 next를 선언해주었던 것처럼, 만약 중복되는 노드가 존재한다면 해당 노드를 건너뛰고 그 다음 노드를 cur의 next에 연결해주었다.
Code
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head:
cur = head
# head의 맨 마지막 노드의 next는 None이다. 따라서 None이 아닌 경우를 확인해주면 된다.
while cur.next:
# 현재 보고 있는 노드인 cur의 값과 다음 노드의 값을 비교한다.
if cur.val == cur.next.val:
# 만약 값이 같다면 다음다음 노드를 현재 cur의 next에 연결해준다.
cur.next = cur.next.next
else:
cur = cur.next
return head
# 아예 head가 빈 단일 연결 리스트인 경우를 커버한다.
return None
https://github.com/nikevapormax