[whiteship스터디]single linked list 구현

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

• LinkedList에 대해 공부하세요.
• 정수를 저장하는 ListNode 클래스를 구현하세요.
• ListNode add(ListNode head, ListNode nodeToAdd, int position)를 구현하세요.
• ListNode remove(ListNode head, int positionToRemove)를 구현하세요.
• boolean contains(ListNode head, ListNode nodeTocheck)를 구현하세요.
• 2021.01.26 - [스터디/[whiteship]JAVA] - [4주차]제어문

[노드 클래스]

public class Node<T> {


    public T data;
    public Node<T> next;


    public Node(T data) {
        this.data = data;
        this.next = null;
    }

}

[링크드 리스트 클래스]

 

public class SingleLinkedList<T> {
    public Node<T> head;
    public int size;

    public SingleLinkedList() {
        this.head = null;
        this.size = 0;
    }

    public Node<T> add(Node<T> head, Node<T> nodeToAdd, int position) {
        //첫 번째 삽입때
        if (position == 0) {
            if (head == null) {
                nodeToAdd.next = null;
                this.head = nodeToAdd;
                size++;
                return nodeToAdd;
            }
            nodeToAdd.next = head;
            this.head = nodeToAdd;
            size++;
            return nodeToAdd;
        }
        // 삽입 위치 전 노드가 가르키는 다음 노드를 주소를 찾는다.
        Node<T> temp = head;
        for (int before = 0; before < position - 1; before++) {
            temp = temp.next;
        }
        nodeToAdd.next = temp.next;
        temp.next = nodeToAdd;
        size++;
        return nodeToAdd;
    }

    public Node<T> remove(Node<T> head, int position) {
        Node<T> removedElement;
        Node<T> temp = head;
        if (position == 0) {
            removedElement = this.head;
            this.head = head.next;
            size--;
            return removedElement;
        }
        for (int before = 0; before < position - 1; before++) {
            temp = temp.next;
        }
        removedElement = temp.next;
        temp.next = removedElement.next;
        size--;
        return removedElement;
    }

    public boolean contains(Node<T> head, Node<T> check) {
        T data = check.data;
        Node<T> temp = head;
        if (temp == null) {
            return false;
        }
        while (temp.data != data) {
            if (temp.data.equals(data)) return true;
            if (temp.next == null) return false;
            temp = temp.next;
        }
        return false;
    }

    public void printList() {
        Node<T> temp = this.head;
        if (temp == null) {
            System.out.println("출력할 것이 없습니다.");
        }
        while (temp != null) {
            System.out.print(temp.data+ " ");
            temp = temp.next;
        }
        System.out.println(" ");
    }
}​

 

public class Test {

    public static void main(String[] args) {
        SingleLinkedList<Object> singleLinkedList = new SingleLinkedList<>();


        singleLinkedList.add(singleLinkedList.head, new Node("hello"), 0);
        singleLinkedList.add(singleLinkedList.head, new Node(600), 1);
        singleLinkedList.add(singleLinkedList.head, new Node(700), 0);
        singleLinkedList.add(singleLinkedList.head, new Node(800), 2);
        singleLinkedList.printList();

        singleLinkedList.remove(singleLinkedList.head, 2);
        singleLinkedList.printList();

        System.out.println("데이터 존재 :"+singleLinkedList.contains(singleLinkedList.head,new Node<>(800)));
        System.out.println("단일 링크드 리스트 크기 :"+singleLinkedList.size);
    }
}

linkedList클래스에서 add, remove, contains 메소드 매개변수 head의 경우 과제에서 명시되어 있기때문에 사용했습니다. 만약 생략 할 경우 add메소드를 호출할때 자기 자신의 헤드값을 매개변수로 주는 불필요한 전달을 제거할 수 있습니다.