원형 이중 연결 리스트 데이터 추가, 삭제하는 방법

목록 끝이나 빈 리스트에 삽입

public class CircularDoublyLinkedList {
	static Node start;
	public static void main(String[] args) {
		insertEnd(1);
		insertEnd(2);
		insertEnd(3);
		printList(start);
	}
	
	static void insertEnd(int data) {
		Node newNode = new Node(data);
		
		if(start == null) {
			newNode.next = newNode.prev = newNode;
			start = newNode;
			return;
		}
		
		Node last = start.prev;
		newNode.next = start;
		newNode.prev = last;
		last.next = newNode;
		start.prev = newNode;
	}
	
	static class Node {
		int data;
		Node next;
		Node prev;
		
		Node(int data) {
			this.data = data;
		}
	}
	
	static void printList(Node n) {
		if(start == null) return;
		
		do {
			System.out.println(n.data);
			n = n.next;		
		} while(start != n);
	}
}

 

빈 리스트일대는 next와 prev가 모두 자기 자신이여야되고 start도 새 노드로 변경해야합니다.

리스트가 비어있지 않으면 start의 prev가 마지막 노드여서 위와 같이 작업해주면 됩니다.

리스트 시작 위치에 삽입

static void insertBegin(int data) {
    if(start == null) {
        insertEnd(data);
    } else {
        Node last = start.prev;
        Node newNode = new Node(data);
        newNode.next = start;
        newNode.prev = last;
        last.next = start.prev = newNode;
        start = newNode;
    }			
}

리스트가 비어있을 경우 insertEnd를 호출하여 추가하여 주고 아니면 노드를 새로 만들고 위와 같이 작업해주면 됩니다.

리스트 중간 위치에 삽입

static void insertAfter(int data, int target) {
    Node newNode = null;
    Node search = start;
    do {
        if(search.data == target) {
            newNode = new Node(data);
            Node next = search.next;

            next.prev = newNode;
            search.next = newNode;

            newNode.next = next;
            newNode.prev = search;
            return;
        }
        search = search.next;
    } while(search != start);

    if(newNode == null) System.out.println("no target");			
}

추가할 data와 target를 받아서 target 위치 뒤에 data를 추가합니다.

 

원형 이중 리스트 데이터 삭제

static void deleteNode(int target) {
    Node search = start;
    do {
        if(search.data == target) {
            Node next = search.next;
            Node prev = search.prev;

            next.prev = prev;
            prev.next = next;
            if(next == search &&  prev == search) start = null;
            else if(start == search) start = next;

            return;
        }
        search = search.next;
    } while(search != start);
}

특정 값을 가지는 노드를 찾아 삭제하는 구현입니다. 현재 노드가 유일한 경우 start를 null로 설정하고 삭제하는 노드가 start 노드일 경우 next 노드로 수정합니다.