[자료구조] 이중 연결 리스트(Doubly Linked List) 개념과 구현

1. 이중 연결 리스트

단순 연결 리스트에서 이전 노드에 접근하기가 어렵다는 점을 개선하여 원형 연결 리스트를 구성했지만, 원형 연결 리스트에서도 현재 노드의 바로 이전 노드에 접근하려면 전체 리스트를 한바퀴 순회해야 하는 문제가 있습니다. 이러한 문제는 리스트를 구성하는 노드의 링크 방향이 한 방향으로만 되어있기 때문에 발생합니다.

 

따라서 이러한 문제를 개선하기 위해 양쪽 방향으로 순회할 수 있도록 연결한 리스트를 이중 연결 리스트(Doubly Linked List)라고 합니다.

 

이중 연결 리스트

2. 이중 연결 리스트 구현

이중 연결 리스트는 양쪽 방향으로 순회할 수 있어야 합니다. 따라서 왼쪽 노드를 연결하는 링크 필드와 오른쪽 노드를 연결하는 링크 필드 그리고 데이터를 저장하는 데이터 필드로 구성된 노드를 연결하여 이중 연결 리스트를 구현합니다.

 

이중 연결 리스트 노드 구조

 

· DoublyListNode

public class DoublyListNode {
	DoublyListNode llink; // 왼쪽 링크 필드
	String data; // 데이터 필드
	DoublyListNode rlink; // 오른쪽 링크 필드

	public DoublyListNode(String data) {
		this.llink = null;
		this.data = data;
		this.rlink = null;
	}

	public String getData() {
		return this.data;
	}
}

 

· DoublyLinkedList

public class DoublyLinkedList {
	private DoublyListNode head;

	public DoublyLinkedList() {
		this.head = null;
	}

	// 리스트의 첫 번째 위치에 노드 삽입
	public void insertFirstNode(String data) {
		DoublyListNode newNode = new DoublyListNode(data);
		DoublyListNode temp;

		if (head == null) {
			head = newNode;
			newNode.llink = newNode;
			newNode.rlink = newNode;
		} else {
			temp = head;
			while (temp.rlink != head) {
				temp = temp.rlink;
			}
			newNode.rlink = head;
			head.llink = newNode;
			head = newNode;
			temp.rlink = head; // 마지막 노드를 첫 번째 노드와 연결
			newNode.llink = temp; // 첫 번째 노드를 마지막 노드와 연결
		}
	}

	// 이전 노드를 입력 받아 중간 위치에 노드 삽입
	public void insertMiddleNode(DoublyListNode preNode, String data) {
		DoublyListNode newNode = new DoublyListNode(data);
		newNode.rlink = preNode.rlink;
		preNode.rlink.llink = newNode;
		preNode.rlink = newNode;
		newNode.llink = preNode;
	}

	// 리스트의 마지막 위치에 노드 삽입
	public void insertLastNode(String data) {
		DoublyListNode newNode = new DoublyListNode(data);
		DoublyListNode temp;

		if (head == null) {
			head = newNode;
			newNode.llink = newNode;
			newNode.rlink = newNode;
		} else {
			temp = head;
			while (temp.rlink != head) {
				temp = temp.rlink;
			}
			temp.rlink = newNode;
			newNode.llink = temp;
			newNode.rlink = head; // 마지막 노드를 첫 번째 노드와 연결
			head.llink = newNode; // 첫 번째 노드를 마지막 노드와 연결
		}
	}

	// 리스트의 첫 번째 노드 삭제
	public void deleteFirstNode() {
		DoublyListNode temp;

		if (head == null) {
			return;
		}

		if (head.rlink == head) { // 노드가 한 개일 때
			head = null;
		} else { // 노드가 두 개 이상일 때
			temp = head;
			while (temp.rlink != head) {
				temp = temp.rlink;
			}
			temp.rlink = head.rlink; // 마지막 노드를 첫 번째 노드와 연결
			head = head.rlink;
			head.llink = temp; // 첫 번째 노드를 마지막 노드와 연결
		}
	}

