연결리스트(Linkedlist)

연결리스트 :  - 차례대로 연결된 노드를 표현해 주는 자료구조

                  - 단방향 연결리스트에서 각 노드는 다음 노드를 가르킨다.

                  - 양방향 연결 리스트에서 각 노드는 다음노드와 이전 노드를 가르킨다.

                  - 배열과 달리 연결리스트는 특정 인덱스를 상수시간에 접근 할 수 없다.

                    => k번째 원소를 찾고 싶다면, k번 루프를 돌아야 한다.

 

1 <-> 2 <-> 3 <-> 4

 

연결리스트의 장점 : 리스트의 시작 지점에서 아이템을 추가하거나 삭제하는 연산을 상수시간에 할 수 있다.

 

단 방향 연결리스트 코딩

public class Node {
    Node next = null;
    int data;
    public Node(int d) {
        this.data = d;
    }

}

코드 : Node를 만드는 로직이 들어가있다. 이때 주의 할 점은 자기 자신을 호출한다는 점에 있다. 이 부분이 내가 생각할때 핵심인것 같다. 그리고 생성자를 통해 값을 주입받고 있다. 연결리스트 2번째 특징을 다시 살펴보면

각 노드는 다음 노드를 가르킨다고 했다. 그러기 때문에 노드를 추가하는 메서드를 추가해야한다.

    void appendToTail(int d) {
        Node end = new Node(d);
        Node n = this;
        while(n.next != null) {
            n = n.next;
        }
        n.next = end;
    }

신기한건 노드클래스를 다시 만들고 있다는 점에 있다. 다시 만들게 되면 다시 만든 노드의 next부분은 null이지만...

현재 노드의 next는 어떨까? 바로 Node end = new Node(d)에서 사용된 값이 들어간다는 것을 알 수 있다.

여기까지 이해하겠는데 while문을 사용하는 이유는 과연 무엇일까? 이것을 만들어놓지 않으면 무조건 첫 번째에서 마지막으로 이동하게 된다. 

만약에 1, 3, 5 ,8 를 차례대로 이 클래스에 넣어넣다고 가정하자.

그러면 노드1을 만들고,,, 그 뒤에 노드3을 추가한다. 하지만 노드3입장에서는 노드를 생성하게 된다. 그러니까

노드1입장에서는 1->3이지만

노드3입장에서는 1->3->? 이 된다. 이런식으로 계속 나아가면

 

1-> 3 ->

1-> 3 -> 5 ->

1 ->3 -> 5 -> 8

 

이렇게 된다. 또한 핵심은 this인데 this는 현재 클래스를 뜻하는 키워드다. 그렇기 때문에 n.next가 null일때까지 찾아야 된다. 만약에 이게 if라면, 만약에 n.next 가 null 이 아니라면... 그냥 다음 걸 호출된다.

 

이제 여기서 값을 삭제하는 메소드를 추가해 보자.

    Node deleteNode(Node head, int d) {
        Node n = head;
        if (n.data == d) {
            return head.next;
        }

        while (n.next != null) {
            if (n.next.data == d) {
                n.next = n.next.next;
                return head;
            }
            n = n.next;
        }
        return head;
    }

 값을 찾고,지워주면 된다. 여기서 왜 n.next이냐면... 값이 지워지면 인덱스가 지워지기 때문이다. 

그래서 다음거를 다다음거로 바꾸는 작업을 모든 노드를 돌면서 확인해야한다. 이 때문에 이런식으로 작성된것 같다.

 

다시 정리 하면 LinkedList는 ArrayList에 비해 중간에 추가, 삭제가 용이한 자료구조라고 한다.