* 원형 연결 리스트 (Circular Linked List)
- 단순 연결 리스트에서 마지막 노드가 리스트의 첫 번째 노드를 가리키게 하여 리스트의 구조를 원형으로 만든 리스트
단순 연결 리스트는 현재노드에서 이전 노드를 접근 하려면 현재 위치에 상관없이 항상 리스트의 첫번째 노드부터 시작
그러나, 원형 연결 리스트는 마지막 노드와 첫번째 노드가 연결되어 링크를 따라 순회하면 이전 노드에 접근 가능
* 원형 연결 리스트는 마지막에 노드를 삽입하는 것이 곧 리스트의 첫 번째에 노드를 삽입하는 것과 같은 의미를 가짐
[ 삽입연산 ]
if 리스트가 비어있는 경우 (CL==null)
삽입하는 노드가 리스트의 첫번째 노드이자 마지막노드
1. 리스트에 새로운 노드를 추가하고, 첫번째 노드로 지정
2. 새 노드의 next가 자기 자신을 가리키게 하여 원형 연결 리스트 만듬
else 리스트가 비어있지 않은 경우 (CL!=null)
단순연결 리스트에서의 마지막 노드 삽입 연산 과정과 유사
1. current = CL 첫 번째 노드에 대한 참조값을 임시 변수에 저장
2. while(current.next != CL) 마지막 노드까지 이동
3. new.next = CL 마지막 노드가 가리키는 첫번째 노드를 새로운 노드가 가리키게 하고,
CL = new 리스트의 첫번째 노드를 새로운 노드로 만듬
4. current.next = new 마지막 노드가 새로운 노드를 가리키게 함
[ 삭제연산 ]
if 리스트가 비어있는 경우 (CL==null)
오류 메세지 출력, return
else 리스트가 비어있지 않은 경우 (CL!=null)
1. 두개의 변수 prev, current 를 두어 각각 삭제할 노드의 이전노드, 삭제할 노드를 가리키게 함
2. while(current.data != "찾으려는 값") 삭제하려는 노드를 찾음
3. prev.next = current.next prev가 삭제하려는 노드 current의 next를 가리키게함
4. CL = current.next 만약 삭제하려는 노드가 첫번째 노드라면 삭제하려는 노드의 다음 노드를 CL이 가리키게함
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | Test.java package CircularLinkedList; public class Test { public static void main(String[] args) { CircularList list = new CircularList(); System.out.println("(1) 공백 리스트에 노드 3개 삽입하기"); list.insertLastNode("월"); list.insertLastNode("수"); list.insertLastNode("일"); list.printList(); System.out.println("(2) \"수\"노드 뒤에 \"금\" 노드 삽입하기"); ListNode pre = list.searchNode("수"); if(pre==null){ System.out.println("검색 실패 >> 찾는 데이터가 없습니다."); }else{ list.insertMiddleNode(pre, "금"); } list.printList(); System.out.println("(3) 리스트의 첫번째에 노드 추가하기"); list.insertFirstNode("토"); list.printList(); System.out.println("(4) 리스트의 마지막 노드 삭제하기"); list.deleteLastNode(); list.printList(); System.out.println("(5) 리스트의 중간 노드 \"수\" 삭제하기"); list.deleteMiddleNode("수"); list.printList(); System.out.println("(6) 리스트의 첫번째 노드 삭제하기"); list.deleteFirstNode(); list.printList(); } } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | ListNode.java package CircularLinkedList; public class ListNode { String data; ListNode next; public ListNode(){ this.data = null; this.next = null; } public ListNode(String data){ this.data = data; this.next = null; } public ListNode(String data, ListNode next){ this.data = data; this.next = next; this.next = null; } public String getData(){ return this.data; } } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 | CircularList.java package CircularLinkedList; public class CircularList { private ListNode CL; public CircularList() { this.CL = null; } //마지막 노드에 삽입 void insertLastNode(String str){ ListNode node = new ListNode(str); if(CL == null){ CL = node; node.next = node; }else{ ListNode current = CL; while(current.next!=CL){ current = current.next; } node.next = current.next; current.next = node; } } //첫번째 노드에 삽입 void insertFirstNode(String str){ ListNode node = new ListNode(str); if(CL == null){ CL = node; }else{ ListNode current = CL; while(current.next!=CL){ current = current.next; } node.next = current.next; current.next = node; CL = node; } } //중간 노드에 삽입 void insertMiddleNode(ListNode pre, String str){ ListNode node = new ListNode(str); if(CL == null){ CL = node; }else{ ListNode current = CL; while(current.next!=pre){ current = current.next; } current = current.next; node.next = current.next; current.next = node; } } //마지막 노드 삭제 void deleteLastNode(){ if(CL==null){ System.out.println("지울 노드가 존재하지 않습니다."); }else{ ListNode prev = CL; ListNode current = CL.next; while(current.next!=CL){ prev = current; current = current.next; } prev.next = current.next; } } //첫번째 노드 삭제 void deleteFirstNode(){ if(CL==null){ System.out.println("지울 노드가 존재하지 않습니다."); }else{ ListNode current = CL; while(current.next!=CL){ current = current.next; } ListNode old = current.next; CL = old.next; current.next = CL; } } //중간 노드 삭제 void deleteMiddleNode(String str){ ListNode node = new ListNode(str); if(CL==null){ System.out.println("지울 노드가 존재하지 않습니다."); }else{ ListNode prev = CL; ListNode current = CL.next; while(current.data!=node.data){ prev = current; current = current.next; } prev.next = current.next; } } ListNode searchNode(String str){ ListNode node = new ListNode(str); if(CL==null){ System.out.println("노드가 비어있습니다."); return null; }else{ ListNode current = CL; while(current.data!=node.data){ current = current.next; } return current; } } void printList(){ if(CL==null){ System.out.println("출력할 리스트가 존재하지 않습니다."); }else{ ListNode current = CL; System.out.print("["); while(current.next!=CL){ System.out.print(current.data + " "); current = current.next; } System.out.print(current.data); System.out.print("]"); System.out.println(); } } } |
'전산 기초 > 자료구조' 카테고리의 다른 글
| [자료구조/java] 스택 (Stack) - 1차원 배열, 연결리스트 구현 (0) | 2015.10.31 |
|---|---|
| [자료구조/java] 다항식의 연결 자료구조 표현 (0) | 2015.10.30 |
| [자료구조/java] 이중 연결 리스트 (Doubly Linked List) (0) | 2015.10.27 |
| [자료구조/java] 단순 연결 리스트 (Linked List) (0) | 2015.10.25 |
| [자료구조] 자료구조 시작 (0) | 2015.10.24 |
