Linked List
# [3] -> [4]
# node 안에는 data, next로 구성
class Node:
def __init__(self, data):
self.data = data
self.next = None # 다음 포인터를 가리키지 않기 때문
node = Node(3)
print(node) # <__main__.Node object at 0x000001207C448BE0>
print(node.data) # 3[3]이 있는 칸(노드)을 구현
# [3] -> [4]
# node 안에는 data, next로 구성
class Node:
def __init__(self, data):
self.data = data
self.next = None # 다음 포인터를 가리키지 않기 때문
node = Node(3)
print(node) # <__main__.Node object at 0x000001207C448BE0>
print(node.data) # 3
first_node = Node(4)
node.next = first_node
print(node.next.data) # 4[4]가 있는 칸(노드)을 만들고 next로 연결. 이런 식으로 쭉쭉 이어나갈 수도 있지만 만약 데이터가 1억개라면? 일일이 next로 연결 해줘야하는 번거로움에 손가락과 손목이 부서질수도😱💀
그래서 아래의 코드처럼 head를 생성해준 것이다.
# [3] -> [4]
# node 안에는 data, next로 구성
class Node:
def __init__(self, data):
self.data = data
self.next = None # 다음 포인터를 가리키지 않기 때문
node = Node(3)
print(node) # <__main__.Node object at 0x000001207C448BE0>
print(node.data) # 3
first_node = Node(4)
node.next = first_node
print(node.next.data) # 4
class LinkedList:
def __init__(self, data):
self.head = Node(data)
linked_list = LinkedList(3)
print(linked_list) # <__main__.LinkedList object at 0x000001207C5F8DF0>
print(linked_list.head) # Node(data) 이렇게 정의 해 놨으니까 , <__main__.Node object at 0x000001207C5F8A90> 값이 나오게 된다.
print(linked_list.head.data) # 3
print(linked_list.head.data.next) # None // 아직 next를 지정해놓지 않아서 처음 Node class에서 정의한 none이 나오게 된다.
head를 생성해서 [3]칸(노드)을 만들어줌. 이제 여기서 .append 함수를 클래스에 정의하여 뒷 칸(노드)들을 쭉 연결 할 것이다.
# [3] -> [4]
# node 안에는 data, next로 구성
class Node:
def __init__(self, data):
self.data = data
self.next = None # 다음 포인터를 가리키지 않기 때문
node = Node(3)
print(node) # <__main__.Node object at 0x000001207C448BE0>
print(node.data) # 3
first_node = Node(4)
node.next = first_node
print(node.next.data) # 4
class LinkedList:
def __init__(self, data):
self.head = Node(data)
def append(self, data):
self.head.next = Node(data)
linked_list = LinkedList(3)
print(linked_list) # <__main__.LinkedList object at 0x000001207C5F8DF0>
print(linked_list.head) # Node(data) 이렇게 정의 해 놨으니까 , <__main__.Node object at 0x000001207C5F8A90> 값이 나오게 된다.
print(linked_list.head.data) # 3
print(linked_list.head.data.next) # None // 아직 next를 지정해놓지 않아서 처음 Node class에서 정의한 none이 나오게 된다.
여기에서 뒤에 차례로 붙여줄 코드를 짜면 아래처럼 된다.
# [3] -> [4]
# node 안에는 data, next로 구성
class Node:
def __init__(self, data):
self.data = data
self.next = None # 다음 포인터를 가리키지 않기 때문
node = Node(3)
print(node) # <__main__.Node object at 0x000001207C448BE0>
print(node.data) # 3
first_node = Node(4)
node.next = first_node
print(node.next.data) # 4
class LinkedList:
def __init__(self, data):
self.head = Node(data)
def append(self, data):
self.head.next = Node(data)
linked_list = LinkedList(3)
print(linked_list) # <__main__.LinkedList object at 0x000001207C5F8DF0>
print(linked_list.head) # Node(data) 이렇게 정의 해 놨으니까 , <__main__.Node object at 0x000001207C5F8A90> 값이 나오게 된다.
print(linked_list.head.data) # 3
print(linked_list.head.data.next) # None // 아직 next를 지정해놓지 않아서 처음 Node class에서 정의한 none이 나오게 된다.이렇게 짜여진 코드로 [3] -> [4] -> [5] -> [6] 까지 만들었다고 가정하고, [6] 칸 뒤에 새로운 칸을 넣고 싶다면 어떻게 코드를 짜야할까? 위의 코드로는 head와 head.next만 있어서 첫 번째 칸에 위치해 있다.
append 함수에 while문을 돌려서 만들면 된다.이 코드의 내용은 위치를 맨 뒤로 가서 None을 만나면 새로운 칸(노드)을 추가하는 것이다.
class Node:
def __init__(self, data):
self.data = data
self.next = None # 다음 포인터를 가리키지 않기 때문
class LinkedList:
def __init__(self, data):
self.head = Node(data)
def append(self, data):
if self.head is None: # head가 None이라면?에 대한 예외 처리
self.head = Node(data) # None인 head에 data 값을 넣음
return
self.head.next = Node(data) # 단순히 head 뒤에 노드를 추가
cur = self.head # 만들어진 리스트의 맨 끝으로 이동해 노드를 추가
while cur.next is not None:
cur = cur.next
# print('cur is', cur.data) #4
cur.next = Node(data)
linked_list = LinkedList(3)
linked_list.append(4)
linked_list.append(5)<print의 위치에 따라 print 값이 달라짐>
class Node:
def __init__(self, data):
self.data = data
self.next = None # 다음 포인터를 가리키지 않기 때문
class LinkedList:
def __init__(self, data):
self.head = Node(data)
def append(self, data):
if self.head is None: # head가 None이라면?에 대한 예외 처리
self.head = Node(data) # None인 head에 data 값을 넣음
return
self.head.next = Node(data) # 단순히 head 뒤에 노드를 추가
cur = self.head # 만들어진 리스트의 맨 끝으로 이동해 노드를 추가
print('cur is', cur.data)
# cur is 3
# cur is 3 이 print만 살려놓고 돌리며 이렇게 결과 값이 2개가 나오게 된다.
# cur = self.head 를 위에 선언 해놔서 이기 때문이다.
while cur.next is not None:
cur = cur.next
# print('cur is', cur.data) #4
cur.next = Node(data)
linked_list = LinkedList(3)
linked_list.append(4)
linked_list.append(5)class Node:
def __init__(self, data):
self.data = data
self.next = None # 다음 포인터를 가리키지 않기 때문
class LinkedList:
def __init__(self, data):
self.head = Node(data)
def append(self, data):
if self.head is None: # head가 None이라면?에 대한 예외 처리
self.head = Node(data) # None인 head에 data 값을 넣음
return
self.head.next = Node(data) # 단순히 head 뒤에 노드를 추가
cur = self.head # 만들어진 리스트의 맨 끝으로 이동해 노드를 추가
while cur.next is not None:
cur = cur.next
print('cur is', cur.data)
# cur is 4
# cur is 5 self.head.next = Node(data)를 정의해 놔서 이렇게 뜬다.
cur.next = Node(data)
linked_list = LinkedList(3)
linked_list.append(4)
linked_list.append(5)class Node:
def __init__(self, data):
self.data = data
self.next = None # 다음 포인터를 가리키지 않기 때문
class LinkedList:
def __init__(self, data):
self.head = Node(data)
def append(self, data):
if self.head is None: # head가 None이라면?에 대한 예외 처리
self.head = Node(data) # None인 head에 data 값을 넣음
return
cur = self.head # 만들어진 리스트의 맨 끝으로 이동해 노드를 추가
while cur.next is not None:
cur = cur.next
print('cur is', cur.data)
# cur is 4 self.head.next = Node(data)를 삭제하고 코드 실행
cur.next = Node(data)
linked_list = LinkedList(3)
linked_list.append(4)
linked_list.append(5)class Node:
def __init__(self, data):
self.data = data
self.next = None # 다음 포인터를 가리키지 않기 때문
class LinkedList:
def __init__(self, data):
self.head = Node(data)
def append(self, data):
if self.head is None: # head가 None이라면?에 대한 예외 처리
self.head = Node(data) # None인 head에 data 값을 넣음
return
cur = self.head # 만들어진 리스트의 맨 끝으로 이동해 노드를 추가
while cur.next is not None:
cur = cur.next
print('cur is', cur.data)
# cur is 4 self.head.next = Node(data)를 삭제하고 코드 실행
# 왜 4만 나온걸까??
cur.next = Node(data)
linked_list = LinkedList(3)
linked_list.append(4)
linked_list.append(5)맨 처음 코드 실행은 [3]만 들어가 있는 상황에서 .append를 이용해 [4]를 추가했다. 그런데 우리가 지금 self.head.next = Node(data)를 삭제하고 코드 실행했기 때문에 head.next가 없는 상황, 즉 None이기에 while문이 돌지 않고 그 밑의 cur.next =Node(Data)가 실행되어 [4]가 추가가 된 상황이고, linked_list = LinkedList(5)에 의해 append된 상황이다.
이렇게 추가가 되었기 때문에 cur=self.head가 3이 된 상황이고 next가 4인 None이 아닌 상황이 되는것이다. 그러고 while문으로 진입하여 cur=4인 상황이 되는것이다. 그래서 print문 출력된 것이다. 그러고 나서 4 뒤에 5가 담ㄱㅕ진 채 함수가 중단 될 것이다.
가 선생님의 코드 설명이었는데 나는 도저히 이해가 안가서 내가 알고있는 깃허브처럼 생각했다. 우리가 add를 하고 commit을 하고, push까지 마쳐야 비로소 업데이트 되는 것처럼 3을 정의한 것이 처음 파일 생성한 것, 4를 append한 게 commit, 5를 append한 게 4까지의 상황을 pushㅎㅏ고 5는 commit 한 것이라 이해했다... 아니면 어떡하지,,,??
▶️ linked list 전체 출력
class Node:
def __init__(self, data):
self.data = data
self.next = None # 다음 포인터를 가리키지 않기 때문
class LinkedList:
def __init__(self, data):
self.head = Node(data)
def append(self, data):
if self.head is None: # head가 None이라면?에 대한 예외 처리
self.head = Node(data) # None인 head에 data 값을 넣음
return
cur = self.head # 만들어진 리스트의 맨 끝으로 이동해 노드를 추가
while cur.next is not None:
cur = cur.next
print('cur is', cur.data)
# cur is 4
cur.next = Node(data)
def print_all(self):
print('[ All Nodes ]')
cur = self.head
while cur is not None:
print(cur.data)
cur = cur.next
linked_list = LinkedList(3)
linked_list.append(4)
linked_list.append(5)
linked_list.print_all()
# [ All Nodes ]
# 3
# 4
# 5처음 append 함수를 만들 때처럼 똑같이 while문을 써주었다.
▶️ linked list node index 번째 출력하기
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self, value):
self.head = Node(value)
def append(self, value):
cur = self.head
while cur.next is not None:
cur = cur.next
cur.next = Node(value)
def print_all(self):
cur = self.head
while cur is not None:
print(cur.data)
cur = cur.next
def get_node(self, index):
# index번으로 가려면 head에서 next를 index번 해야 한다는 의미
node = self.head
count = 0
while count < index:
node = node.next
count += 1
return node
linked_list = LinkedList(5)
linked_list.append(12)
print(linked_list.get_node(0).data)
print(linked_list.get_node(1).data)▶️ linked list node index 번째에 값을 삽입하 출력하기
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self, value):
self.head = Node(value)
def append(self, value):
cur = self.head
while cur.next is not None:
cur = cur.next
cur.next = Node(value)
def print_all(self):
cur = self.head
while cur is not None:
print(cur.data)
cur = cur.next
def get_node(self, index):
# index번으로 가려면 head에서 next를 index번 해야 한다는 의미
node = self.head
count = 0
while count < index:
node = node.next
count += 1
return node
def add_node(self, index, value):
# index번째에 새로운 값을 추가하는 것이므로
# index번째도 알아야하고, 무슨 값을 넣는지도 알아야한다.
# index next_node
# [자갈] [밀가루] [우편]
# new_node
# [흑연]
# 원래는 자밀우 순을 자흑밀우 순으로 !
# index.next = new_node
# new_node.next = next_node
new_node = Node(value)
node = self.get_node(index)
next_node = node.next
node.next = new_node
new_node.next = next_node
return
linked_list = LinkedList(5)
linked_list.append(12)
# print(linked_list.get_node(0).data) # 5
# print(linked_list.get_node(1).data) # 12
# [5] -> [12]
linked_list.append(8)
# [5] -> [12] -> [8] 을 [5] -> [6] -> [12] -> [8] 로 변경
linked_list.add_node(1,6) # [5] -> [12] -> [6] -> [8] 이 나오는걸로 봐서는 index-1번째를 찾아야함을 알 수 있다.
linked_list.print_all()index를 제대로 고치고
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self, value):
self.head = Node(value)
def append(self, value):
cur = self.head
while cur.next is not None:
cur = cur.next
cur.next = Node(value)
def print_all(self):
cur = self.head
while cur is not None:
print(cur.data)
cur = cur.next
def get_node(self, index):
# index번으로 가려면 head에서 next를 index번 해야 한다는 의미
node = self.head
count = 0
while count < index:
node = node.next
count += 1
return node
def add_node(self, index, value):
# index번째에 새로운 값을 추가하는 것이므로
# index번째도 알아야하고, 무슨 값을 넣는지도 알아야한다.
# index next_node
# [자갈] [밀가루] [우편]
# new_node
# [흑연]
# 원래는 자밀우 순을 자흑밀우 순으로 !
# index.next = new_node
# new_node.next = next_node
new_node = Node(value) # 6
node = self.get_node(index - 1) # 5
next_node = node.next # 12
node.next = new_node # 5 다음에 6
new_node.next = next_node #6 다음에 12
return
linked_list = LinkedList(5)
linked_list.append(12)
# print(linked_list.get_node(0).data) # 5
# print(linked_list.get_node(1).data) # 12
# [5] -> [12]
linked_list.append(8)
# [5] -> [12] -> [8] 을 [5] -> [6] -> [12] -> [8] 로 변경
linked_list.add_node(1,6)
linked_list.print_all()
# 5
# 6
# 12
# 8탸라~ 완성🙃
인 줄 알았겠지만 우리가 index-1을 해줌으로써 index[0]은 어떻게 되는건지 항상 생각을 해주어야한다.
이걸 고려해서 코드를 다시 짜면
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self, value):
self.head = Node(value)
def append(self, value):
cur = self.head
while cur.next is not None:
cur = cur.next
cur.next = Node(value)
def print_all(self):
cur = self.head
while cur is not None:
print(cur.data)
cur = cur.next
def get_node(self, index):
# index번으로 가려면 head에서 next를 index번 해야 한다는 의미
node = self.head
count = 0
while count < index:
node = node.next
count += 1
return node
def add_node(self, index, value):
# index번째에 새로운 값을 추가하는 것이므로
# index번째도 알아야하고, 무슨 값을 넣는지도 알아야한다.
# index next_node
# [자갈] [밀가루] [우편]
# new_node
# [흑연]
# 원래는 자밀우 순을 자흑밀우 순으로 !
# index.next = new_node
# new_node.next = next_node
new_node = Node(value) # 6 , 이 코드를 왜 올려두지???
if index == 0: # index가 0일 때 -1에 대한 예외 처리
# self.head = new_node 이렇게 코드짜면 앞에서 선언한 헤드가 없어지니까 안된다.
new_node.next = self.head # 6 -> 5가 온다
self.head = new_node # 6을 head로 지정
return
node = self.get_node(index - 1) # 5
# 0은 어떻게 되는 건지 고려하기
next_node = node.next # 12
node.next = new_node # 5 다음에 6
new_node.next = next_node #6 다음에 12
return
linked_list = LinkedList(5)
linked_list.append(12)
# print(linked_list.get_node(0).data) # 5
# print(linked_list.get_node(1).data) # 12
# [5] -> [12]
linked_list.append(8)
# [5] -> [12] -> [8] 을 [5] -> [6] -> [12] -> [8] 로 변경
linked_list.add_node(1,6)
linked_list.print_all()
# 5
# 6
# 12
# 8-1이 나오게 되면 무조건 0일 때를 항상 고려해 줘야한다!
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self, value):
self.head = Node(value)
def append(self, value):
cur = self.head
while cur.next is not None:
cur = cur.next
cur.next = Node(value)
def print_all(self):
cur = self.head
while cur is not None:
print(cur.data)
cur = cur.next
def get_node(self, index):
node = self.head
count = 0
while count < index:
node = node.next
count += 1
return node
def add_node(self, index, value):
new_node = Node(value)
if index == 0:
new_node.next = self.head
self.head = new_node
return
node = self.get_node(index - 1)
next_node = node.next
node.next = new_node
new_node.next = next_node
def delete_node(self, index):
# index
# [자갈] [흑연] [밀가루] [우편]
# delete_node
if index == 0: # index가 0일 때 -1에 대한 예외 처리
self.head = self.head.next
return
node = self.get_node(index - 1)
# 0은 어떻게 되는 건지 고려하기
node.next = node.next.next
return
# 내가 원하는 리스트 [5] -> [12]
linked_list = LinkedList(5)
linked_list.append(12)
# 내가 원하는 리스트 [3] -> [5] -> [12]
linked_list.add_node(0,3)
linked_list.print_all()
# 내가 원하는 리스트 [5] -> [12]
linked_list.delete_node(0)
linked_list.print_all()
# 결과값 제대로 나옴
# 3
# 5
# 12
# 5
# 12
Linked List Question 1
다음과 같은 두 링크드 리스트를 입력받았을 때, 합산한 값을 반환하시오.
예를 들어 아래와 같은 링크드 리스트를 입력받았다면, 각각 678, 354 이므로 두개의 총합 678 + 354 = 1032 를 반환해야 한다. 단, 각 노드의 데이터는 한자리 수 숫자만 들어갈 수 있다.
[6] -> [7] -> [8]
[3] -> [5] -> [4]
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self, value):
self.head = Node(value)
def append(self, value):
cur = self.head
while cur.next is not None:
cur = cur.next
cur.next = Node(value)
def get_linked_list_sum(linked_list_1, linked_list_2):
sum_1 = 0
head_1 = linked_list_1.head
while head_1 is not None:
sum_1 = sum_1 * 10 + head_1.data
head_1 = head_1.next
sum_2 = 0
head_2 = linked_list_2.head
while head_2 is not None:
sum_2 = sum_2 * 10 + head_2.data
head_2 = head_2.next
print(sum_1)
print(sum_2)
return sum_1 + sum_2
linked_list_1 = LinkedList(6)
linked_list_1.append(7)
linked_list_1.append(8)
linked_list_2 = LinkedList(3)
linked_list_2.append(5)
linked_list_2.append(4)
print(get_linked_list_sum(linked_list_1, linked_list_2))중복되지 않는 코드가 좋은 코드이기 때문에
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self, value):
self.head = Node(value)
def append(self, value):
cur = self.head
while cur.next is not None:
cur = cur.next
cur.next = Node(value)
def i_get_linked_list_sum(linked_list):
linked_list_sum = 0
head = linked_list.head
while head is not None:
linked_list_sum = linked_list_sum * 10 + head.data
head = head.next
return linked_list_sum
def get_linked_list_sum(linked_list_1, linked_list_2):
sum_1 = i_get_linked_list_sum(linked_list_1)
sum_2 = i_get_linked_list_sum(linked_list_2)
return sum_1 + sum_2
linked_list_1 = LinkedList(6)
linked_list_1.append(7)
linked_list_1.append(8)
linked_list_2 = LinkedList(3)
linked_list_2.append(5)
linked_list_2.append(4)
print(get_linked_list_sum(linked_list_1, linked_list_2))
라고 선생님 코드 그대로 썼는데 왜 때문에 찾을수 없다 그렂??? 왜,,,??!?!?!?!??!?!?