JAVA 자료구조 : 링크드 리스트(Linked List)

스터디사이트 : https://www.hackerrank.com

JAVA 자료구조 : 링크드 리스트(Linked List)

※ 조건

• 새로운 노드를 만드는 insert()메소드의 내용을 완성해라.
• head 파라미터를 이용하여 새로운 노드를 링크드 리스트 끝에 추가하라.
• 새로운 노드가 추가되면, head 노드의 참조값을 리턴해라.
• insert() 메소드로 전달되는 head인자가 null이면, 초기 목록은 empty인 것이다.

※ 주어진 코드

: 아래 표시된 영역 안에서만 코딩 할 것.

class Node {
    int data;
    Node next;
    Node(int d) {
        data = d;
        next = null;
    }
} // end Node class
 
class Solution {
    public static Node insert(Node head,int data) {
        //Complete this method
        /* 코딩할 영역 */
    }
 
    public static void display(Node head) {
        Node start = head;
        while(start != null) {
            System.out.print(start.data + " ");
            start = start.next;
        }
    }
 
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        Node head = null;
        int N = sc.nextInt();
 
        while(N-- > 0) {
            int ele = sc.nextInt();
            head = insert(head,ele);
        }
        display(head);
        sc.close();
    }
}

Node 클래스의 변수

data : int

next : 

- 리턴타입이 Node객체타입의 변수

- 인스턴스 포인터의 역할을 함 - 다른 노드로 지정하는 역할을 하는. (i.e. 리스트 안의 다른 노드)

* i.e. : 즉 (라틴어 id est에서)

insert() 메소드

파라미터1 : head

 - Linked List의 첫 노드로 지정하는 Node객체변수

파라미터2 : data 

 - int타입, 리스트의 끝에 새로운 Node 객체로써 추가되어야 하는 숫자변수

입력

4        ← 노드 갯수

2

3

4

1

출력

2 3 4 1

Overview

디버깅1

코딩을 보니 흐름도는 ..

1. Scanner로 입력을 받는다.

2. 입력받은 첫 줄의 숫자만큼 while문으로 반복을 돌린다.

3. while문 안에서 입력받은 다음 줄의 숫자를 ele변수로 받고 Solution클래스의 insert() 메소드를 불러옴. insert() 메소드는 우리가 코딩해야 한다.

4. while문 빠져나오고 Solution클래스의 display() 메소드를 불러옴. display() 안에서 Output이 나온다.

5. Node클래스의 생성자가 여태 안쓰인 것 보니 우리가 코딩할 때 사용해야 하나보다.

사실 자료구조에서 LinkedList의 개념을 알아야 더 쉽게 풀 수 있는데 필자는 워낙 배운 지 오래 되어서 이해하는 데에 험난한 길을 다시 걸어야 할 것 같다. 

일단 자료구조에 대한 생활코딩 youtube 를 통해서 개념을 배웠다.. →→→→  Click 

LinkedList의 개념

배열이 아닌 독립된 형태의 각 요소들이 리스트로 순차적으로 있다고 하면,

이 요소 하나하나를 노드로 부를 수 있다.

맨 첫번째 노드를 'head'라고 명명하고, 맨 끝 노드를 'tail'이라 명명한다.

첫번째 노드는 두번째 노드를 가리키며, 두번째 노드는 세번째 노드를 가리키고 하는 식으로 head부터 tail 노드까지 연결이 된 리스트를 LinkedList라고 하는 것이다.

디테일은 그림으로 보고 이해하면 된다.

코딩연습 1

class Node { int data; Node next; Node(int d) { data = d; next = null; } } // end Node class public class July14_LinkedList { public static Node insert(Node head,int data) { //Complete this method head = new Node(data); System.out.println("insert data : " + head.data); return head; } public static void display(Node head) { Node start = head; while(start != null) { System.out.print(start.data + " "); start = start.next; } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); Node head = null; int N = sc.nextInt(); while(N-- > 0) { int ele = sc.nextInt(); head = insert(head,ele); } display(head); sc.close(); } }

결과 :  insert data : 2 insert data : 3 insert data : 4 insert data : 1 1

디버깅2

입력받는 ele를 insert메소드의 파라미터로 넣었으니,

insert메소드의 ele파라미터를 Node클래스의 생성자의 파라미터에다가 삽입해 보았다.

그리고 디버깅을 위해 System.out.println으로 Node클래스의 data변수에 값이 잘 출력되는지 코딩해보았다.

