[자료구조] 03. 이중 연결리스트

이중 연결 리스트는, 각 노드가 이전 노드와 다음 노드를 가리키는 연결리스트 입니다.

앞서 구현했던 단순연결리스트의 경우에는, 다음 노드만을 가리키기 때문에 역방향 탐색이 불가능했습니다.

이중 연결 리스트는 이런 단점을 보완하긴 했으나, 노드마다 이전 노드를 가리키는 저장 공간이 추가돼야 한다는 단점이 있습니다.

 

이중연결리스트에서 사용하는 노드 클래스입니다.

노드는 자신의 이전 노드를 가리키는 previous 가 추가되었습니다.

public class Node<E>
{
	private Node previous;
	private E value;
	private Node next;
	
	public Node(Node previous, E value, Node next)
	{
		this.previous = previous;
		this.value = value;
		this.next = next;
	}
	
	public Node getPrevious() { return previous; }
	public E getValue() { return value; }
	public Node getNext() { return next; }
	public void setPrevious(Node newPrevious) { previous = newPrevious; }
	public void setValue(E newValue) { value = newValue; }
	public void setNext(Node newNext) { next = newNext; }
}

 

이중 연결 리스트 클래스의 변수 및 생성자 등 입니다.

head 는 연결리스트의 첫 노드를 가리키며, head 는 마지막 노드를 가리킵니다.

다만 이 두 노드들은, 실제로 항목을 저장하기 위한 것이 아닌 더미 노드가 되겠습니다.

protected Node<E> head, tail;
private int size;

public DoublyLinkedList()
{
	size = 0;
	head = new Node(null, null, null);
	tail = new Node(head, null, null);
	head.setNext(tail);
}

public Node<E> getHead() { return head; }
public Node<E> getTail() { return tail; }

 

삽입 연산입니다.

노드 p 가 주어졌을 때, p 의 앞/뒤 에 새로운 노드를 만들어서 레퍼런스를 알맞게 연결시켜줍니다.

p 에서 getPrevious / getNext 등을 통해 앞뒤 원소들의 레퍼런스에 접근할 수 있습니다.

insertBefore 의 경우를 보자면, (앞 원소와 p) 를 가리키는 새로운 노드를 하나 생성합니다.

기존 p의 앞 원소의 next 레퍼런스와, p 의 previous 레퍼런스에 새롭게 생성한 노드를 추가해줍니다.

head 의 앞, tail 의 뒤에는 노드를 추가하지 않습니다.

public void insertBefore(Node p, E value)
{
	if(p == head) throw new NoSuchElementException();
	Node<E> newNode = new Node(p.getPrevious(), value, p);
	p.getPrevious().setNext(newNode);
	p.setPrevious(newNode);
	size++;
}

public void insertAfter(Node p, E value)
{
	if(p == tail) throw new NoSuchElementException();
	Node<E> newNode = new Node(p, value, p.getNext());
	p.getNext().setPrevious(newNode);
	p.setNext(newNode);
	size++;
}

 

삭제 연산입니다.

노드 p 를 받아서, p 의 앞뒤원소를 서로 연결시켜 줍니다.

앞의 원소와 뒤의 원소의 레퍼런스가 각각 서로 연결된다면, p 는 참조가 불가능해지기 때문에 가비지 콜렉터가 수거해갑니다.

public void delete(Node p)
{
	if(p == null) throw new NoSuchElementException();
	p.getPrevious().setNext(p.getNext());
	p.getNext().setPrevious(p.getPrevious());
	size--;
}

 

수행시간

이중 연결 리스트에서 수행되는 삽입이나 삭제 연산은, 단순 연결 리스트와 마찬가지로 O(1) 입니다.

탐색 연산 역시 마찬가지로 head 혹은 tail 부터 순차적으로 진행되기 때문에, O(N) 입니다.