🧑🏻‍💻 Doubly Linked List 직접 구현 with dummy head & dummy tail (JAVA)

 

https://ming412.tistory.com/167

🧑🏻‍💻 Doubly Linked List 직접 구현 (JAVA)

dummy node를 사용하지 않고 Doubly Linked List를 구현하는 방법은 위 글에 자세히 적어놓았다.

 

이번에는 dummy node를 사용해서 간단히 search, add, remove 메서드를 구현하고,

dummy node를 사용했을 때의 장단점에 대해 알아보자.

 

1. Doubly Linked List 직접 구현 (with. dummy head & dummy tail)

1) ADT (Abstract Data Type) 정의

- 데이터 (Data)

    - Node

        - data: 데이터

        - prev: 이전 노드를 참조

        - next: 다음 노드를 참조

    - MyDoublyLinkedList

        - dHead: 연결 리스트의 처음 위치에 dummy head 노드를 참조

        - dTail: 연결 리스트의 마지막 위치에 dummy tail 노드를 참조

        - size: 연결 리스트의 길이

 

- 작업 

    - search(idx): 특정 위치의 노드 반환

    - add(idx, e): 특정 위치에 요소 추가

    - remove(idx): 특정 위치의 요소 삭제

 

2) Node 클래스 정의

Node 클래스는 dummy node를 사용하지 않고 Doubly Linked List를 구현할 때와 동일하다.

public class Node<E> {
	public E data;
	public Node<E> prev;
	public Node<E> next;

	public Node(E data) {
		this.data = data;
		this.prev = null;
		this.next = null;
	}
}

 

3) DoublyLinkedList 클래스 정의

dummy node를 사용하지 않았을 때는 `head`와 `tail`을 가지고 있었지만, 지금은 `dHead`와 `dTail`을 가지고 있다.

`head`와 `dHead`, 그리고 `tail`과 `dTail`의 차이점은 아래와 같다.

 

`head`: 실제 첫 노드

`dHead`: 연결 리스트의 처음 위치에 있는 노드로, 유의미한 값을 가지고 있는 첫 노드는 `dHead.next`

 

`tail`: 실제 마지막 노드

`dTail`: 연결 리스트의 마지막 위치에 있는 노드로, 유의미한 값을 가지고 있는 마지막 노드는 `dTail.prev`

public class DoublyLinkedList<E> {
	private Node<E> dHead; // dummyHead
	private Node<E> dTail; // dummyTail
	private int size;

	public DoublyLinkedList() {
		this.dHead = new Node<>();
		this.dTail = new Node<>();
		dHead.next = dTail;
		dTail.prev = dHead;
	}
}

 

4) search 구현

찾고자 하는 노드(`idx`)가 연결 리스트의 앞 부분에 존재하는지 or 뒷 부분에 존재하는지로 구분한다.

앞 부분에 존재하면 `dHead`부터 순서대로 탐색하고, 뒷 부분에 존재하면 `dTail`부터 역순으로 탐색한다.

public Node<E> search(int idx) {
    if (size < idx) {
        throw new IndexOutOfBoundsException();
    }
    Node<E> cur;
    if (idx < size/2) {
        cur = dHead;
        for (int i=-1; i<idx; i++) {
            cur = cur.next;
        }
    } else {
        cur = dTail;
        for (int i=size; i>idx; i--) {
            cur = cur.prev;
        }
    }
    return cur;
}

 

5) add 구현

dummy node를 사용하지 않았을 때는,

새로운 노드를 추가하고자 하는 위치(`idx`)가 0일 때(=맨 처음), `size`일 때(=맨 끝), 둘 다 아닐 때(=중간 위치)로 구분했다.

 

하지만 dummy node를 사용하면, 연결리스트에 항상 `dHead`와 `dTail` 노드가 존재하므로 별도의 조건문 없이 일괄적으로 처리할 수 있다.

public void add(int idx, E data) {
    if (idx < 0 || idx > size) {
        throw new IndexOutOfBoundsException();
    }
    Node<E> newNode = new Node<>(data);
    Node<E> targetNode = search(idx);

    // targetNode와 targetNode의 바로 앞 노드 사이에 newNode를 끼워넣는 것
    newNode.next = targetNode; // newNode 다음에 targetNode 연결
    newNode.prev = targetNode.prev; // newNode와 targetNode 앞 노드 연결

    targetNode.prev.next = newNode; // targetNode의 앞 노드와 newNode 연결
    targetNode.prev = newNode; // targetNode 앞 노드를 newNode로 갱신

    size++;
}

 