	// 리스트의 마지막 노드 삭제
	public void deleteLastNode() {
		DoublyListNode temp;

		if (head == null) {
			return;
		}

		if (head.rlink == head) { // 노드가 한 개일 때
			head = null;
		} else { // 노드가 두 개 이상일 때
			temp = head;
			while (temp.rlink != head) {
				temp = temp.rlink;
			}
			temp.llink.rlink = head; // 마지막 노드를 첫 번째 노드와 연결
			head.llink = temp.llink; // 첫 번째 노드를 마지막 노드와 연결
		}
	}

	// 이중 연결 리스트 왼쪽으로 순회
	public void leftTraversal(String start, String end) {
		DoublyListNode to = searchNode(start);
		DoublyListNode from = searchNode(end);
		DoublyListNode temp;

		if (to == null || to == null) {
			System.out.println("해당 원소가 리스트에 없습니다.\n");
		} else {
			temp = to;
			while (temp != from) {
				System.out.printf("%s -> ", temp.getData());
				temp = temp.llink; // 왼쪽으로 순회
			}
			System.out.printf("%s\n\n", temp.getData());
		}
	}

	// 이중 연결 리스트 오른쪽으로 순회
	public void rightTraversal(String start, String end) {
		DoublyListNode to = searchNode(start);
		DoublyListNode from = searchNode(end);
		DoublyListNode temp;

		if (to == null || to == null) {
			System.out.println("해당 원소가 리스트에 없습니다.\n");
		} else {
			temp = to;
			while (temp != from) {
				System.out.printf("%s -> ", temp.getData());
				temp = temp.rlink; // 오른쪽으로 순회
			}
			System.out.printf("%s\n\n", temp.getData());
		}
	}

	// 노드 검색
	public DoublyListNode searchNode(String data) {
		DoublyListNode temp = head;

		do {
			if (temp.getData() == data) {
				return temp; // 검색 성공
			}
			temp = temp.rlink; // 오른쪽으로 순회
		} while (temp != head);

		return null; // 검색 실패
	}

	// 리스트 출력
	public void printList() {
		DoublyListNode temp;

		if (head == null) {
			System.out.println("빈 리스트입니다.\n");
		} else {
			temp = head;
			System.out.printf("L = [");
			do {
				System.out.printf("%s", temp.getData());
				temp = temp.rlink; // 오른쪽으로 순회
				if (temp != head) {
					System.out.printf(", ");
				}
			} while (temp != head);
			System.out.printf("]\n\n");
		}
	}

	// 리스트 역순으로 출력
	public void printReverseList() {
		DoublyListNode temp;

		if (head == null) {
			System.out.println("빈 리스트입니다.\n");
		} else {
			temp = head.llink; // 리스트의 마지막 노드
			System.out.printf("L = [");
			do {
				System.out.printf("%s", temp.getData());
				temp = temp.llink; // 왼쪽으로 순회
				if (temp != head.llink) {
					System.out.printf(", ");
				}
			} while (temp != head.llink);
			System.out.printf("]\n\n");
		}
	}
}

 

· MainForDoublyLinkedList

public class MainForDoublyLinkedList {
	public static void main(String[] args) {
		DoublyLinkedList dL = new DoublyLinkedList();
		DoublyListNode node;

		System.out.println("1. 리스트에 원소 4개 삽입하기");
		dL.insertFirstNode("A");
		dL.insertLastNode("B");
		dL.insertLastNode("C");
		dL.insertLastNode("E");
		dL.printList();

		System.out.println("2. C 뒤에 D 삽입하기");
		node = dL.searchNode("C");
		if (node == null) {
			System.out.println("해당 원소가 리스트에 없습니다.");
		} else {
			dL.insertMiddleNode(node, "D");
			dL.printList();
		}

		System.out.println("3. B에서 D까지 오른쪽으로 순회하기");
		dL.rightTraversal("B", "D");

		System.out.println("4. B에서 D까지 왼쪽으로 순회하기");
		dL.leftTraversal("B", "D");

		System.out.println("5. 리스트 노드 삭제하기");
		dL.deleteFirstNode();
		dL.deleteLastNode();
		dL.printList();

		System.out.println("6. 리스트 역순으로 출력하기");
		dL.printReverseList();
	}
}

 

· 실행 결과