linkedList 에 대해서 궁금해요

Question

/* * &#64; TITLE Linked List (연결 리스트) */ // List를 구성하는 Node 클래스 class ListNode{ private String data; // 데이터 저장 변수 public ListNode link; // 다른 노드를 참조할 링크 노드 public ListNode() { this.data &#61; null; this.link &#61; null; } public ListNode(String data) { this.data &#61; data; this.link &#61; null; } public ListNode(String data, ListNode link) { this.data &#61; data; this.link &#61; link; } public String getData() { return this.data; } } public class LinkedList { private ListNode head; // ListNode 타입의 head 노드 인스턴스 변수 // LinkedList 생성자 public LinkedList() { head &#61; null; // head 노드 초기화 } // Node 삽입 (중간에 삽입) public void insertNode(ListNode preNode, String data) { ListNode newNode &#61; new ListNode(data); // 새로운 노드 생성 // preNode.link는 preNode의 다음 노드이므로, // newNode.link &#61; preNode.link는 새로운 노드의 link가 preNode의 다음 노드를 참조하도록 함. newNode.link &#61; preNode.link; // preNode의 link가 새로운 노드를 참조하도록 함. // 최종적으로 'preNode -> newNode -> 기존 preNode의 다음 노드 '이렇게 구성됨. preNode.link &#61; newNode; } // Node 삽입 (마지막에 삽입) public void insertNode(String data) { ListNode newNode &#61; new ListNode(data); // 새로운 노드 생성 if(head &#61;&#61; null) { // head 노드가 null인 경우 새로운 노드를 참조하도록 함 this.head &#61; newNode; } else { // head 노드가 null이 아닌 경우 temp 노드가 head를 참조. // tempNode는 마지막 노드를 찾아서 참조하기 위해 사용. ListNode tempNode &#61; head; // temp 노드의 link가 null이 아닐 때까지 다음 노드를 참조. // tempNode.link는 다음 노드를 참조하고 있으므로, // tempNode &#61; tempNode.link는 tempNode에 다음 노드를 참조하도록 하는 것. // while문이 모두 실행되면 tempNode는 가장 마지막 노드를 참조하게 됨. while(tempNode.link !&#61; null) { tempNode &#61; tempNode.link; // 다음 노드를 참조 } // tempNode(마지막 노드)의 link가 다음 노드를 참조하도록 함. tempNode.link &#61; newNode; } } // Node 삭제(중간 노드 삭제) public void deleteNode(String data) { // preNode는 head가 가리키는 노드를 할당 ListNode preNode &#61; head; // tempNode는 head가 가리키는 노드의 다음 노드. 즉, preNode의 다음 노드를 할당 ListNode tempNode &#61; head.link; // 주어진 데이터가 preNode의 데이터와 일치하는 경우 // 즉, 첫번째 노드의 데이터와 일치하는 경우 if(data.equals( preNode.getData() )) { // head는 preNode의 다음 노드를 참조하도록 함. head &#61; preNode.link; // preNode의 link는 null을 할당하여 연결을 끊음. preNode.link &#61; null; } else { // tempNode가 null일 때까지 반복하여 탐색 while(tempNode !&#61; null) { // 주어진 데이터와 temp 노드의 데이터가 일치할 경우. if(data.equals( tempNode.getData() )) { // tempNode가 마지막 노드인 경우 if(tempNode.link &#61;&#61; null) { preNode.link &#61; null; } else { // tempNode가 마지막 노드가 아닌 경우 // preNode의 link는 tempNode의 다음 노드를 참조. // tempNode의 link는 null을 할당하여 다음 노드로의 연결을 끊음. preNode.link &#61; tempNode.link; tempNode.link &#61; null; } break; } else { // 데이터가 일치하지 않을 경우 // preNode에 tempNode를 할당하고, tempNode에 다음 노드 할당. preNode &#61; tempNode; tempNode &#61; tempNode.link; } } } } // Node 삭제(마지막 노드 삭제) public void deleteNode() { ListNode preNode; ListNode tempNode; // head 노드가 null인 경우 모든 노드가 삭제되었으므로 return if(head &#61;&#61; null) { return; } // head 노드의 link가 null인 경우 // 노드가 1개 남았을 경우 if(head.link &#61;&#61; null) { // head에 null을 할당하여 남은 노드와의 연결을 끊음. head &#61; null; } else { // preNode는 head가 가리키는 노드를 할당 preNode &#61; head; // tempNode는 head가 가리키는 노드의 다음 노드. 즉, preNode의 다음 노드를 할당 tempNode &#61; head.link; // tempNode의 link가 null이 아닐 때까지 한 노드씩 다음 노드로 이동. // preNode는 tempNode를 할당하고 // tempNode는 tempNode의 다음 노드를 할당. // 이렇게 하면 preNode는 마지막 노드의 이전 노드가 되고, tempNode는 마지막 노드가 됨. while(tempNode.link !&#61; null) { preNode &#61; tempNode; tempNode &#61; tempNode.link; } // preNode의 link를 null로 만들어서 가장 마지막 노드를 삭제 // 즉, preNode의 다음 노드인 tempNode로의 연결을 끊음. preNode.link &#61; null; } } // Node 탐색 public ListNode searchNode(String data) { ListNode tempNode &#61; this.head; // temp 노드에 head가 가리키는 첫 번째 할당. // temp 노드가 null이 아닐 때까지 반복하여 탐색 while(tempNode !&#61; null) { // 주어진 데이터와 temp 노드의 데이터가 일치할 경우 해당 temp 노드를 return if(data.equals(tempNode.getData())) { return tempNode; } else { // 데이터가 일치하지 않을 경우 temp 노드에 다음 노드 할당. tempNode &#61; tempNode.link; } } return tempNode; } // 리스트의 노드를 역순으로 구성 public void reverseList() { ListNode nextNode &#61; head; // head가 참조하는 첫번째 노드를 할당. ListNode currentNode &#61; null; ListNode preNode &#61; null; // nextNode가 순차적으로 이동하며 currentNode의 link가 preNode를 참조하도록 함. // 1) preNode를 currentNode 위치로 이동 // 2) currentNode는 nextNode 위치로 이동 // 3) nextNode는 다음 노드 위치로 이동 // 4) currentNode의 link는 preNode를 참조하도록 함 while(nextNode !&#61; null) { preNode &#61; currentNode; // preNode는 currentNode 위치로 이동 currentNode &#61; nextNode; // currentNode는 nextNode 위치로 이동 nextNode &#61; nextNode.link; // nextNode는 다음 노드 위치로 이동 currentNode.link &#61; preNode; // currentNode의 link에 preNode를 할당하여 역순으로 설정 } head &#61; currentNode; // currentNode가 마지막 노드를 가리킬 때, head는 currentNode를 참조하도록 함. } // 연결 리스트에 저장된 모든 데이터를 출력 public void printList() { ListNode tempNode &#61; this.head; // tempNode에 head가 가리키는 첫번째 노드를 할당 // tempNode가 null이 아닐 때까지 반복하여 출력 while(tempNode !&#61; null) { System.out.print(tempNode.getData() &#43; &#34; &#34;); tempNode &#61; tempNode.link; // temp 노드에 다음 노드(tempNode.link) 할당. } System.out.println(); } public static void main(String args[]) { LinkedList linkedList &#61; new LinkedList(); // 연결 리스트 생성 String str &#61; &#34;wed&#34;; linkedList.insertNode(&#34;sun&#34;); linkedList.insertNode(&#34;mon&#34;); linkedList.insertNode(&#34;tue&#34;); linkedList.insertNode(&#34;wed&#34;); linkedList.insertNode(&#34;thu&#34;); linkedList.insertNode(&#34;fri&#34;); linkedList.insertNode(&#34;sat&#34;); linkedList.printList(); System.out.println(linkedList.searchNode(str).getData()); linkedList.deleteNode(linkedList.searchNode(str).getData()); linkedList.printList(); str &#61; &#34;sun&#34;; linkedList.deleteNode(linkedList.searchNode(str).getData()); linkedList.printList(); linkedList.reverseList(); linkedList.printList(); } } 출처: https://freestrokes.tistory.com/84 [FREESTROKES DEVLOG] 이런 코드가 있습니다.여기서 의문이 계속 풀리지 않는데요 public void insertNode(String data) { ListNode newNode &#61; new ListNode(data); // 새로운 노드 생성 if(head &#61;&#61; null) { // head 노드가 null인 경우 새로운 노드를 참조하도록 함 this.head &#61; newNode; } else { // head 노드가 null이 아닌 경우 temp 노드가 head를 참조. // tempNode는 마지막 노드를 찾아서 참조하기 위해 사용. ListNode tempNode &#61; head; // temp 노드의 link가 null이 아닐 때까지 다음 노드를 참조. // tempNode.link는 다음 노드를 참조하고 있으므로, // tempNode &#61; tempNode.link는 tempNode에 다음 노드를 참조하도록 하는 것. // while문이 모두 실행되면 tempNode는 가장 마지막 노드를 참조하게 됨. while(tempNode.link !&#61; null) { tempNode &#61; tempNode.link; // 다음 노드를 참조 } // tempNode(마지막 노드)의 link가 다음 노드를 참조하도록 함. tempNode.link &#61; newNode; } } 출처: https://freestrokes.tistory.com/84 [FREESTROKES DEVLOG]이 부분 while 문에서요tempNode.link &#61; newNode 할 경우 head.link 에 대입이 되는데 여기서 알 수 있는건 tempNode 와 head 는 같은 곳을 참조한다 라는건데요~그러면 그전에 while 문이 돌면 tempNode &#61; tempNode .link 가 됩니다.이 때왜 같은 곳을 참조하고있는데head 는 head .link로 변하지 않는 걸까요?

