과제 2. LinkedList를 구현하세요.

• LinkedList에 대해 공부하세요.
• 정수를 저장하는 ListNode 클래스를 구현하세요.
• ListNode add(ListNode head, ListNode nodeToAdd, int position)를 구현하세요.
• ListNode remove(ListNode head, int positionToRemove)를 구현하세요.
• boolean contains(ListNode head, ListNode nodeTocheck)를 구현하세요.

LinkedList

LinkedList는 컴퓨터에 자료를 저장하는 구조의 한 종류로써 일렬로 연결된 데이터를 저장할때 사용합니다. 기본적으로 LinkedList는 Node형태로 되어있으며 HeadNode로 부터 시작하여 자신의 다음 노드의 주소값을 저장하고있는 형태로 사용됩니다.

LinkedList는 배열과 비교가 많이 됩니다. 배열의 경우 배열의 방들이 물리적으로 한곳에 모여있으며 배열의 방 크기를 한번 생성하면 크기를 늘이거나 줄일 수 없습니다.

하지만 LinkedList의 경우 노드를 생성하여 주소값을 변경해주어 쉽게 새로운 데이터를 추가 혹은 제거 할 수 있습니다. 이때, 노드가 LinkedList에서는 삭제되었지만 메모리상에는 남아있게됩니다. Java에서는 GC가 알아서 처리해주지만 C 혹은 C++에서는 반드시 해당 노드를 사용하지 않는다고 명시해주어야 메모리상에서 정리가됩니다.

이러한 데이터의 추가 혹은 삭제를 배열에서 처리하려면 새로운 방을 만들어 전체 데이터를 복사해주고 이전 방을 삭제하는 작업이 필요하게됩니다.

그렇기 때문에 길이가 정해져있지 않은 데이터를 핸들링할때는 LinkedList를 이용하는것이 좋습니다.

Java에서 LinkedList 구현해보기

package linkedList;

public class LinkedList {
    ListNode header;

    static class ListNode {
        int data;
        ListNode next = null;

        public ListNode() {
        }

        public ListNode(int data) {
            this.data = data;
        }
    }

    LinkedList() {
        header = new ListNode();
    }

    LinkedList add(ListNode nodeToAdd, int position) {
        // 지정한 position이 List의 크기보다 큰 경우
        if (size() < position) throw new IndexOutOfBoundsException();
        else {
            ListNode target = header;
            for (int i = 0; i <= position; i++) {
                if (i == position) {
                    if (target.next == null) {
                        target.next = nodeToAdd;
                    }else {
                        nodeToAdd.next = target.next;
                        target.next = nodeToAdd;
                    }
                }
                target = target.next;
            }
        }
        return this;
    }

    LinkedList remove(int positionToRemove) {
        // 지정한 position이 List의 크기보다 큰 경우
        if (size() < positionToRemove) throw new IndexOutOfBoundsException();
        else {
            ListNode target = header.next;
            ListNode before = header;
            for (int i = 0; i <= positionToRemove; i++) {
                if (i == positionToRemove) {
                    if (target.next != null) {
                        before.next = target.next;
                    } else {
                        before.next = null;
                    }
                } else {
                    before = target;
                    target = target.next;
                }
            }
        }
        return this;
    }

    boolean contains(ListNode nodeTocheck) {
        ListNode target = header;
        while (target.next != null) {
            if (target == nodeTocheck) {
                return true;
            }
            target = target.next;
        }
        return false;
    }

    int size() {
        int result = 0;
        ListNode target = header;
        while (target.next != null) {
            result++;
            target = target.next;
        }
        return result;
    }

    void retrieve() {
        ListNode target = header.next;
        while (target.next != null) {
            System.out.print(target.data + " -> ");
            target = target.next;
        }
        System.out.println(target.data);
    }
}

TestCode 작성