6) remove 구현

마찬가지로, 맨 처음 노드를 삭제하는지 마지막 노드를 삭제하는지 중간 노드를 삭제하는지에 따라 분기할 필요가 없다.

 

연결 리스트에서 노드를 삭제한다는 것은 연결을 끊어 고립시키는 것이라고 했다.

따라서 삭제할 노드의 이전 노드와 삭제할 노드의 다음 노드를 서로 연결시켜 `targetNode`를 고립시키도록 구현했다.

public void remove(int idx) {
    if (idx < 0 || idx > size) {
        throw new IndexOutOfBoundsException();
    }
    Node<E> targetNode = search(idx); // 삭제할 노드
    // 삭제할 노드의 이전 노드와 삭제할 노드의 다음 노드를 서로 연결 (삭제할 노드 고립)
    targetNode.prev.next = targetNode.next; 
    targetNode.next.prev = targetNode.prev;

    size--;
}

 

7) 전체 코드

public class DoublyLinkedList<E> {
	private Node<E> dHead; // dummyHead
	private Node<E> dTail; // dummyTail
	private int size;

	public DoublyLinkedList() {
		this.dHead = new Node<>();
		this.dTail = new Node<>();
		dHead.next = dTail;
		dTail.prev = dHead;
	}

	public Node<E> search(int idx) {
		if (size < idx) {
			throw new IndexOutOfBoundsException();
		}
		Node<E> cur;
		if (idx < size/2) {
			cur = dHead;
			for (int i=-1; i<idx; i++) {
				cur = cur.next;
			}
		} else {
			cur = dTail;
			for (int i=size; i>idx; i--) {
				cur = cur.prev;
			}
		}
		return cur;
	}

	// dummy node를 사용하면 add 시 idx가 맨 처음/마지막일 경우 따로 분리하지 않아도 된다.
	public void add(int idx, E data) {
		if (idx < 0 || idx > size) {
			throw new IndexOutOfBoundsException();
		}
		Node<E> newNode = new Node<>(data);
		Node<E> targetNode = search(idx);

		// targetNode와 targetNode의 바로 앞 노드 사이에 newNode를 끼워넣는 것
		newNode.next = targetNode; // newNode 다음에 targetNode 연결
		newNode.prev = targetNode.prev; // newNode와 targetNode 앞 노드 연결

		targetNode.prev.next = newNode; // targetNode의 앞 노드와 newNode 연결
		targetNode.prev = newNode; // targetNode 앞 노드를 newNode로 갱신

		size++;
	}

	public void remove(int idx) {
		if (idx < 0 || idx > size) {
			throw new IndexOutOfBoundsException();
		}
		Node<E> targetNode = search(idx);
		targetNode.prev.next = targetNode.next;
		targetNode.next.prev = targetNode.prev;

		size--;
	}

	public void printAll() {
		Node<E> cur = dHead;
		System.out.print("dummy head - ");
		while (cur.next != dTail) {
			cur = cur.next;
			System.out.print(cur.data + " - ");
		}
		System.out.println("dummy tail");
	}
}

public class Main {
	public static void main(String[] args) {
		DoublyLinkedList<String> linkedList = new DoublyLinkedList<>();
		linkedList.add(0, "A");
		linkedList.add(0, "B");
		linkedList.printAll();
		linkedList.add(1, "C");
		linkedList.add(1, "D");
		linkedList.printAll();
		linkedList.add(4, "E");
		linkedList.printAll();

		System.out.println(linkedList.search(1).data);

		linkedList.remove(3);
		linkedList.printAll();
		linkedList.remove(0);
		linkedList.printAll();
	}
}

실행 결과

 

2. dummy node를 사용했을 때의 장단점

장점

- 노드를 추가하거나 제거할 때 별도의 조건문 없이 일관된 방식으로 연산을 수행할 수 있다.

- 특별한 경우(ex. 리스트가 비어있을 때)를 처리할 필요가 없으므로 버그 발생 가능성이 줄어든다.

 

단점

- 더미 노드들도 메모리를 사용하기 때문에 메모리 오버헤드가 발생한다.

- 의미 있는 값이 아닌 더미 값이 실제 데이터와 함께 연결 리스트에 존재하므로 헷갈릴 수 있다.