gandhi · Answer

https://www.tutorialspoint.com/data_structures_algorithms/linked_list_algorithms.htm아래 while문이 어떻게 동작되는지 이해 부족하신것 같습니다.저도 처음에 이해가 잘 안됐던 부분입니다.ㅎㅎ while(tempNode.link !&#61; null) { tempNode &#61; tempNode.link; // 다음 노드를 참조 }처음엔 생각하신것처럼 head에서 시작하지만while문이 돌면서tempNode에 마지막 노드가 들어가고마지막 노드 link에 newNode를 붙이는 겁니다그림 그려가며 이해하시면 도움 많이 됩니다 ㅎㅎ

커린이 · Answer

gandhi kim 제 질문은 그게 아닌데요 그래도 설명을 덧붙이기엔 좋은거같아요 while문이 돌면서 link에 newNode 가 들어가면 head.link에도 newNode가 들어가잖아요?! ㅎㅎ 참조를 하기때문에요 근데 while문이 돌 때 tempNode 가 tempNode.link 가 되는데 왜 head는 head.link로 변하지 않냐는 질문이 었습니다. 이해가 잘되신거같은데 꼭좀 답변좀 부탁드리겟습니다 ㅠㅠㅠ 거의 2개월 째 헤매고 있어요;;

junior123 · Answer

