Linked List - 연결 리스트

지금 유데미에서 Scott Barrett의 Data Structures & Algorithms - Java 강의를 듣고 있는데 정말 좋다. 자료 구조나 알고리즘 강의를 여러 개 보고 책도 읽어 봤지만 조금도 이해를 못해서 지금까지 계속 회피하는 중이었는데, 우연히 만난 스캇 선생님의 강의는 어째서 이 미천한 나도 이해할 수 있도록 만들어져 있는 것인지 그저 놀랍다. 영어라고 겁내지 말고, dsa로 고생하는 중이라면 그냥 유데미 상위권에 있는 강사들 강의 듣는 게 좋을 것 같다.

아무튼 지금은 노트에 필기하면서 강의를 듣는 중인데 언젠가 한번 velog에 싹 정리해야겠다.

언젠가..

public class LinkedList {

	private Node head;
	private Node tail;
	private int length;
	
	class Node {
		int value;
		Node next;
		
		Node(int value) {
			this.value = value;
		}
	}
	
	public LinkedList(int value) {
		Node newNode = new Node(value);
		head = newNode;
		tail = newNode;
		length = 1;
	}
	
	public void printList() {
		Node temp = head;
		while (temp != null) {
			System.out.print(temp.value + " ");
			temp = temp.next;
		}
	}
	
	public void append(int value) { 
		Node newNode = new Node(value);
		if (length == 0) {
			// LL이 empty 인데 append 하는 경우에 대응 
			head = newNode;
			tail = newNode;
		} else { 
			tail.next = newNode;
			tail = newNode;		
		}
		length++;
	}
	
	public Node removeLast() {
		
		// 링크리스트에 아무 것도 없을 때는 당연히 return null
		// 조건란에 head == null, tail == null 도 가능
		if(length == 0) return null;
		
		Node temp = head;
		Node pre = head;
		
		while (temp.next != null) {
			pre = temp;
			temp = temp.next;
		}
		
		tail = pre;
		tail.next = null;
		length--;
		
		if(length == 0) {
			head = null;
			tail = null;
		}
		
		return temp;
	}

	public void prepend(int value) {
		Node newNode = new Node(value);
		if(length == 0) {
			head = newNode;
			tail = newNode;
		} else {
			newNode.next = head; 
			head = newNode;
		}
		length++;
	}
	 
	public Node removeFirst() {
		if(length == 0) return null;
		// 아무 노드도 없을 땐 아무 것도 떼내지 않았기에
		
		Node temp = head;
		head = head.next;
		temp.next = null; // 떼어내고 포인터를 null
		length--;
		
		if(length == 0) {
			tail = null;
		}
		
		return temp; 
		// 떼어낸 게 어떤 건지를 반환함 
	}
	
	public Node get(int index) {
		// 유효하지 않은 인덱스에 대한 처
		if (index < 0 || index >= length) {
			return null;
		} 
		
		Node temp = head;
		for(int i = 0; i < index; i++) {
			temp = temp.next;
		}
		return temp;
	}
	
	public boolean set(int index, int value) {
		Node temp = get(index);
		if(temp != null) {
			// 범위가 맞는 인덱스의 값을 변경하려고 할 때만 true 반환  
			temp.value = value;
			return true;
		}
		// 범위 안 맞으면 전부 false
		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 temp = get(index - 1);
		
		newNode.next = temp.next;
		temp.next = newNode;
		length++;
		return true;
	}
	
	public Node remove(int index) { 
		// 범위 오류 처리 
		if (index < 0 || index >= length) return null;
		// removeFirst
		if (index == 0) return removeFirst();
		// removeLast
		if (index == length - 1) return removeLast();
		
		Node prev = get(index - 1);
		Node temp = prev.next;
		prev.next = temp.next; 
		temp.next = null;
		length--;
		
		return temp;
	}
	
	public void reverse() {
		Node temp = head;
		head = tail;
		tail = temp;
		
		Node after = temp.next;
		Node before = null;
		
		for (int i = 0; i < length; i++) {
			after = temp.next;
			temp.next = before;
			before = temp;
			temp = after;
		}
	}
	
	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);
	}
  
}