Linked List 활용

public static void main(String[] args) {

    // Linked List

    // 메모리가 필요한 만큼만 딱! 깔끔하게 생긴다 (null인 고리 찾으면 거기서 끝나니까.)
    // --> 알아서 고리가 착착 연결되니까 배열길이를 복사하는 과정이 필요없단 말임



    MyLinkedList<String> list = new MyLinkedList<>(); 
    // 이게 리스트 선언한건데, 이게 없어지지 않는 이상 연결고리는 계속 돌아간다(= 메모리가 소멸을 안한다구)
    list.add("안녕1");
    list.add("안녕2");
    list.add("안녕3");
    list.add("안녕4");
    list.add("안녕5");
    list.add("안녕6");


    list.remove(1);		// 배열의 2번째를 삭제하겠다 
    list.add(1, "하하하"); 	


    String value = list.get(3);		// 배열의 4번째를 찾아보겠다 (저 3은 get의 index)
    System.out.println(value);

    for(int x = 0 ; x < 6 ; x++) {
        System.out.println(list.get(x));
    }




}

// 연결 리스트(Linked List)는 선형 자료구조로, 각 요소를 "노드(Node)"라고 부른다

// **기본타입** --> 시작(null)-한조-메르시-티모를 이어주는 list중 한조를 구현한거임
// class Node{
//      String value; --> 한조가 들어가는 공간
//      Node next; --> 메르시와 이어주는 link
// }

 

class Node<E>{
	
	E value;
	Node<E> next;
	
}


class MyLinkedList<E>{
	
	Node<E> first;			// 시작

	void add(E value) {		// 자료추가
		
		Node<E> newNode = new Node<>();
		newNode.value = value;
		
	
		if(first == null) {		// 첫코드는 무조건 null이니까
			first = newNode;	// 이게 한번 실행되면(= 한조가 배정되면) 이제 null이 아니지?
			return;
		}
		
	
		Node<E> temp = first;				
		while(true) {
			
			if(temp.next == null) { 	
            // 마지막 자료구조의 연결고리 끝은 null이겠지? 그때 나오겠다고.
				break;
			}
			temp = temp.next;			
			// temp가 연결고리를 따라서 다음 자료를 찾는 아이
			// 다음 주소값을 계속 얻어와. 또 이어지겠지?
			// next가 null인 자료를 계속 찾으면서 돌다가~
	
		}
		temp.next = newNode;		
		// 고리를 이어준다! --> while문 밖에 있어야겠지
	
	}
	
	
	// 배열의 어떠한 값을 가져오고 싶을 때 : get
	// 그러나 linked List의 단점임!
	// --> first부터 주르륵 돌면서 index에서 멈추는 값을 찾아야되니까. (시간이 아주 오래걸린다구)

	E get(int index) {
		
		Node<E> temp = first;
		
		for(int x = 0 ; x < index ; x++) {
			temp = temp.next;
		}
		
		return temp.value;
	}
	
	
	
	// 배열의 어떠한 값을 삭제하고 싶을 때 : 
	// linked List의 최대 장점!
	// 연결고리를 끊어버리면 메모리도 깔끔하게 소멸된다.
	// 1-2-3 에서 1-3으로 해주면 되겠지.
	
	void remove(int index) {
		
		Node<E> temp = first;
		
		// 삭제하는할 요소(2)의 바로 앞(1)을 찾아야겠지 -> 그래서 index-1
		for(int x = 0 ; x < index-1 ; x++) {
			temp = temp.next;
		}
		
		// temp는 1일거고, 2(temp.next)가 아니라 3이랑 연결되고 싶은거잖아?
		
		// 그때의 temp.next(2)의 다다음(3)으로 넣어주면되지
		temp.next = temp.next.next;
		
	}
	
	
	
	// 배열 중간에 어떠한 값을 삽입(= 추가)하고 싶을 때 : 
	// 삽입하고 싶은자리의 앞을 찾아야겠지
	
	
	void add(int index, E value) {
		
		// 내가 삽입하고 싶은 값(2)
		Node<E> newNode = new Node<>();
		newNode.value = value;
		
		
		// 삽입하고싶은 앞자리(1) 찾기
		Node<E> temp = first;
		for(int x = 0 ; x < index-1 ; x++) {
			temp = temp.next;
		}
		
		// 지금 temp는 1이겠지.
		// 그니까 내가 삽입하고싶은 값의 next가 ...... 다시
		
		newNode.next = temp.next;
		temp.next = newNode;
	
	}

}