- 노드 개수 카운팅하는 메소드
public int countNode() {
ListNode current = head;
int count = 0;
while(current != null){
current = current.link; // current = current.nextNode
count++;
}
return count;
}솔직히.... 진짜 느낌대로 짠 코드라 잘 짰는진 모르겠지만 current가 head를 참조하게 한 뒤에 current 가 null값이 되기 전까지 count 변수를 증가시킨다.
// L = (빨강, 주황, 노랑, 초록, 파랑, 남색, 보라)
int counting;
counting = L.countNode();
for(int i = 0; i < counting; i++) {
L.deleteLastNode();
}
L.insertLastNode("빨강");
L.insertLastNode("주황");
L.insertLastNode("노랑");
L.insertLastNode("초록");
L.insertLastNode("파랑");
L.insertLastNode("남색");
L.insertLastNode("보라");
L.printList();LinkedList L = (일, 금, 수)
노드 개수만큼 반복문 돌려서 끝에 있는 노드를 삭제하고 insertLastNode 메소드로 노드 하나씩 추가함. 교수가 insertLastNode 메소드 쓰라는데 솔직히 이게 맞나?싶음. 앞에 delete 부분도 최대한 깔끔하게 하고자 count 함수 추가 구현해서 반복문 돌린건데....
- 노드 순서 바꾸기 ................
// 무지개 리스트의 색깔을 아래와 같은 순서로 바꾸고 출력하기
// L = (노랑, 주황, 초록, 남색, 파랑, 보라, 빨강)를 연결리스트로 만들고 출력하기
/*
* 1.빨강 삭제
* 2. 노랑,주황 순서 바꾸기
* 3. 파랑,남색 순서 바꾸기
* 4. 마지막에 빨강 삽입
* 혹은
* 1. 빨강 삭제(첫번째 노드 삭제)
* 2. 주황, 파랑 차례로 삭제
* 3. 노랑 뒤에 주황, 남색 뒤에 파랑 각각 삽입
* 4. 가장 끝에 빨강 삽입
*/두가지 방법을 생각 해보았는데 생각보다 어렵다.... 첫번째 방법은 노드 3개를 이용해서 swap을 시켜야하고 .. 그 전에 바꾸고 싶은 특정 노드의 인덱스 혹은 link를 찾는 함수도 추가적으로 구현 해야한다. 교수님께서 reverse 시킬 때 사용하는 논리를 잘 응용 해보라고 하셨다.
public ListNode searchNode(String data){
ListNode temp = this.head;
while(temp!=null){
if(data == temp.getData()) return temp;
else temp = temp.link;
}
return temp;
}이건 특정 data 값을 갖는 노드를 찾는 메소드다. 얘는 쉬운데 문제는..... link값을 활용해서 tmp라는 새로운 null 노드를 만들고 흔히들 하는 swap 과정을 실행시킨 뒤에 노드를 연결시키면 짜잔~하고 성공할 줄 알았다. 그치만 생각보다 안풀린다. 아직도 성공 못함. A와 B의 순서를 바꾼다고 하면 B의 주소 즉 위치는 A.link로 찾을 수 있는데 이렇게 찾는다고 해도 link값만 바뀌지 data값은 여전히 그대로다. 심지어 바꾼 link값을 토대로 다시금 리스트를 연결 시켜야함. 이 부분 구현하기가 꽤나 어렵다.. 머리가 핑핑 돌고있음. 주솟값이 아닌 리스트 상의 위치, 인덱스를 리턴하는 메소드를 사용 해볼까 싶기도 하다..
만약 두번째 방법을 사용한다면 특정 노드를 삭제하는 메소드를 추가적으로 구현 해야한다. 사실 이 메소드만 구현하면 첫번째 보다는 훨씬 쉽다. 노랑과 파랑을 삭제하고 남은 노드를 연결시킨 후에 insertMiddleNode()로 다시 원하는 위치에 삽입해주면 됨. 마지막으로 insertLastNode()로 빨강까지 삽입시키고... 노드 순서바꾸기보다는 그냥 삽입과 삭제의 반복일 뿐, 비효율적인 방법이지만 이렇게라도 풀어야지 우짜겠니..
//특정 노드부터 끝까지 삭제하는 함수
public void deleteTargetToEnd(String targetData) {
ListNode pre, temp;
if(head == null) return;
if(head.link == null) head = null;
else {
pre = head;
temp = head.link;
while(temp.link != null) {
pre = temp;
temp = temp.link;
if(targetData == temp.getData())
pre.link = null;
}
}
}
특정 노드 삭제 메소드를 구현하다가 어쩌다보니 특정 노드부터 끝까지 삭제하는 메소드를 구현했다..ㅋㅋㅋㅋ 그래도 이 코드 덕분에 노드 하나만 삭제하는 것도 성공적으로 구현할 수 있었음
/*
* 특정 노드 삭제 함수 추가 구현
* 찾는 타겟 데이터와 같은 데이터를 가진 노드를 발견하면
* 그 노드를 삭제한다.
*/
public void deleteTargetNode(String targetData) {
ListNode pre, temp;
if(head == null) return;
if(head.link == null) head = null;
else {
pre = head;
temp = head.link;
while(temp.link != null) {
pre = temp;
temp = temp.link;
if(targetData == temp.getData())
pre.link = temp.link;
}
}
}요게 바로 deleteTargetNode! search() 와 deleteLastNode()를 참고했다. 둘을 적절하게 섞으면 되는데.... 계속 해서 pre와 temp를 움직여 주다가 targetData값을 만나면 pre.link를 temp.link로 연결해주면 끝! pre.link를 null로 지정하면 deleteTargetToEnd가 되는거구. . 하 뿌듯 . 단순 연결리스트에서 노드 삭제는 그 노드를 어떠한 자유 공간에 버린다는 생각보다는 삭제할 노드를 건너뛰고 그 다음 노드에 연결시킨다는 생각이 보다 구현을 쉽게할 수 있게 만드는 것 같다.
package listNode;
public class LinkedList {
private ListNode head;
public LinkedList(){
this.head = null;
}
public LinkedList(ListNode head) {
this.head = head;
}
//새로운 빈 노드 만드는 메소드
public ListNode newLinkedList() {
ListNode newNode = null;
return newNode;
}
public void insertMiddleNode(LinkedList L, ListNode pre, String data){
ListNode newNode = new ListNode(data);
if (L.head == null) {
L.head = newNode;
newNode.link = null;
}
else {
newNode.link = pre.link;
pre.link = newNode;
}
}
public void insertMiddleNode(ListNode pre, String data){
ListNode newNode = new ListNode(data);
newNode.link = pre.link;
pre.link = newNode;
}
public void insertLastNode(String data){
ListNode newNode = new ListNode(data);
if(head == null){
this.head = newNode;
}
else{
ListNode temp = head;
while(temp.link != null) temp = temp.link;
temp.link = newNode;
}
}
//첫번째 노드에 삭제 메소드 추가 구현. head
public void deleteFirstNode() {
ListNode temp = head;
//temp = temp.link;
head = head.link;
}
//특정 노드부터 끝까지 삭제하는 함수
public void deleteTargetToEnd(String targetData) {
ListNode pre, temp;
if(head == null) return;
if(head.link == null) head = null;
else {
pre = head;
temp = head.link;
while(temp.link != null) {
pre = temp;
temp = temp.link;
if(targetData == temp.getData())
pre.link = null;
}
}
}
/*
* 특정 노드 삭제 함수 추가 구현
* 찾는 타겟 데이터와 같은 데이터를 가진 노드를 발견하면
* 그 노드를 삭제한다.
*/
public void deleteTargetNode(String targetData) {
ListNode pre, temp;
if(head == null) return;
if(head.link == null) head = null;
else {
pre = head;
temp = head.link;
while(temp.link != null) {
pre = temp;
temp = temp.link;
if(targetData == temp.getData())
pre.link = temp.link;
}
}
}
public void deleteLastNode(){
ListNode pre, temp;
if(head == null) return;
if(head.link == null) {
head = null;
}
else {
pre = head;
temp = head.link;
while(temp.link != null) {
pre = temp;
temp = temp.link;
}
pre.link = null;
}
}
public ListNode searchNode(String data){
ListNode temp = this.head;
while(temp!=null){
if(data == temp.getData()) return temp;
else temp = temp.link;
}
return temp;
}
//리스트 노드 개수 세는 함수 추가 구현.
public int countNode() {
ListNode current = head;
int count = 0;
while(current != null){
current = current.link; // current = current.nextNode
count++;
}
return count;
}
public void reverseList(){
ListNode next = head;
ListNode current = null;
ListNode pre = null;
while(next != null) {
pre = current;
current = next;
next = next.link;
current.link = pre;
}
head = current;
}
public void printList(){
ListNode temp = this.head;
System.out.printf("L = (");
while(temp != null){
System.out.printf(temp.getData());
temp = temp.link;
if(temp != null){
System.out.printf(", ");
}
}
System.out.println(")");
}
}
package listNode;
public class ch_06_2 {
static LinkedList L = new LinkedList();
public static void main(String[] args) {
System.out.println("(1) 공백 리스트에 노드 3개 삽입하기");
L.insertLastNode("월");
L.insertLastNode("수");
L.insertLastNode("일");
L.printList();
System.out.println("(2) 수 노드 뒤에 금 노드 삽압하기");
ListNode pre = L.searchNode("수");
if(pre == null)
System.out.println("검색실패>>찾는 데이터가 없습니다.");
else {
L.insertMiddleNode(pre, "금");
L.printList();
}
System.out.println("(3) 리스트의 노드를 역순으로 바꾸기");
L.reverseList();
L.printList();
System.out.println("(4) 리스트의 마지막 노드 삭제하기");
L.deleteLastNode();
L.printList();
System.out.println("(5) 무지개 리스트 생성하기");
// 위 예제를 참고하여, insertLastNode 함수를 사용하여 아래 무지개 리스틀 생성하고 출력하기
// L = (빨강, 주황, 노랑, 초록, 파랑, 남색, 보라)
int counting;
counting = L.countNode();
for(int i = 0; i < counting; i++) {
L.deleteLastNode();
}
L.insertLastNode("빨강");
L.insertLastNode("주황");
L.insertLastNode("노랑");
L.insertLastNode("초록");
L.insertLastNode("파랑");
L.insertLastNode("남색");
L.insertLastNode("보라");
L.printList();
System.out.println("(6) 무지개 리스트의 색깔 순서틀 바꾸기");
// 무지개 리스트의 색깔을 아래와 같은 순서로 바꾸고 출력하기
// L = (노랑, 주황, 초록, 남색, 파랑, 보라, 빨강)를 연결리스트로 만들고 출력하기
/*
* 1.빨강 삭제
* 2. 노랑,주황 순서 바꾸기
* 3. 파랑,남색 순서 바꾸기
* 4. 마지막에 빨강 삽입
* 혹은
* 1. 빨강 삭제(첫번째 노드 삭제)
* 2. 주황, 파랑 차례로 삭제
* 3. 노랑 뒤에 주황, 남색 뒤에 파랑 각각 삽입
* 4. 가장 끝에 빨강 삽입
*/
//두번째 방법
L.deleteFirstNode();
L.deleteFirstNode();
L.deleteTargetNode("파랑");
ListNode preNode = L.searchNode("노랑");
L.insertMiddleNode(preNode, "주황");
ListNode preNode2 = L.searchNode("남색");
L.insertMiddleNode(preNode2, "파랑");
L.insertLastNode("빨강");
L.printList();
}
}
'Major > Data Structure & Algorithm' 카테고리의 다른 글
| 원형 연결 리스트 (0) | 2022.04.16 |
|---|---|
| 이중 연결 리스트의 삽입, 삭제 + (다항식 연산 ) (0) | 2022.04.13 |
| [JAVA] 연결리스트, 노드, 삽입 및 삭제 (0) | 2022.04.03 |
| [python+]연결리스트,노드,삽입,삭제 (0) | 2022.04.02 |
| 배열 순차 자료구조, 선형 리스트, 다항식의 순차 자료구조 (0) | 2022.03.20 |