※ 원형 연결 리스트(Circular Linked List)란?
연결 리스트의 구조를 원형으로 만든것 -> 마지막 노드의 링크를 첫번째 노드에 걸어준다.
단순 연결 리스트는 이전 노드에 접근하려면 노드를 다시 처음부터 순회해야 되지만 원형 연결 리스트는 계속 순회하면 이전 노드에 접근할 수 있다.
1.원형 연결 리스트의 삽입연산
운형 연결 리스트에서의 삽입연산은 마지막 노드부분을 처음 노드와 연결하는 부분 빼고 단순 연결 리스트와 똑같다. 또한 원형 연결 리스트의 마지막 노드를 삽입하는 것이 곧 리스트의 첫 번째 노드를 삽입하는 것과 같은 의미이다.
그래서 원형 연결 리스트에서의 삽입연산은 첫 번째 노드 삽입과 중간 노드 삽입의 경우로 나눌 수 있다.
※ 구현
메인
public class Main {
public static void main(String[] args) {
CircularLinkedList list = new CircularLinkedList();
//FirstNodeInsert Test
list.FirstNodeInsert("목");
list.FirstNodeInsert("화");
list.FirstNodeInsert("월");
list.printList();
//MiddelNodeInsert Test
Node pre = list.searchNode("수");
list.middleNodeInsert("존재하지않는 노드", pre);
pre = list.searchNode("화");
list.middleNodeInsert("수", pre);
pre = list.searchNode("목");
list.middleNodeInsert("토", pre);
list.middleNodeInsert("금", pre);
list.printList();
//Node Delete Test
Node delNode = list.searchNode("일");
list.deletNode(delNode);
delNode = list.searchNode("월");
list.deletNode(delNode);
delNode = list.searchNode("수");
list.deletNode(delNode);
delNode = list.searchNode("토");
list.deletNode(delNode);
list.printList();
//Node Reverse Test
System.out.println("**Reverse List**");
list.reverseList();
list.printList();
}
}
노드
public class Node {
private String data;
public Node link;
public Node(){
this.data = null;
this.link = null;
}
public Node(String data) {
// TODO Auto-generated constructor stub
this.data = data;
}
public Node(String data, Node link){
this.data = data;
this.link = link;
}
public String getData( ){
return this.data;
}
}
연결리스트
public class CircularLinkedList {
private Node head;
public CircularLinkedList() {
// TODO Auto-generated constructor stub
this.head = null;
}
public void printList(){
if(head ==null){
System.out.println("길이가 0인 리스트");
return;
}
Node temp = head;
int idx = 1;
//길이가 1인 리스트
if(temp.link ==temp){
System.out.println("index : " + idx + " data : " + temp.getData());
}else{
while(temp.link != head){
System.out.println("index : " + idx + " data : " + temp.getData());
temp = temp.link;
idx++;
}
System.out.println("index : " + idx + " data : " + temp.getData());
}
}
public void FirstNodeInsert(String data){
Node insertNode = new Node(data);
if(this.head == null){
head=insertNode;
insertNode.link = insertNode;
}else{
Node temp = head;
insertNode.link = head;
while(temp.link != head){
temp = temp.link;
}
temp.link = insertNode;
head = insertNode;
}
}
public Node searchNode(String data){
Node searchNode = new Node();
searchNode = head;
//middleNode Insert
while(searchNode.link != head){
if(searchNode.getData().equals(data)){
return searchNode;
}else{
searchNode = searchNode.link;
}
}
//lastNode Insert
if(searchNode.getData().equals(data)){
return searchNode;
}else{
//Not Exist Node
System.out.println("찾는 데이터 없음");
return null;
}
}
public void middleNodeInsert(String data, Node pre){
Node insertNode = new Node(data);
//head is null
if(head == null){
head = insertNode;
insertNode.link = insertNode;
}else{
Node temp = head;
//middle node insert
while(temp.link !=head){
if(pre == temp){
insertNode.link=pre.link;
pre.link = insertNode;
return;
}else{
temp = temp.link;
}
}
//last node insert
if(temp==pre){
insertNode.link = pre.link;
pre.link = insertNode;
return;
}else{
//not exist node
System.out.println("pre 노드가 존재하지 않습니다.");
}
}
}
public void deletNode(Node deleteNode){
Node temp = head;
//FirstList Del
if(temp == deleteNode){
Node headNode = head;
head = headNode.link;
while(temp.link != headNode){
temp = temp.link;
}
temp.link= head;
}else{
// MiddelList Del
Node preNode =temp;
while(temp.link != head){
if(temp.link == deleteNode){
temp.link = deleteNode.link;
deleteNode.link=null;
return;
}else{
preNode =temp;
temp=temp.link;
}
}
if(temp == deleteNode){
//LastList Del
preNode.link =head;
deleteNode.link =null;
}else{
//Not Exist Node
System.out.println("해당 노드가 없음");
return;
}
}
}
public void reverseList(){
Node pre = null;
Node current = null;
Node next= head;
Node headNode = head;
if(next.link == head){
System.out.println("리스트의 길이가 1입니다. reverse할 길이가 안됩니다.");
return;
}else if(head == null){
System.out.println("리스트의 길이가 0입니다. reverse할 길이가 안됩니다.");
return;
}
while(next.link != head){
pre = current;
current = next;
next = next.link;
current.link = pre;
}
//head setting
pre = current;
current = next;
current.link = pre;
headNode.link = current;
head = current;
}
}
'플밍 is 뭔들 > 자료구조' 카테고리의 다른 글
| 03-1 스택 (0) | 2016.11.25 |
|---|---|
| 02-4 이중 연결 리스트 (0) | 2016.11.25 |
| 02-2 단순 연결 리스트 (0) | 2016.11.25 |
| 02-1 연결 자료구조 방식 (0) | 2016.11.25 |
| 01-3 행열의 순차 자료구조 표현 (0) | 2016.11.25 |
