[ 자료구조 ] LinkedList

다시 시작된.. 자료구조의 세계로.. 

이번엔 링크드 리스트 구분 

힘들었던 점.. ! 우선 nullpointer exception이 너무 나서 그걸 처리하는 게 꽤 많은 힘이 들었다. 

보면 insert 를 할때나 delete 할 때 모두 if 문으로 size 에 맞지 않을 경우 예외처리를 해주어야하는데 해당 부분에서 애를 먹어서 다른 사람들 코드를 좀 창고하였다. ㅎㅎ 

import lombok.val;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class MyLinkedList {

    // 하나하나의 작은 노드를 생성
    class Node {
        private Object val;
        //다음 노드를 가르키는 필드
        public Node next;

        public Node(Object object) {
            this.val = object;
            this.next = null;
        }
        
    }

    public Node head;
    public Node tail;
    public int size;
    /** Initialize your data structure here. */
    // 그 다음에 링크드리스트 생성자 생성
    public MyLinkedList() {
        size=0;
        tail =null;
        head= null;
    }
    public void print() {
        Node node = head;
        for(int i =0; i<size; i++)
        {
            System.out.print(node.val+"->");
            node = node.next;
        }
        System.out.println("");
        System.out.println("size = " + size);
    }

    /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
    public int get(int index) {
        if (index <0 || index>= size)
            return -1;

        int idx = 0;
        Node findNode = head;

        // head node 로 계속 해야한다.
        for(int i =0; i<index; i++) {
            findNode = findNode.next;
        }

        return (int)(findNode.val);
    }


    /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
    public void addAtHead(int val) {
        Node curNode = new Node(val);
        // 첫번째 노드
        if ( head == null ){
            head = curNode;
            tail = curNode;
            size++;
        }
        // 첫번째가 아닌 노드
        else {
            curNode.next = head;
            head = curNode;
            size++;
        }

    }

    /** Append a node of value val to the last element of the linked list. */
    public void addAtTail(int val) {
       Node curNode = new Node(val);
       // 마지막 노드가 없을 때
       if( tail == null || size == 0){
           head = curNode;
           tail = curNode;
           size++;
       }
       else {
           tail.next = curNode;
           tail = curNode;
           size++;
       }


    }

    /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
    public void addAtIndex(int index, int val) {
        if(index <0 || index > size)
            return;
        if(index == 0 ){
            addAtHead(val);
        }
        else if(index == size) {
            addAtTail(val);
        }
        else {
            Node curNode = new Node(val);
            Node findNode = head;
            int idx = 0;

            // indexth 번째면은 실제로 index-1 인번째를 찾아야하는 것.
            for(int i =0; i<index -1; i++) {
                findNode = findNode.next;
            }
            Node nextNode = findNode.next;
            findNode.next = curNode;
            curNode.next = nextNode;
            size++;

        }


    }

    /** Delete the index-th node in the linked list, if the index is valid. */
    public void deleteAtIndex(int index) {
        if(size == 0 || index >= size || index <0 )
            return;

        Node findNode = head;
        if(index ==0 ){
            Node nextNode = head.next;
            head = nextNode;
            size--;
            // 해당 예외문 추가
            if(size ==0) {
                tail = null;
            }
        }
        else {
            for(int i =0; i<index-1; i++) {
                findNode= findNode.next;
            }
//            System.out.println("findNode.val = " + findNode.val);
            Node curNode = findNode.next;

            if(curNode.next == null) {
                //curNode 가 tail 이라는 뜻
                tail = findNode;
                findNode.next = null;
            }
            else {
                Node nextNode = curNode.next;
                findNode.next = nextNode;
            }
            size--;

        }

    }
};



public class Main {
    public static int N, M =0;
    public static StringBuilder sb = new StringBuilder();
    public static boolean check[];
    public static int arr[][] = new int[9][9];
    public static void main(String[] args) throws IOException {


        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addAtTail(3);
        myLinkedList.print();
        myLinkedList.addAtTail(1);
        myLinkedList.print();
        myLinkedList.addAtTail(1);
        myLinkedList.print();
        myLinkedList.addAtTail(4);
        myLinkedList.print();
        myLinkedList.deleteAtIndex(5);
        myLinkedList.print();
        myLinkedList.deleteAtIndex(1);
        myLinkedList.print();
//        myLinkedList.addAtIndex(1, 2);    // linked list becomes 1->2-3



    }

}