그렇게 하니까 Node.data에는 값이 잘 들어간다.

그렇다면 display() 에서는 Node객체가 null값일 때까지 while 반복을 하는데, Node.data를 하나씩 덧붙여가며 출력을 시키는 방식이다.

배열변수가 있는것도 아니고 어떻게 할수있지..

더군다나 while 반복이 다 마무리 된 이후에 딱 한번 실행하는 display()메소드인대도..

아, main메소드 안에 쓰이는 while문 안의 insert메소드는 반복이 되고, 본인이 직접 코딩 할 수 있으므로,

insert 메소드 안에다가 display메소드를 실행시키면 되겠구나! 싶었다.

코딩연습 2

class Node { int data; Node next; Node(int d) { data = d; next = null; } } // end Node class public class July14_LinkedList { public static Node insert(Node head,int data) { //Complete this method head = new Node(data); display(head); return head; } public static void display(Node head) { Node start = head; while(start != null) { System.out.print(start.data + " "); start = start.next; } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); Node head = null; int N = sc.nextInt(); while(N-- > 0) { int ele = sc.nextInt(); head = insert(head,ele); } display(head); sc.close(); } }

결과 :  2 3 4 1 1

디버깅2

아까비.. 한번 더 출력되었네..

코딩연습 3

class Node { int data; Node next; Node(int d) { data = d; next = null; } } // end Node class public class July14_LinkedList { public static Node insert(Node head,int data) { //Complete this method head = new Node(data); display(head); System.out.println("Node.next : " + head.next); return head.next; } public static void display(Node head) { Node start = head; while(start != null) { System.out.print(start.data + " "); start = start.next; } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); Node head = null; int N = sc.nextInt(); while(N-- > 0) { int ele = sc.nextInt(); head = insert(head,ele); } display(head); sc.close(); } }

결과 :  2 Node.next : null 3 Node.next : null 4 Node.next : null 1 Node.next : null

디버깅3

Node 생성자를 이용하면 마지막에 next 변수는 항상 null값이 된다는 것을 이용해서,

리턴값을 항상 null값이 나오게끔 return을 next변수로 나오게 했다.

그래야 display()메소드 돌아갈 때 while문이 아얘 돌아가지 않을 테니까.. ㅋ

결과

class Node { int data; Node next; Node(int d) { data = d; next = null; } } // end Node class public class July14_LinkedList { public static Node insert(Node head,int data) { //Complete this method head = new Node(data); display(head); return head.next; } public static void display(Node head) { Node start = head; while(start != null) { System.out.print(start.data + " "); start = start.next; } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); Node head = null; int N = sc.nextInt(); while(N-- > 0) { int ele = sc.nextInt(); head = insert(head,ele); } display(head); sc.close(); } }

결과 :  2 3 4 1

다른 사람의 코딩 1

public static Node insert(Node head,int data){ // if list has no elements, return a new node if(head == null){ return new Node(data); } // else iterate through list, add node to tail, and return head Node tmp = head; while(tmp.next != null){ tmp = tmp.next; } tmp.next = new Node(data); return head; }

결과 :  2 3 4 1

다른 사람의 코딩 2

public static Node insert(Node head,int data){ Node n = new Node(data); Node current = head; //if there is no headNode if(head == null){ return n; // if there is no headNode, create a Node } //if there is a headNode else{ //check if another Node is linked to the list while(current.next != null){ current = current.next; } current.next = n; return head; } //end if }

결과 :  2 3 4 1 * 설명 line 5 : check if head is null(there will be no nodes at the very begining) line 6 : if there is no headNode, create new node and return that line 11 : check if this node points to null line 12 : iterate through the list, move to the next node if current node is not pointing to null line 14 : the last node must now point to the newly added node line 15 - head 말고 current를 리턴하지 않는 이유 : current will be pointing to the end of list.. As per the task, you need to return the starting point(reference to head) of the list.

디버깅 4

위의 코딩을 보면서 UML을 그려 보았다. 

Node 클래스의 next변수의 타입이 Node이므로,

 Node객체의 next변수는 새로 만들어진 'n' Node객체를 가르키고 있다.

그러므로 출력할 때 

 System.out.print(start.data)로 출력 후 Node start = start.next 를 통해서 다음 Node객체로 넘어가면서 그 다음 Node객체의 data를 출력하는 방식으로 반복출력을 시키면 되는 것이다.

관련 강좌 링크도 있어서 참고하기를.. →→→ CLICK