선형데이터구조, 연결리스트(LinkedList) #8 이중 연결리스트(Doubly LinkedList)

이전글

https://yonghwankim-dev.tistory.com/184

선형데이터구조, 연결리스트(LinkedList) #7 반복자(Iterator)

 

개요

이전글에서는 연결리스트를 순회하기 위한 반복자(Iterator)를 구현하였습니다. 이번글에서는 Node 클래스에 prev 포인터를 추가한 이중 연결 리스트를 구현하도록 하겠습니다.

 

1. 단순 연결리스트의 문제점

단순 연결리스트에서 removeLast 메서드를 보면 tail 포인터가 있는데도 불구하고 O(n) 시간복잡도를 소요하는 것을 볼 수 있습니다. 이유는 마지막 노드가 앞의 노드를 가리킬 수 없기 때문입니다. 그림으로 표현하면 아래와 같습니다.

위 그림과 같이 예를 들어 removeLast 메소드를 호출했다고 가정할 때, tail 포인터에서 "C" 노드에 접근이 가능한 방법이 없습니다. 따라서 기존 removeLast 메소드는 마지막 노드를 제거하기 위해서 previous, current 포인터를 활용하여 연결리스트를 순회하고 제거 작업을 수행하는 것입니다. 이 순회하는 과정에서 시간 복잡도 O(n)을 소모하게 되는 것입니다.

 

따라서 이러한 문제점을 해결하기 위해서 이중 연결리스트를 활용하여 문제를 해결 할 수 있습니다.

2. 이중 연결리스트의 구현

이중 연결리스트는 Node 클래스가 기존 Node 클래스에 더하여 prev 포인터를 가지고 있는 연결리스트입니다. 이중 연결리스트를 그림으로 표현하면 아래와 같습니다.

addFirst 메서드 개선

	@Override
	public void addFirst(E data) {
		Node<E> newNode = new Node<E>(data);
		
		// 1. 경계조건, 자료구조가 비어있는 경우
		if(head==null)
		{
			tail = newNode;
		}
		else
		{
			head.prev = newNode;
		}
		
		newNode.next = head;
		head = newNode;
		currentSize++;
	}

head.prev = newNode;

위의 코드를 통하여 head에 노드가 추가될 때마다 기존 head가 가리키는 노드의 prev는 newNode를 가리키도록 합니다. addFirst 메서드의 수행과정을 그림으로 표현하면 아래와 같습니다.

1. head.prev = newNode;
2. newNode.next = head;
3. head = newNode;

 

addLast 메서드 개선

	@Override
	public void addLast(E data) {
		
		Node<E> newNode = new Node<E>(data);
		// 1. 경계조건, 자료구조가 비어있는 경우
		if(head==null)
		{
			head = tail = newNode;
			currentSize++;
			return;
		}
		else
		{
			newNode.prev = tail;
		}
		
		tail.next = newNode;		
		tail = newNode;
		
		currentSize++;
	}

newNode.prev = tail;

위의 코드를 통하여 이중 연결리스트의 노드수가 1개 이상일때 addLast 메서드 호출시 새로운 노드(newNode)의 prev 포인터는 기존 tail이 가리키는 노드를 가리킵니다. 그림으로 표현하면 아래와 같습니다.

위 그림의 addLast 메서드 수행과정을 코드로 표현하면 아래와 같습니다.

1. newNode.prev = tail;
2. tail.next = newNode;
3. tail = newNode;

 

removeFirst 메서드 개선

	@Override
	public E removeFirst() {
		// 경계조건 1. Empty, 자료구조가 비어있는 경우
		if(head==null)
		{
			return null;
		}
		
		E delData = head.data;
		
		// 경계조건 2. Single Element, 삭제할 노드가 단 하나남은 노드인 경우 
		// head, tail은 null을 가리키도록 함
		if(head==tail)
		{
			head = tail = null;
		}
		else
		{
			head = head.next;
			head.prev = null;
		}
		
		currentSize--;
		
		return delData;
	}

head.prev = null;

위 코드를 통하여 이중 연결리스트의 노드 개수가 1개 이상일때 removeFirst 메소드로 인하여 head가 가리키는 노드가 제거된다면 head.next 포인터가 가리키는 노드의 prev 포인터는 아직 head를 가리키고 있습니다. 따라서 head.prev 포인터를 null로 저장하여 규칙을 유지시킵니다. 위 과정을 그림으로 표현하면 아래와 같습니다.

위 그림의 수행과정을 코드로 표현하면 아래와 같습니다.

1. head = head.next;
2. head.prev = null;

 

removeLast 메서드 개선

	@Override
	public E removeLast() {
		// 경계조건 1. Empty, 자료구조가 비어있는 경우
		if(head==null)
		{
			return null;
		}
		
		// 경계조건 2. Single Element, 자료구조에서 요소가 하나 있는 경우
		if(head==tail)
		{
			return removeFirst();
		}
		
		E delVal = tail.data;
		tail.prev.next = null;
		tail = tail.prev;
		
		currentSize--;
		
		return delVal;
		
	}

E delVal = tail.data;
tail.prev.next = null;
tail = tail.prev;

기존 단순 연결리스트에서는 마지막 노드와 마지막 노드의 이전 노드를 찾기 위해 current, previous 포인터를 사용하여 순회를 한 것에 비하여 이중 연결리스트에서는 tail 포인터만으로 removeLast 메소드 수행을 할 수 있습니다. 위 코드를 통하여 기존 O(n) 시간 복잡도가 소요된데 반해 이중 연결리스트의 removeLast 메소드는 O(1) 시간밖에 안걸린다는 것을 알 수 있습니다. 위 수행과정을 그림으로 표현하면 아래와 같습니다.

위 그림의 수행과정을 코드로 표현하면 아래와 같습니다.

1. tail.prev.next = null;
2. tail = tail.prev;

 

remove 메서드 개선

	@Override
	public E remove(E obj) {
		Node<E> current=head, previous=null;
		
		// 경계 조건 Empty 포함
		while(current!=null)
		{
			if(((Comparable<E>)obj).compareTo(current.data)==0) // find
			{
				// 경계조건 Single Element, Beginning
				// 노드가 1개 or 첫번째 노드 제거
				if(current==head)
				{
					return removeFirst();
				}
				// 경계조건 End
				// 마지막 노드 제거
				if(current==tail)
				{
					return removeLast();
				}
				
				previous.next = current.next;	// remove
				current.next.prev = previous;
				
				currentSize--;
				return current.data;
			}
			// 찾고자 하는 요소가 아닌 경우
			previous = current;
			current = current.next;
		}
	
		return null;
	}

current.next.prev = previous;

이중 연결리스트에서 삭제될 노드를 제거할 때 삭제될 노드의 다음 노드의 prev 포인터를 previous 노드를 가리키도록 설정합니다. 위 수행과정을 그림으로 표현하면 아래와 같습니다.

위 그림의 수행과정을 코드로 표현하면 아래와 같습니다.

1. previous.next = current.next;
2. current.next.prev = previous;

 

3. 이중 연결리스트의 장단점

장점

removeLast 메서드와 같이 마지막 노드를 제거하기 위해서 연결리스트를 순회하지 않고 tail 포인터만으로 O(1) 시간에 제거가 가능합니다.

 

단점

이중 연결 리스트의 단점은 prev 포인터가 추가되기 때문에 노드를 추가하는 과정이 더 복잡해집니다. 그리고 모든 노드에 prev 포인터가 추가되므로 더 많은 메모리 공간이 필요하게 됩니다.

 

References

[부스트코스] 자바로 구현하고 배우는 자료구조