Hackerrank Day 15 Linked List

알고리즘 연습 사이트

www.hackerrank.com

Day 15:Linked List

List reference: https://docs.oracle.com/javase/tutorial/collections/interfaces/list.html

Linked List 연결된 리스트, 리스트의 요소 한개가 다음 요소(노드)와 연결되어 있다는 의미이다. 
자세한 내용은 위의 java API docs 참조 문헌에 있다.
링크드 리스트에서 노드들은 다음번 차례의 노드의 참조 주소를 가지고 있어서 아래의 그림과 같이 연결이 되는 형태이다. 
마지막 tail 노드는 다음 요소가 없기 때문에 null를 가르키는 특징을 가진다.

LinkedList

정의된 Node 클래스를 이용하여 LinkedList의 insert 메소드를 구현해보는 것이 Day 15의 문제이다.

KeyPoint는 첫번째 Head Node의 객체의 참조 주소를 절대로 잃어버려서는 안된다는 점이다.

새로 생기는 노드로 참조를 이동해서 연결해야 한다(?)는 강박관념에 사로잡혀 굉장히 어렵게 문제를 풀었다.
지금 구현하고자 하는 insert 메소드는 최초의 노드를 계속 return 해주어야 하는게 핵심이다. 
왜냐하면 첫번째 노드를 잃어버리게 되면, LinkedList 객체의 참조 주소 자체를 잃어버리는 것과 같다.
시작 노드자체가 Null인 경우/중간 노드/꼬리 노드의 특징을 이용하여 if 분기 처리를 한다.  
중간 노드인 경우 next 값이 존재 하므로 next가 null인 경우까지 반복하면서 꼬리를 찾다가 꼬리노드의 next에 새로운 노드를 만들어 값을 넣으면 된다.



노드 클래스는 아래와 같이 next 라는 다음 노드의 주소를 저장하는 참조변수와, data를 저장하는 int형 변수로 이루어져 있다.

class Node {
   int data;
   Node next;
   Node(int d) {
       data = d;
       next = null;
   }
}

방법은 해커스랭크의 도움을 받아 2가지로 정리해보았다.
1번 방법이 코드상으로 더 깔끔해 보인다. 
소스 코드를 보면 메소드 인자로 전달되는 head 변수가 다른 노드 주소로 변동되는 지점이 전혀 없다.

//1번 방법

public static Node insert(Node head,int data) {
    if(head == null){ //처음 시작 지점. head 가 null로 들어온 경우.
        return new Node(data);
    }else if(head.next == null){ //꼬리노드라면,
        Node newNode = new Node(data); //새로운 노드를 만들면서 data를 생성자를 통해 초기화
        head.next = newNode; // 현재 노드의 next 변수에 새로 만든 노드의 참조주소를 세팅한다.
    }else{ //중간 노드라면,
        insert(head.next , data); //재귀 호출을 통해 자신의 꼬리를 찾는다.
    }
    return head; //계속 head 노드를 리턴해 주어 첫번째 참조 변수 값을 잃지 않는다.
}

//2번 방법

public static Node insert(Node head,int data) {    
    if(head == null){ //1번과 동일
        return new Node(data);
    }else if(head.next == null){ //1번과 동일
        Node nextNode = new Node(data);
        head.next = nextNode;
    }else{ //중간 노드라면,
        /*
          tmp 참조 변수에 head 참조 주소를 복사한다.
          head의 값을 복사하는 경우는 while문 안에서 꼬리노드를 찾기 위해 tmp값에 변동이 일어난다.
          만약 tmp 값을 복사하지 않고 head값을 그대로 이용하면 head 참조변수 값을 잃어버리게 된다. 
        */
        Node tmp = head; 
        while(tmp.next !=null){ //tmp의 next가 null이 아닐 때까지 반복한다.
            tmp = tmp.next; //tmp에 tmp.next를 대입하여 다음 노드의 next값을 계속 체크 할 수 있도록 한다.
        }
        //while문을 벗어났다면 tmp는 꼬리노드일 것이다.
        tmp.next = new Node(data);//꼬리 노드의 next에 새로운 노드를 추가한다.
    }
    return head;
}