원형 단일 연결 리스트 데이터 추가, 삭하는 방법 구현

원형 단일 연결 리스트 데이터 추가

원형 연결 리스트를 구현할려면 마지막 노드를 가리키는 외부 포인터를 사용합니다. 마지막 노드를 가리키는 포인터 last의 next는 첫번째 노드를 가리킬 것입니다.

 

첫 번째 노드가 아닌 마지막 노드를 가리키는 포인터 사용 이유

첫 번째 노드에 추가하려면 전체 리스트를 탐색해야됩니다. 마지막 노드에 추가하려해도 전체 리스트 탐색해야합니다.

start 포인터 대신 last 포인터를 사요하면 위 두 경우 전체 목록을 탐색할 필요가 없습니다.

 

빈 리스트에 데이터 추가

빈 리스트에 추가 후 last 포인터는 새로 추가된 노드를 가리킵니다. 새 노드는 첫 번째이자 마지막 노드입니다.

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

탐색할 때 노드가 last가 다시 나오면 종료되어야 되기 때문에 do while문으로 하였습니다.

 

시작 부분에 추가

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

 

리스트 끝에 추가

static void addEnd(int data) {
    if(last == null) {
        addToEmpty(data);
        return;
    }

    Node newNode = new Node(data);
    newNode.next = last.next;
    last.next = newNode;
    last = newNode;
}

 

리스트 중간에 추가

static void addAfter(int data, int item) {
    if(last == null) return;

    Node n = last;
    do {
        if(n.data == item) {
            Node newNode = new Node(data);
            newNode.next = n.next;
            n.next = newNode;
            return;
        }
        n = n.next;
    } while(n != last);
}

주어진 item에 해당하는 노드를 찾은 다음에 data를 next로 둡니다.

 

원형 단일 리스트 노드 삭제

static void deleteNode(int del) {
    if(last == null) return;

    Node n = last.next;
    Node prev = last;
    do {
        if(n.data == del) {
            prev.next = n.next;
            if(n == last) {
                if(n == prev) {
                    last = null;
                } else {
                    last = prev;
                }
            }
            return;
        }
        prev = n;
        n = n.next;
    } while(n != last.next);
}

next로 처음부터 검사하여 prev를 생성할 수 있게 합니다.

지워질 데이터가 마지막에 있으면 last 포인터를 prev로 바꾸고 만약 리스트에 1개밖에 없으면 last 포인터를 null로 합니다.