tempNode는 reference variable입니다.말 그대로 head가 이미 null이 아니기 때문에 else 로 제어 되었고,head.link는 다음 노드를 가리키죠.그렇기 때문에 tempNode는 현재 head를 가리키고 있습니다.tempNode.link 는 head.link의 메모리 주소와 같습니다.tempNode.link가 null이 아니라면, tempNode는 그 다음 Node를 가리키게 되겠죠.결국엔, tempNode.link가 null 이라면 마지막 노드라는 말이 되니까 마지막 노드.link에 참조 시키는 코드로 이해되었습니다.여기서 질문이,tempNode 와 head 는 참조하고 있는 주소가 같은데도 head는 메모리 주소가 변경되지 않는가에 대한 질문으로 사료되네요ListNode tempNode &#61; head;여기서, tempNode는 head 메모리 주소를 가리키게 됩니다.while(tempNode.link !&#61; null) { tempNode &#61; tempNode.link; // 다음 노드를 참조 }여기서, tempNode.link가 null이 아니라면, tempNode는 head.link, 즉 head에 연결된 다음 노드를 가리키게 됩니다, 가장 중요한 점은, tempNode 주소는 head를 가리키고 있다가 head.link 주소를 가리키게 됩니다.결론은, tempNode 와 head 가 같은 주소를 참조하고 있더라도, tempNode 는 계속 해서 가리키는 메모리 주소만 변경되는 것이지, head 가 가리키는 메모리 주소를 변경시키고 있는 행위는 아닙니다. 도움이 되셨길 바랍니다.

커린이 · Answer

junior123 너무 감사합니다. junior123 님이 써주신 글을 이해하기에 전에 잘못알고 있던 부분이있어서 증명하느라 좀 늦었습니다. ㅎㅎ 덕분에 궁금중이 해결되었어요 너무 감사드립니다. 혹시나 저의 확신을 위해서 제가 설명 하나만 드려도 될 까요?! head 는 일반적인 데이터 타입이고 tempNode 참조타입의 변수 이기에 참조타임의 참조 주소가 달라지더라도 일반적인 데이터 타입의 head는 데이터가 변하지 않는다 라고 생각하면 될까요? ㅎㅎ

junior123 · Answer

tempNode 가 참조 타입의 변수이고, head도 참조 타입의 변수입니다.ListNode tempNode &#61; head;그렇기에 tempNode가 head와 같은 메모리 주소를 가리키고 있습니다.while(tempNode.link !&#61; null) { tempNode &#61; tempNode.link; // 다음 노드를 참조 }이 행위를 한다면, tempNode는 head를 가리키는 화살표를 끊고, head.link를 가리킵니다.쉽게 나타내자면tempNode -> head 메모리주소tempNode -> head.link 메모리주소tempNode -> link.link 메모리주소tempNode -> link.link 메모리주소를 가리키게 됩니다.단순히 가리키는 화살표만 바꾸고 있다고 생각하시면 될거 같아요좀 깊게 파시려면 JVM과 GC를 공부하시면 좋을 것 같습니다!^^저도 잘 모르지만 답변 남겨봅니다.

linkedList 에 대해서 궁금해요

5개의 답변

Q&A 목록