[ORACLEJAVA Community,오라클자바커뮤니티강좌입니다]자바로구현한 원형연결리스트(Circular Linked List) 예제

원형연결리스트는 마지막 노드가 다시 처음 노드를 가리키는 형태이다.

header Node를 별도로 두어 시작 노드를 가리키게 할수도 있고, 아닐수도 
있는데, 헤드노드를 두는 이유는 없는 노드를 찾을때 무한루트로
빠지지 않게 하기 위해서이다.

아래에는 헤드노드를 별도의 노드로 두어 이용한 것과 아닌 2가지 예제이니
참조 바랍니다.

//CircularLinkedList Example
//시작노드를 가리키는 별도의 빈headerNode를 둠,,,
class CircularListNode {
    Object data;
    CircularListNode next;   
}

public class CircularList {
    private CircularListNode headerNode;

public CircularList() {
headerNode = new CircularListNode();
        headerNode.next = headerNode;
}

    public synchronized void insert(Object data) {
        CircularListNode tn = new CircularListNode();
        tn.data = data;
//맨처음 insert되는 경우
if (headerNode.next == headerNode) {
            tn.next = headerNode;
            headerNode.next = tn;
        } else {                         
    //마지막 노드를 찾는다.(headerNode 이전의 노드)
CircularListNode p = findPrev(data);
            tn.next = headerNode;
            p.next = tn;
        }
    }

    public synchronized void delete(Object data) {
        CircularListNode prev = findPrev(data);
CircularListNode p = prev.next;

        if (prev.data.toString().equals(p.data.toString()) && p.next == headerNode) {
headerNode.next = headerNode;
headerNode.data = null;
 return;
}
prev.next = p.next;
    }

private CircularListNode findPrev(Object data) {
headerNode.data = data;
        CircularListNode p = headerNode.next;
        do {
if (p.next.data.toString().equals(data.toString())) return p;
            p = p.next;
        } while (p != headerNode);
        throw new IllegalArgumentException();
    }

       
public String toString() {
StringBuffer sb = new StringBuffer("[");
CircularListNode p = headerNode.next;
if (p != null) {
  do {
if (p.data == null) sb.append(" ");
else sb.append(" " + p.data.toString());
p = p.next;
if (p != headerNode) sb.append(",");
  } while (p != headerNode);
}
sb.append(" ]");
return sb.toString();
}
}

class Main {
    public static void main(String[] args) {
CircularList names = new CircularList();

names.insert(new String("Scott"));
names.insert(new String("Tiger"));
names.insert(new String("Swan"));
System.out.println(names);

// Delete item
names.delete(new String("Swan"));
System.out.println(names);

    names.delete(new String("Tiger"));
System.out.println(names);

names.delete(new String("Scott"));
System.out.println(names);
}
}


------------------------------------------------------------------------------


//CircularLinkedList Example
//시작노드를 가리키는 별도의 빈headerNode를 두지않고,
//맨처음 노드를 headerNode라고 지칭.
class CircularListNode {
    Object data;
    CircularListNode next;   
}

public class CircularList {
    private CircularListNode headerNode;

    public synchronized void insert(Object data) {
        CircularListNode tn = new CircularListNode();
        tn.data = data;
//맨처음 insert되는 경우
if (headerNode == null) {
            tn.next = tn;
            headerNode = tn;
        } else {                         
    //headerNode가 가리키는것 이전까지 찾는다.
CircularListNode p = findPrev(headerNode.data);
            tn.next = headerNode;
            p.next = tn;
        }
    }

    public synchronized void delete(Object data) {
        CircularListNode prev = findPrev(data);
CircularListNode p = prev.next;

        if (p == p.next) {  // Last Object on the list
headerNode = null;
 return;
}
prev.next = p.next;
//맨앞의 노드가 지워지는 경우엔 headerNode를 다시 set
if (headerNode == p) headerNode = p.next;
    }

//주어진 data노드의 이전노드를 Return
    private CircularListNode findPrev(Object data) {
headerNode.data = data;
        CircularListNode p = headerNode;
        if (p == null)
            throw new IllegalArgumentException();
        do {
if (p.next.data.toString().equals(data.toString())) return p;
            p = p.next;
        } while (p != headerNode);
        throw new IllegalArgumentException();
    }
 
public String toString() {
StringBuffer sb = new StringBuffer("[");
CircularListNode p = headerNode;
if (p != null) {
  do {
if (p.data == null) sb.append(" null");
else sb.append(" " + p.data.toString());
p = p.next;
if (p != headerNode) sb.append(",");
  } while (p != headerNode);
}
sb.append(" ]");
return sb.toString();
}
}


class Main {
    public static void main(String[] args) {
CircularList names = new CircularList();

names.insert(new String("Scott"));
names.insert(new String("Tiger"));
names.insert(new String("Swan"));
System.out.println(names);

// Delete item
names.delete(new String("Scott"));
System.out.println(names);

names.delete(new String("Tiger"));
System.out.println(names);

names.delete(new String("Swan"));
System.out.println(names);
}
}

[출처] 오라클자바커뮤니티 - http://www.oraclejavanew.kr/bbs/board.php?bo_table=LecJavaAlgorithm&wr_id=67