Data structure
Linked List (링크드 리스트)
배열(list) 는 순차적으로 연결된 공간에 데이터를 나열하는 구조
연결 리스트 (Linked List) 는 떨어진 곳에 존재하는 데이터를 화살표로 연결하여 관리하는 구조
리스트는 미리 공간을 확보해야하는데 linked list는 그때 그때 필요한 공간을 사용 가능. 리스트의 단점을 극복
노드(Node) : 데이터 저장 단위 (데이터 값, 포인터(주소값)) 로 구성
포인터(Pointer) : 각 노드 안에서 다음이나 이전 노드와의 연결 정보를 가지고 있는 공간
맨 앞의 주소만 알면 리스트의 모든 데이터를 알수 있다.
문제에서 주어진 linked list 코드
class SingyLinkedListNode(): # 상속하는 클래스가 없을 때는 괄호가 없어도되긴 함!
def __init__(self, node_data):
self.data = node_data
self.next = None
class SingyLinkedList():
def __init__(self):
self.head = None
1. 링크드 리스트 head 가 주어졌을 때 모든 값을 print 하기
for 문을 이용해서 해결할 수 있다.
input 의 head 는 head node 자체를 의미한다.
def printLinkedList(head):
print(head.data)
n = head.next
while True:
print(n.data)
n = n.next
if n == None:
break
if __name__ == '__main__':
llist_count = int(input())
llist = SinglyLinkedList()
for _ in range(llist_count):
llist_item = int(input())
llist.insert_node(llist_item)
printLinkedList(llist.head)
while n == None 이 아닐 때 까지 : 좀 더 쉽게 표현할 수 있다.
def printLinkedList(head):
print(head.data)
n = head.next
while n:
print(n.data)
n = n.next
다음은 재귀적으로 문제를 해결
def printLinkedList(head):
print(head.data)
if head.next:
printLinkedList(head.next)
2. 링크드 리스트에 data 값 추가하기
def insertNodeAtHead(llist, data):
# Write your code here
new = SinglyLinkedListNode(data)
new.next = llist
return new
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
llist_count = int(input())
llist = SinglyLinkedList()
for _ in range(llist_count):
llist_item = int(input())
llist_head = insertNodeAtHead(llist.head, llist_item)
llist.head = llist_head
print_singly_linked_list(llist.head, '\n', fptr)
fptr.write('\n')
fptr.close()
지금까지 fast campus 는 링크드 리스트에서 None 다음에 data 를 add 한다고 배웠는데
이 문제에서는 head 를 대체하라고 되어있다. 문제를 잘 읽어야 하겠다.
(문제가 더 쉬워짐!)
3. 링크드 리스트 특정 위치에 노드 추가하기
def insertNodeAtPosition(llist, data, position):
# Write your code here
n = llist
for _ in range(position-1):
n = n.next
new = SinglyLinkedListNode(data)
new.next = n.next
n.next = new
return llist
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
llist_count = int(input())
llist = SinglyLinkedList()
for _ in range(llist_count):
llist_item = int(input())
llist.insert_node(llist_item)
data = int(input())
position = int(input())
llist_head = insertNodeAtPosition(llist.head, data, position)
print_singly_linked_list(llist_head, ' ', fptr)
fptr.write('\n')
fptr.close()
'백준 단계별 코딩 테스트' 카테고리의 다른 글
HackerRank : Equal Stacks (0) | 2022.09.06 |
---|---|
HackerRank prepare 문제 : Linked List 2 (0) | 2022.07.31 |
220722 : 1032, 1110 번 풀이 + HackerRank prepare 1문제 (0) | 2022.07.22 |
220714 : 1264, 2744, 23037 번 풀이 (0) | 2022.07.22 |
스택 Stack (0) | 2021.12.09 |