Doubly Linked List (자바) 알고리즘 학습용 예제

Node.java

package blog.dblinkedlist;

public class Node {
	private Object data;
	private Node prev, next;
	
	// Constructor
	
	public Node(Object data) {
		this.data = data;
	}
	
	public Node(Object data, Node prev) {
		this.data = data;
		this.prev = prev;
	}
	
	public Node(Object data, Node prev, Node next) {
		this.data = data;
		this.prev = prev;
		this.next = next;
	}
	
	// Setter and Getter

	public Object getData() {
		return data;
	}

	public void setData(Object data) {
		this.data = data;
	}

	public Node getPrev() {
		return prev;
	}

	public void setPrev(Node prev) {
		this.prev = prev;
	}

	public Node getNext() {
		return next;
	}

	public void setNext(Node next) {
		this.next = next;
	}

	// toString

	@Override
	public String toString() {
		return "Node [data=" + data + ", prev=" + prev + ", next=" + next + "]";
	}
	
}

NodeMgmt.java

package blog.dblinkedlist;

public class NodeMgmt {
	
	private Node head, tail;
	
	public NodeMgmt(Object data) {
		this.head = new Node(data);
		this.tail = this.head;
	}
	
	public Node getHead() {
		return head;
	}

	public void setHead(Node head) {
		this.head = head;
	}

	public Node getTail() {
		return tail;
	}

	public void setTail(Node tail) {
		this.tail = tail;
	}

  // 연결 리스트의 맨 마지막에 노드 추가

	public void insert(Object data) {
		if(this.head == null) {
			this.head = new Node(data);
			this.tail = this.head;
		} else {
			Node node = this.head;
			while(node.getNext() != null) {
				node = node.getNext();
			}
			Node newNode = new Node(data);
			node.setNext(newNode);
			newNode.setPrev(node);
			this.tail = newNode;
		}
	}
	
	// 연결 리스트 순회
	
	public void desc() {
		Node node = this.head;
		while(node != null) {
			System.out.println("node: " + node.getData());
			node = node.getNext();
		}
	}
	
	// 노드의 헤드로부터 노드 찾기
	
	public Node searchFromHead(Object data) {
		Node node = this.head;
		while(node != null) {
			if(node.getData().equals(data)) {
				return node;
			} else {
				node = node.getNext();
			}
		}
		return null;
	}
	
	// 노드의 테일로부터 노드 찾기
	
	public Node searchFromTail(Object data) {
		Node node = this.tail;
		while(node != null) {
			if(node.getData().equals(data)) {
				return node;
			} else {
				node = node.getPrev();
			}
		}
		return null;
	}
	
	public boolean insertBefore(Object data, Object beforeData) {
		if(this.head == null) {
			this.head = new Node(data);
			this.tail = this.head;
			return true;
		} else {
			Node node = this.tail; // ###
			while(!node.getData().equals(beforeData)) {
				node = node.getPrev();
				if(node == null) {
					return false;
				}
			}
			Node newNode = new Node(data);
			Node beforeNewNode = node.getPrev();
			// 이전 노드의 next 포인터 변경
			beforeNewNode.setNext(newNode);
			// newNode의 양방향 포인터 설정
			newNode.setPrev(beforeNewNode);
			newNode.setNext(node);
			// 기존 노드의 prev 포인터를 새 노드로 변경
			node.setPrev(newNode);
			
			return true;
			
		}
	}
	
	public boolean insertAfter(Object data, Object afterData) {
		if(this.head == null) {
			this.head = new Node(data);
			this.tail = this.head;
			return true;
		} else {
			Node node = this.head; // ###
			while(!node.getData().equals(afterData)) {
				node = node.getNext();
				if(node == null) {
					return false;
				}
			}
			Node newNode = new Node(data);
			Node afterNewNode = node.getNext();
			// 기존 존재하던 노드의 prev 포인터 변경
			afterNewNode.setPrev(newNode);
			// newNode의 양방향 포인터 설정
			newNode.setPrev(node);
			newNode.setNext(afterNewNode);
			// 기존 노드의 next 포인터를 새 노드로 변경
			node.setNext(newNode);
			
			return true;
			
		}
	}
	
}

NodeMgmtTest.java

package blog.dblinkedlist;

public class NodeMgmtTest {
	
	public static void main(String[] args) {
		System.out.println("==== Node Test ====");
		// 더블 연결 리스트 생성 및 노드 삽입 테스트
		NodeMgmt dblLinkedList1 = new NodeMgmt(10);
		dblLinkedList1.insert(20);
		for(int i = 30; i <= 100; i += 10) {
			dblLinkedList1.insert(i);
		}
		dblLinkedList1.desc();
		
		System.out.println("\n==값을 통해 노드 찾기==");
		
		Node tail = dblLinkedList1.getTail();
		System.out.println(tail.getData());
		
		// 노드30을 헤드로부터 찾음
		Node node30 = dblLinkedList1.searchFromHead(30);
		System.out.println(node30.getData());
		
		// 노드80을 테일로부터 찾음
		Node node80 = dblLinkedList1.searchFromTail(80);
		System.out.println(node80.getData());
		
		System.out.println("\n==노드75를 80 전에 삽입==");
		
		// 노드75를 80 전에 삽입
		boolean node75i = dblLinkedList1.insertBefore("==75==", 80);
		System.out.println(node75i);
		dblLinkedList1.desc();
		
		System.out.println("\n==노드35를 30 앞에 삽입==");
		
		// 노드35를 30 앞에 삽입
		boolean node35i = dblLinkedList1.insertAfter("==35==", 30);
		System.out.println(node35i);
		dblLinkedList1.desc();
		
		
	}
	
}