규도자 개발 블로그

[해커랭크(Hackerrank)/30 Days of Code/파이썬3(python3)] Day 15: Linked List 본문

알고리즘/풀이

[해커랭크(Hackerrank)/30 Days of Code/파이썬3(python3)] Day 15: Linked List

규도자 (gyudoza) 2019. 3. 27. 20:37

Objective 
Today we're working with Linked Lists. Check out the Tutorial tab for learning materials and an instructional video!


Node class is provided for you in the editor. A Node object has an integer data field, , and a Node instance pointer, , pointing to another node (i.e.: the next node in a list).

Node insert function is also declared in your editor. It has two parameters: a pointer, , pointing to the first node of a linked list, and an integer  value that must be added to the end of the list as a new Node object.

Task 
Complete the insert function in your editor so that it creates a new Node (pass  as the Node constructor argument) and inserts it at the tail of the linked list referenced by the  parameter. Once the new node is added, return the reference to the  node.

Note: If the  argument passed to the insert function is null, then the initial list is empty.

Input Format

The insert function has  parameters: a pointer to a Node named , and an integer value, 
The constructor for Node has  parameter: an integer value for the  field.

You do not need to read anything from stdin.

Output Format

Your insert function should return a reference to the  node of the linked list.

Sample Input

The following input is handled for you by the locked code in the editor: 
The first line contains T, the number of test cases. 
The  subsequent lines of test cases each contain an integer to be inserted at the list's tail.

4
2
3
4
1

Sample Output

The locked code in your editor prints the ordered data values for each element in your list as a single line of space-separated integers:

2 3 4 1

Explanation

, so the locked code in the editor will be inserting  nodes. 
The list is initially empty, so  is null; accounting for this, our code returns a new node containing the data value  as the  of our list. We then create and insert nodes , and  at the tail of our list. The resulting list returned by the last call to  is , so the printed output is 2 3 4 1.

풀이

    def insert(self,head,data): 
        node = Node(data)
        if not head:
            head = node
        else:
            current = head
            while(current.next):
                current = current.next
            current.next = node
        return head

설명

자료형 중 하나인 연결형 리스트를 구현하는 문제이다. 그림에서 볼 수 있다시피 연결형 리스트를 마치 기차처럼 표현했지만 실제 코드로 구현하는 연결형 리스트의 모습은 기차형태가 아닌, 인형 안에 똑같이 생긴 인형이 들어있는 마트료시카와 비슷한 모습이라고 상상하면 쉽다. 예제로 주어진 2 3 4 1을 예로 들자면 2라는 데이터가 가리키고 있는 .next는 다음 노드의 주소나 위치가 아니다. 그냥 .next안에 다음 노드 데이터가 들어있는 형태이다. 2노드 안에는 3노드가 들어 있고, 그 안에는 4, 그리고 그 안에 1이 들어있는 4중 마트료시카 구조라고 보면 된다.

 물론! 자바에서 클래스와 객체에 대해서 배웠거나 C에서 구조체, 혹은 배열에 대해서 어느정도 배웠다면 객체를 변수에 대입해도 해당 변수에 실제 객체가 들어가는 것이 아니라 해당 객체의 시작점이 되는 메모리 주소가 들어간다는 걸 알 것이다. 하지만 위에서 말했다시피 해당 자료구조를 코드로 구현할 때 개념적인 이해를 돕기 위해서는 위처럼 상상하는 게 도움된다.

Comments