(자료구조) List - LinkedList를 만들어보자!

class Node {
    private Object value;
    private Node next;

    Node(Object o) {
        this.value = o;
    }

    public Object getValue() {
        return value;
    }

    public void setValue(Object o) {
        this.value = o;
    }

    public Node getNext() {
        return next;
    }

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

    boolean isLast() { // 마지막 노드인지
        return this.next == null;
    }

    public boolean equals(Node node) { // 내용물과 참조하는 애가 같은지
        return value.equals(node.getValue()) && next == node.getNext();
    }
}

class NodeTest {
    public static void main(String[] args) {
        Node n = new Node(2);
        Node n2 = new Node(2);
        Node n3 = new Node(2);
        Node n4 = new Node(3);
        n.setNext(n4); // n 다음에 n4
        n2.setNext(n4); // n2 다음에 n4
        n3.setNext(n); // n3 다음에 n
        System.out.println(n.equals(n2)); // true
        System.out.println(n.equals(n3)); // false
        System.out.println(n.isLast()); // false
        System.out.println(n4.isLast()); // true

        // 지금 구조(List)는 n3(2) 다음에 n(2) 다음에 n4(3) 순으로 연결(Linked)돼있다.
        // 초기 노드를 지정해주고, 계속해서 다음 노드를 참조하는 걸 증감식에 적어줌,
        for(Node node = n3; true; node = node.getNext()) { // 탈출 조건이 있는 무한 반복문
            // 마지막 노드여도 출력까지는 해줘야함.
            System.out.println(node.getValue()); // 2 2 3
            if(node.isLast()) break;
        }
    }
}

class LinkedList {
    private Node[] nodes;
    private int idx; // 현재 리스트의 몇 번째 요소까지 노드가 들어왔는지 확인하는 변수

    LinkedList() {
        this(10); // 기본적으로 10개를 만들어주자, 너무 작게 만들면 복사하는 처리 비용이 많이 들테니...
    }

    LinkedList(int size) {
        nodes = new Node[size];
    }

    void add(Object o) { // 맨 끝에 삽입하는 경우
        int size = size();
        Node node = new Node(o);

        // 꽉차지 않았다면
        if(idx != size)  nodes[idx] = node; // 현재 인덱스에 노드 삽입.
        else { // 꽉 찼으면
            Node[] tmpNodes = new Node[size+10]; // 나중에 또 금방 복사하지 않게 적절하게 큰 배열을 만들자.
            for(int i=0; i<size; i++) tmpNodes[i] = nodes[i]; // 기존의 값들을 새로운 배열에 복사
            tmpNodes[idx] = node; // 새로운 값 삽입
            nodes = tmpNodes; // 복사한 배열을 원본 배열 변수로 갈아치우기
        }
        if(idx == 0) {
            idx++;
            return; // 하나만 넣은 거면 참조 관계를 수정할 필요가 없음.
        }
        nodes[idx-1].setNext(nodes[idx++]); // 이전 노드의 참조를 현재 노드로 변경
    }

    void add(int idx, Object o) { // 인덱스를 지정해 해당 지점에 삽입하려는 경우
        // List는 선형구조이므로 데이터를 삽입해야할 인덱스보다 더 뒤에 노드를 삽입하는 것은 불가능하다.
        // 당연히 배열의 인덱스를 벗어나는 음수도 불가능하다.
        if(this.idx < idx || idx < 0) throw new ArrayIndexOutOfBoundsException("올바른 인덱스를 입력해주세요!");
        // 배열의 중간에 노드를 삽입하는 게 아닌 경우
        if(idx == this.idx) this.add(o);
        else { // 배열의 중간에 노드를 삽입하는 경우
            int size = size();
            Node node = new Node(o);
            // 꽉 차지 않았다면 기존과 동일한 사이즈의 배열 생성, 아니라면 넉넉히 길이가 10 더 긴 배열 생성.
            Node[] tmpNodes = idx != size ? new Node[size] : new Node[size+10];

            // 복사할 배열을 직접 넘겨줘서 추가하기.
            for(int i=0; i<idx; i++) tmpNodes[i] = nodes[i]; // idx 이전까지는 그대로 복사
            for(int i=idx; i<this.idx; i++) { // last까지 복사
                tmpNodes[i+1] = nodes[i]; // idx 이후는 한 칸씩 밀어서 복사
            }
            tmpNodes[idx] = node; // 새로운 배열에 지금 들어온 노드 삽입
            nodes = tmpNodes; // 복사한 배열을 원본 배열 변수로 갈아치우기
            nodes[idx].setNext(nodes[idx-1].getNext()); // idx 노드는 중간에 끼어들었으므로 idx 노드 이전 노드의 참조를 가리켜야함.
            nodes[idx-1].setNext(nodes[idx]); // idx 이전 노드의 참조는 idx 노드를 가리키고 있어야함.
            this.idx++;
        }
    }

    void remove() {
        nodes[--idx] = null; // 마지막 노드 삭제 후 인덱스 1 낮춤.
        nodes[idx-1].setNext(null); // 이전 노드가 마지막 노드이므로 참조할 노드가 없음.
    }

    void remove(int idx) {
        Node[] tmpNodes = new Node[size()]; // 배열을 한 칸씩 땡겨야하므로 새롭게 배열 생성.
        Node node = getNode(idx).getNext(); // idx 번째 노드가 갖고 있는 참조 노드
        for(int i=0; i<idx; i++) tmpNodes[i] = nodes[i]; // idx 이전까지 복사
        for(int i=idx+1; i<this.idx; i++) tmpNodes[i-1] = nodes[i]; // idx 이후로 또 복사
        nodes = tmpNodes; // 복사한 배열을 원본 배열 변수로 갈아치우기
        nodes[idx-1].setNext(node);
        this.idx--;
    }

    Object get(int idx) {
        Node node = getNode(idx);
        return node == null ? null : node.getValue();
    }

    Node getNode(int idx) {
        Node node=nodes[0];
        // idx까지 계속 다음 참조 노드를 구함.
        for(int i=0; i<idx; i++, node=node.getNext());
        return node;
    }

    int size() {
        return nodes.length;
    }
}

class LinkdedListTest {
    public static void main(String[] args) {
        LinkedList l = new LinkedList();
        l.add(1);
        l.add("a");
        System.out.println(l.get(0)); // 1
        // 0번째 노드를 구하고 그 참조 노드를 구하고 값을 얻기
        System.out.println(l.getNode(0).getNext().getValue()); // a
        for(int i=0; i<10; i++) l.add(i); // 1 a 0 1 2 3 4 6 7 8 9
        System.out.println(l.get(11)); // 9
        l.add(11, 22);
        System.out.println(l.get(11)); // 22

        LinkedList l2 = new LinkedList();
        l2.add(1);
        l2.add(2);
        l2.add(3);
        l2.add(4);
        System.out.println(l2.get(3)); // 4
        l2.remove();
        System.out.println(l2.get(3)); // null
        System.out.println(l2.get(1)); // 2
        l2.remove(1);
        System.out.println(l2.get(1)); // 3
    }
}