이중 연결 리스트

---

연결 리스트의 종류는 다양하다.

그 중 하나가 바로 이중 연결 리스트(doubly linked list)이다.

전형적인 연결 리스트는 각 노드에 다음 노드를 가리키는 1개의 링크만 있었지만, 이중 연결 리스트는 이전 노드로의 링크 1개 다음 노드로의 링크 1개, 총 2개의 링크가 존재한다.

이중 연결 리스트는 아래의 이미지와 같이 표현할 수 있다.

다음 코드는 이중 연결 리스트의 노드를 자바로 구현한 것이다.

코드가 이해가 안된다면 이전에 포스팅한 연결 리스트와 효율성을 보고 오도록 하자.

public class DoublyLinkedList_Node {

	private String data;
    
	private DoublyLinkedList_Node nextNode;
    
	private DoublyLinkedList_Node previousNode;
    
	public DoublyLinkedList_Node(String data) {
		this.data = data;
	}
	public String getData() {
		return data;
	}
	public void setData(String data) {
		this.data = data;
	}
	public DoublyLinkedList_Node getnextNode() {
		return nextNode;
	}
	public void setnextNode(DoublyLinkedList_Node nextNode) {
		this.nextNode = nextNode;
	}
	public DoublyLinkedList_Node getpreviousNode() {
		return previousNode;
	}
	public void setpreviousNode(DoublyLinkedList_Node previousNode) {
		this.previousNode = previousNode;
	}		
}

public class DoublyLinkedList {
	private DoublyLinkedList_Node firstNode;
	private DoublyLinkedList_Node lastNode;
	
	public DoublyLinkedList() { firstNode = null; lastNode = null;}

	public DoublyLinkedList_Node getFirstNode() {
		return firstNode;
	}
	
	public void setFirstNode(DoublyLinkedList_Node firstNode) {
		this.firstNode = firstNode;
	}

	public DoublyLinkedList_Node getLastNode() {
		return lastNode;
	}

	public void setLastNode(DoublyLinkedList_Node lastNode) {
		this.lastNode = lastNode;
	}
    	// 이중 연결리스트 삽입 메서드
	public void insertAtEnd( String value ) {
		DoublyLinkedList_Node newNode = new DoublyLinkedList_Node(value);
		
		// 연결 리스트에 아직 원소가 없을 때
		if( firstNode == null ) {
			firstNode = newNode;
			lastNode = newNode;
		}
		// 연결 리스트에 원소가 하나 이상 있을 때
		else {
			newNode.setpreviousNode( lastNode );
			lastNode.setnextNode( newNode );
			lastNode = newNode;
		}
	}
	// 이중 연결 리스트 가장 앞 노드 삭제 메서드
	public DoublyLinkedList_Node removeFromFront() {
		DoublyLinkedList_Node removedNode = firstNode;
		firstNode = firstNode.getnextNode();
		return removedNode;
	}
		

테스트 코드로써 일시적으로 data를 String 타입으로 선언하였지만. 직접 활용하기 위해서는 제네릭으로 바꿔 선언하면 좋을 것이다.

이중 연결 리스트는 첫 노드와 마지막 노드 모두 알고 있으므로 리스트 앞과 끝에서의 읽기, 삽입, 삭제 또한 O(1)에 할 수 있다.

연결 리스트 끝에서의 삽입 연산을 아래 이미지에 따라 진행해보자.

새 노드("Sue")를 생성했다고 가정해보자. 이 노드의 previousNode가 연결 리스트의 lastNode("Greg")을 가리키도록 한다. 이어서 lastNode("Greg")의 nextNode가 새 노드("Sue")를 가리키도록 바꾼다. 마지막으로 새 노드("Sue")를 연결 리스트의 lastNode로 바꾼다.

이중 연결 리스트: 삽입 메서드 구현

---

다음은 리스트 마지막에서 새로운 노드를 삽입할 수 있는 insetAtEnd() 메서드이다. DoublyLinkedList 클래스에 추가하자.

	// 이중 연결리스트 삽입 메서드
	public void insertAtEnd( String value ) {
		DoublyLinkedList_Node newNode = new DoublyLinkedList_Node(value);
		
		// 연결 리스트에 아직 원소가 없을 때
		if( firstNode == null ) {
			firstNode = newNode;
			lastNode = newNode;
		}
		// 연결 리스트에 원소가 하나 이상 있을 때
		else {
			newNode.setpreviousNode( lastNode );
			lastNode.setnextNode( newNode );
			lastNode = newNode;
		}
	}

과정은 아래와 같다.

먼저 새 노드를 생성한다. 리스트에 원소가 없다면 첫번째 노드는 lastNode와 firstNode가 된다.
원소가 있다면 마지막 노드의 다음 노드를 새 원소로 링크한다.

이중 연결 리스트 기반 큐

---

이중 연결 리스트는 앞과 끝 모두에 바로 접근할 수 있으므로 O(1)만에 양 끝에 데이터를 삽입하고 삭제할 수 있다.

이는 끝에서 삽입하고 앞에서 삭제하는 구조인 큐를 위한 완벽한 내부 자료 구조라고 해도 무방하다.

이중 연결 리스트: 이중 연결 리스트 기반 큐 구현

---

다음은 자바로 구현해본 이중 연결 리스트 기반 큐이다.

DLLQue는 DoublyLinkedList 클래스와 DoublyLinkedList_Node 클래스를 이용하여 구현한다.

public class DLLQue {
	private DoublyLinkedList data;
	
	public DLLQue() {
		this.data = new DoublyLinkedList();
	}
	// 원소 삽입 메서드 인큐
	public void enque( String element ) {
		data.insertAtEnd( element );
	}
	// 원소 삭제 메서드 디큐
	public String deque(){
		DoublyLinkedList_Node removedNode = data.removeFromFront();
		return removedNode.getData();
	}
	// 가장 앞 원소 정보 읽기
	public String read() {
		if( data.getFirstNode() == null ) return null;
		return data.getFirstNode().getData();		
	}
}