[Java] Singly Linked List

✔️ 연결 리스트(import java.util.LinkedList) 특징

1. 데이터가 저장되어 있는 노드(Node) 객체들을 참조 체인으로 엮어놓은 자료구조
2. 배열과 달리 데이터가 추가될 때마다 노드들이 생성되어 참조 체인에 추가되어서 빈 공간이 존재하지 않음
3. 삽입이나 삭제 시 항목 이동이 필요없음
4. 항목 탐색 시 첫 노드부터 해당 항목까지 순차 탐색(Sequential Search)해야 함

✔️ 단일 연결 리스트(Singly Linked List)

• 단일 연결 리스트는동적 메모리 할당을 받아 노드를 저장하고, 노드는 레퍼런스(reference)를 이용하여 다음 노드를 가리키도록 만들어 노드들을 한 줄로 연결시킨다.

💡 단일연결리스트의 노드 구조
값을 저장하는 원소와 다음 노드를 위한 레퍼런스를 저장하는 원소로 구성된다.

1. 기본적인 단일연결리스트 클래스

public class SinglyLinkedList<E> {
    // Node 객체
    private static class Node<E> {
        private E element; // 항목 저장
        private Node<E> next; // Node 레퍼런스 저장
        // Node 생성자
        public Node(E e, Node<E> n) {
            element = e;
            next = n;
        }
        public E getElement() { return element; }
        public Node<E> getNext() { return next; }
        public void setNext(Node<E> n) { next = n; }

        private Node<E> head = null; // 연결리스트의 첫번째 노드
        private Node<E> tail = null; // 연결리스트의 마지막 노드
        private int size = 0;
        public void SinglyLinkedList() {}
        public int size() { return size; }
        public boolean isEmpty() { return size == 0; }
        // 첫번째 노드 값 리턴
        public E first() {
            if(isEmpty()) return null;
            return head.getElement();
        }
        // 마지막 노드 값 리턴
        public E last() {
            if(isEmpty()) return null;
            return tail.getElement();
        }
}

- 특정 노드 탐색 : O(N)시간 소요

public int search(E target) {
            for(Node<E> cur = head, int i = 0; i < size && cur != null; cur = cur.getNext(), i++) { // 지역변수 cur이 연결리스트의 첫 노드 참조
                if(target == cur.getElement())
                    return i; // 탐색 성공 시 target이 i번째 인덱스에 있음을 리턴
            }
            return -1; // 탐색 실패 시 -1 리턴
}

- 맨 앞에 노드 삽입

public void addFirst(E e) { // 새 노드 생성 -> 새 노드의 다음 노드를 head로 지정 -> 새 노드를 head로 지정
            head = new Node<>(e, head);
            if(size == 0) tail = head;
            size++;
}

- 맨 뒤에 노드 삽입

public void addLast(E e) { // 새 노드 생성 -> 새 노드 이전 노드를 tail로 지정 -> 새 노드를 tail로 지정
            Node<E> newest = new Node<>(e, null);
            if (isEmpty())
                head = newest;
            else
                tail.setNext(newest);
            tail = newest;
            size++;
}

- 특정 노드 뒤에 새 요소 삽입

public void addAfter(E newElement, Node<E> prevNode) {
            prevNode.setNext(new Node(newElement, prevNode.getNext()));
            size++;
}

- 첫 번째 노드 삭제

public E deleteFirst() { // head 레퍼런스를 다음 노드로 옮기면 됨
            if(isEmpty()) return null;
            E answer = head.getElement();
            head = head.getNext();
            size--;
            if(size == 0)
                tail = null;
            return answer;
}

- 마지막 노드 삭제
바로 앞 노드의 next 레퍼런스를 변경해야 하므로, 마지막 노드의 삭제는 매우 비효율적, 따라서 아래 코드 이용

- 특정 노드의 다음 요소 삭제

public void deleteAfter(Node<E> prevNode) { // head 레퍼런스를 다음 노드로 옮기면 됨
            if(prevNode == null) return;
            Node tmp = prevNode.getNext();
            prevNode.setNext(tmp.getNext());
            tmp.setNext(null);
            size--;
}

2. 2차원 배열의 깊은 복사

public static int[][] deepClone(int[][] original) {
            int[][] backup
}

- 단일연결리스트의 복제

public SinglyLinkedList<E> clone() throws CloneNotSupportedException {
            SinglyLinkedList<E> other = (SinglyLinkedList<E>) super.clone();
            if(size > 0) {
                other.head = new Node<>(head.getElement(), null);
                Node<E> walk = head.getNext();
                Node<E> otherTail = other.head;
                while(walk != null) {
                    Node<E> newest = new Node<>(walk.getElement(), null);
                    otherTail.setNext(newest);
                    otherTail = newest;
                    walk = walk.getNext();
                }
            }
            return other;
}