Doubly Linked List - 이중 연결 리스트

public class DoublyLinkedList {

	private Node head; 
	private Node tail;
	private int length;
	
	class Node { 
		int value;
		Node next;
		Node prev;
		Node(int value) {
			this.value = value;
		}
	}
	
	public DoublyLinkedList(int value) {
		Node newNode = new Node(value);
		head = newNode;
		tail = newNode;
		length = 1;
	}
	
	public void append(int value) {
		
		// an instance which is going to be appended
		Node newNode = new Node(value);
		
		// for ddl null
		if (length == 0) {
			head = newNode;
			tail = newNode; 
		} else {
		// Otherwise
			tail.next = newNode;
			newNode.prev = tail;
			tail = newNode;
		}
		length++;
	}
	
	/**
	 * 버전 1 : length를 감소시킨 후 0인지 검증 후 대응 
	public Node removeLast() {
		// for ddl null
		if (length == 0) return null;
		
		// otherwise
		Node temp = tail;
		tail = tail.prev;
		tail.next = null;
		temp.prev = null;
		length--;
		
		// case for being null after this method
		// after decremented the length
		if(length == 0) {
			head = null;
			tail = null;
		}
		
		// returning the node we tried to remove
		return temp;
	}
	**/
	
	/** 버전 2 : length 감소 부분 전에 모든 로직을 작성함
	 * easier to read version **/
	public Node removeLast() {
		//	FOR 0 item
		if (length == 0) return null;
		
		Node temp = tail;
		
		if (length == 1) {
		// FOR 1 item
			head = null;
			tail = null;
		} else {
		// FOR >= 2 items
			tail = tail.prev;
			tail.next = null;
			temp.prev = null;
		}
		
		length--;
		
		return temp;
	}
	
	public void prepend(int value) {
		// 추가할 노드 
		Node newNode = new Node(value);
		
		// for ddl null
		if (length == 0) {
			// head==null, tail==null 도 conditional portion에 사용 가능
			head = newNode; 
			tail = newNode;
		} else {
			// for >= 1 item
			newNode.next = head;
			head.prev = newNode;
			head = newNode;
		}
		length++;
	}
	
	public Node removeFirst() {
		// for 0 item 
		if(length == 0) return null;
		
		// 가장 앞 노드에 붙어서 삭제를 위해 그 옆의 노드와
		// 연결을 끊어버리기 위해 이 Node 포인터가 필요
		Node temp = head;
		
		if (length == 1) {
			// for 1 item
			head = null;
			tail = null;
		} else { 
			// for >= 2 items
			head = head.next;
			head.prev = null;
			temp.next = null;
		}
		length--;
		return temp;
	}
	
	/**
	 * 버전 1 
	public Node get(int index) {
		// head와 동일한 노드를 만들어서 그 노드를 for 문으로 인덱스만큼 이동시킨다 
		if (index < 0 || index >= length) {
			return null;
		}
		
		Node temp = head;
		for (int i = 0; i < length; i++) {
			temp = temp.next;
		}
		
		return temp;
	}
	**/
	
	/** 버전 2 : 인덱스가 꼬리에 더 가까운 경우를 고려하여 효율적으로 메서드를 작성
	 * Modified to take advantage of the efficiency of DDL **/
	public Node get(int index) { 
		if (index < 0 || index >= length) return null; 
		Node temp = head;
		
		// wrap the for loop with if statement
		if (index < length/2) {
			for (int i = 0; i < index; i++) {
				temp = temp.next;
			}
		} else {
			// index >= length/2 .. 인덱스가 꼬리 부분에 더 가까움
			temp = tail;
			// temp가 꼬리에서부터 움직임 
			for (int i = length - 1; i > index; i--) {
				temp = temp.prev;
			}
		}
		return temp;
	}
	
	public boolean set(int index, int value) {
		Node temp = get(index);
		if (temp != null) {
			temp.value = value;
			return true;
		}
		return false;
	}
	
	public boolean insert(int index, int value) {
		if (index < 0 || index > length) return false;
		
		if (index == 0) {
			prepend(value);
			return true;
		}
		
		if (index == length) {
			append(value);
			return true;
		}
		
		Node newNode = new Node(value);
		Node before = get(index - 1);
		// Node after = get(index + 1); // get method is O(n)
		Node after = before.next; // this is O(1)
		
		newNode.prev = before;
		newNode.next = after;
		before.next = newNode;
		before.prev = newNode;
		after.prev = newNode;
		length++;
		
		return true;
	}
	
	/** 버전 1 : 변수 1개만 사용하기 
	 * (temp) 
	public Node remove(int index) {
		if(index < 0 || index >= length) return null;
		if(index == 0) return removeFirst();
		if(index == length - 1) return removeLast();
		
		Node temp = get(index);
		temp.next.prev = temp.prev;
		temp.prev.next = temp.next;
		temp.next = null;
		temp.prev = null;
		length--;
		
		return temp;
	}
	**/
	
	/** 버전 2 : 변수 3개 사용하기 
	 * (temp, before, after) **/
	public Node remove(int index) {
		if(index < 0 || index >= length) return null;
		if(index == 0) return removeFirst();
		if(index == length - 1) return removeLast();
		
		Node temp = get(index);
		Node before = temp.prev;
		Node after = temp.next;
		before.next = temp.next;
		after.prev = temp.prev;
		temp.next = null;
		temp.prev = null;
		length--;
		
		return temp;
	}
	
	
	
	public void printList() {
		Node temp = head;
		
		while(temp != null) {
			System.out.print(temp.value + " ");
			temp = temp.next;
		}
		
		System.out.println();
	}
	
	public void getHead() {
		System.out.println("Head : " + head.value);
	}
	
	public void getTail() {
		System.out.println("Tail : " + tail.value);
	}
	
	public void getLength() {
		System.out.println("Length : " + length);
	}
}