연결리스트 Java 구현

ㅇ연결리스트

- 한 노드가 다음 노드의 주소를 가지고 있는 형태

- 탐색 시 처음부터 찾아나가야하므로 O(n)

ㅇ연결리스트에서 노드 삭제 구현

- 주소를 다음 다음 노드를 가리키게하면 된다.

- Java의 경우 관계만 끈어도 가비지 컬렉션이 저 객체를 자동으로 지워준다. (C나 C++같은건 직접 삭제해줘야할거다)

 

- Node 클래스

public class Node {

    int data;
    Node next = null;

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

    // 데이터 추가 메서드
    void append(int data) {
        // 데이터 객체에 담기
        Node end = new Node(data);
        // 마지막을 찾기위해 포인터 만들기
        Node pointer = this;
        while (pointer.next != null) {
            pointer = pointer.next;
        }
        // 마지막 노드에 데이터 넣어주기
        pointer.next = end;
    }

    // 데이터 삭제 메서드
    void delete(int d) {
        Node pointer = this;

        while (pointer.next != null) {
            // 삭제할 값이 있으면 연결고리를 다음 다음 노드에 붙이기
            if (pointer.next.data == d) {
                pointer.next = pointer.next.next;
            // d와 같지않으면 다음 노드로 이동
            } else {
                pointer = pointer.next;
            }
        }
    }

    // 전체 출력 메서드
    void printAll() {
        Node pointer = this;

        // N-1번째까지 출력
        while (pointer.next != null) {
            System.out.print(pointer.data + " ");
        }
        // 마지막 N번째 출력
        System.out.println(pointer.data);
    }
}

- Main 클래스

public class Main {
    public static void main(String[] args) {
        Node node = new Node(3);
        node.append(1);
        node.append(2);
        node.append(3);
        node.printAll();
        System.out.println("-- 2 삭제 --");
        node.delete(2);
        node.printAll();
    }
}

결과

ㅇ문제점

- 처음 노드를 지울 수 없다.

 

ㅇ해결방법

- 시작을 알려주는 데이터가 없는 노드를 생성하여 구현한다.

 

ㅇ추가로 생각해본 점

- 전체출력 메서드에서 System.out.print를 사용하였는데 BufferedWriter 클래스를 사용하여

  버퍼에 담은 후 한번에 flush() 하면 더 빠를 것 같다.

 

 

*참고

- 엔지니어 대한민국 (유투버)

- 코딩인터뷰 완전분석 (책)