[자료구조] Singly LinkedList 구현

배열처럼 원하는 값에 한번에 접근할 수 없으니 모든 접근을 head를 통해서 해야한다.
또한, next 링크가 삽입과 삭제 이후에도 정상적으로 작동할 수 있게 next를 제대로 수정해줘야 한다.
특히 어디에서 (중간에서 or head에서 or tail에서) 삽입/삭제할 것인지에 따라서
다르게 처리해줘야 한다는 것을 주의해해야 한다.
삽입 삭제의 자세한 원리는 아래 그림 참고하면 된다.

코드

package SinglyLinkedList;

public class Main {
    class Node{
        int data;
        Node next;

        Node(int data, Node next){
            this.data = data;
            this.next = next;
        }
    }

    class SinglyLinkedList {
        Node head;

        boolean isEmpty() {
            if (head == null) {
                return true;
            }
            return false;
        }

        int getSize() { // head에서 tail까지 cur을 이동시키면서 size++ 시킴
            int size = 0;
            if (!isEmpty()) {
                size = 1;
                Node cur = this.head;
                while (cur.next != null) {
                    cur = cur.next;
                    size++;
                }
            }
            return size;
        }

        void addNode(int data) {
            if (isEmpty()) { // 아무것도 없을 때는 head 만들어주기
                this.head = new Node(data, null);
            } else { // cur을 이용해 tail까지 간 다음, tail의 next에 새 노드 만들어주기
                Node cur = this.head;
                while (cur.next != null) {
                    cur = cur.next;
                }
                cur.next = new Node(data, null);
            }
        }

        void insertNode(int offset, int data) {
            if (isEmpty()) {
                this.head = new Node(data, null);
            } else {
            	// prevIdx를 통해 삽입할 인덱스 이전 노드로 이동
                if (offset == 0) {
                    Node newNode = new Node(data, this.head);
                    this.head = newNode;
                } else if (offset == getSize()) {
                    addNode(data);
                } else {
                    int prevIdx = 0;
                    Node prev = this.head;
                    while (prevIdx != offset-1) {
                        prev = prev.next;
                        prevIdx++;
                    }
                    Node newNode = new Node(data, prev.next);
                    prev.next = newNode;
                }
            }
        }

        void deleteNode(int offset) {
            if(isEmpty()){
                System.out.println("Empty");
            } else {
            	// prevIdx를 통해 삽입할 인덱스 이전 노드로 이동
                if (offset == 0) {
                    if(getSize() == 1){
                        this.head = null;
                    } else {
                        this.head = this.head.next;
                    }
                } else if (offset >= getSize()){
                    System.out.println("Wrong delete");
                } else {
                    int prevIdx = 0;
                    Node prev = this.head;
                    while (prevIdx != offset-1) {
                        prev = prev.next;
                        prevIdx++;
                    }

                    if (offset == getSize() - 1) {
                        prev.next = null;
                    } else {
                        prev.next = prev.next.next;
                    }
                }
            }
        }

        int findNode(int data){
            if(isEmpty()){
                return -1;
            }

            int curIdx = 0;
            Node cur = this.head;
            while(cur.next != null){
                if(cur.data == data){
                    break;
                }
                curIdx++;
                cur = cur.next;
            }

            if(curIdx == getSize()-1 && cur.data !=data){
                return -1;
            }

            return curIdx;
        }

        void print() {
            if (isEmpty()) {
                System.out.println("Empty");
            } else {
                Node cur = this.head;
                while (cur.next != null) {
                    System.out.print(cur.data + ", ");
                    cur = cur.next;
                }
                System.out.print(cur.data + "\n");
            }
        }
    }
}