HackerRank prepare 문제 : Linked List 1

Data structure

Linked List (링크드 리스트)

배열(list) 는 순차적으로 연결된 공간에 데이터를 나열하는 구조

연결 리스트 (Linked List) 는 떨어진 곳에 존재하는 데이터를 화살표로 연결하여 관리하는 구조

리스트는 미리 공간을 확보해야하는데 linked list는 그때 그때 필요한 공간을 사용 가능. 리스트의 단점을 극복

노드(Node) : 데이터 저장 단위 (데이터 값, 포인터(주소값)) 로 구성

포인터(Pointer) : 각 노드 안에서 다음이나 이전 노드와의 연결 정보를 가지고 있는 공간

https://habr.com/en/post/506660/

 

맨 앞의 주소만 알면 리스트의 모든 데이터를 알수 있다.

 

문제에서 주어진 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()