[바미] 자료구조 - Linked list

Linked list?

포인터를 통해 여러 노드(Node)가 연결돼 있는 자료구조를 의미합니다.

 

노드(Node)
자료구조에서 노드는 데이터를 저장하는 기본 단위를 의미합니다.

 

이 노드(Node)는 데이터를 저장하는 공간과 다음 노드를 가리키는 포인터 공간으로 구성됩니다.

 

이러한 구조 덕분에 Linked list의 삽입과 삭제에 걸리는 시간은 O(1)로 빠른편이죠.

노드를 삽입할 땐 새 노드를 만들어 노드 사이에 포인터로 연결하면되고, 노드를 삭제할 땐 바로 앞의 포인터만 바꾸면 되기 때문입니다.

Linked list 형태와 Node 구조.

위 그림에서 세 번째 노드를 삭제할 때 배열이였다면 그 뒤의 노드를 전부 한 칸씩 이동해야 하지만 Linked list는 바로 앞에 있는 노드의 포인터가 네 번째 노드를 가리키도록 수정하면 되죠.

 

삭제전

삭제 후

하지만 Linked list는 특정 데이터가 몇 번째 노드에 위치하는 지 직접적으로 알 수 없기 때문에 탐색 시 모든 노드를 탐색하며 찾아야 하는 단점이 있습니다. 

 

따라서 탐색 시간이 O(n)이 소요되죠.

 

코드(Java)

package example;

import java.lang.reflect.Array;

// 노드 클래스 정의
class Node {
    int data;  // 노드의 데이터
    Node next; // 다음 노드를 가리키는 참조

    // 노드 생성자
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

// 링크드 리스트 클래스 정의
class LinkedList {
    Node head; // 리스트의 첫 번째 노드를 가리키는 참조
    Node tail; // 리스트의 마지막 노드를 가리키는 참조

    // 리스트의 끝에 새 노드를 추가 O(1)
    public void append(int data) {
//      새 노드를 설정.
        Node newNode = new Node(data);
//      리스트가 비어있으면, 새 노드를 head와 tail로 설정.
        if (head == null) {
            head = newNode;
            tail = newNode;
            return;
        }

//      리스트 끝에 새 노드를 추가.
        tail.next = newNode;
        tail = newNode;
    }

// O(N)으로 노드를 추가하는 방법
//    public void append(int data) {
//        // 리스트가 비어 있으면, 새 노드를 헤드로 설정
//        if (head == null) {
//            head = new Node(data);
//            return;
//        }
//        Node current = head;
//        // 리스트의 끝까지 이동
//        while (current.next != null) {
//            current = current.next;
//        }
//        // 끝에 새 노드를 추가
//        current.next = new Node(data);
//    }

    // 리스트의 앞에 새 노드를 추가
    public void prepend(int data) {
        // 새 노드를 생성하고, 헤드로 설정
        Node newHead = new Node(data);
        newHead.next = head;
        head = newHead;
    }

    // 주어진 값을 가진 첫 번째 노드를 삭제
    public void deleteWithValue(int data) {
        // 리스트가 비어 있으면 아무 것도 하지 않음
        if (head == null) return;

        // 헤드 노드가 삭제하려는 값인 경우
        if (head.data == data) {
            head = head.next;
            return;
        }

        Node current = head;
        // 삭제할 값을 가진 노드를 찾음
        while (current.next != null) {
            if (current.next.data == data) {
                // 노드를 삭제
                current.next = current.next.next;
                return;
            }
            current = current.next;
        }
    }

    // 리스트를 출력
    public void printList() {
        Node current = head;
        // 리스트의 모든 노드를 순차적으로 출력
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null"); // 마지막 노드를 출력
    }

    // 메인 메서드: 프로그램 실행 진입점
    public static void main(String[] args) {
        LinkedList list = new LinkedList(); // 새로운 링크드 리스트 생성
        list.append(1); // 리스트의 끝에 1 추가
        list.append(2); // 리스트의 끝에 2 추가
        list.append(3); // 리스트의 끝에 3 추가
        list.prepend(0); // 리스트의 앞에 0 추가
        list.printList();  // 출력: 0 -> 1 -> 2 -> 3 -> null

        list.deleteWithValue(2); // 값이 2인 첫 번째 노드 삭제
        list.printList();  // 출력: 0 -> 1 -> 3 -> null
    }
}

코드설명

Node 클래스 정의

Node 클래스는 연결 리스트의 각 노드를 나타내며, 데이터와 다음 노드를 가리키는 포인터를 포함시켰습니다.

class Node {
    int data;  // 노드의 데이터
    Node next; // 다음 노드를 가리키는 참조

    // 노드 생성자
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

LinkedList 클래스 정의

LinkedList 클래스는 연결 리스트를 관리하며, 추가, 삭제, 출력을 수행할 수 있습니다.

class LinkedList {
    Node head; // 리스트의 첫 번째 노드를 가리키는 참조
    Node tail; // 리스트의 마지막 노드를 가리키는 참조
    
    ....

append 메서드

 리스트의 끝에 새로운 노드를 추가하는 메서드인데 이 메서드는 tail 참조를 사용하여 효율적으로 노드를 추가하도록 만들었습니다.

public void append(int data) {
    Node newNode = new Node(data); // 새 노드를 설정.
    if (head == null) { // 리스트가 비어있으면, 새 노드를 head와 tail로 설정.
        head = newNode;
        tail = newNode;
        return;
    }
    tail.next = newNode; // 리스트 끝에 새 노드를 추가.
    tail = newNode;
}

//    public void append(int data) {
//        // 리스트가 비어 있으면, 새 노드를 헤드로 설정
//        if (head == null) {
//            head = new Node(data);
//            return;
//        }
//        Node current = head;
//        // 리스트의 끝까지 이동
//        while (current.next != null) {
//            current = current.next;
//        }
//        // 끝에 새 노드를 추가
//        current.next = new Node(data);
//    }

밑에 주석은 비효율적으로 노드를 추가할 때 예시를 추가하여 O(1)과 O(N)으로 추가했을 때 어떤 차이가 있는 지 비교하시라고 추가하였습니다.

prepend 메서드

리스트의 앞에 새로운 노드를 추가하는 메서드입니다. 즉, Head를 추가하는 메서드가 됩니다.

public void prepend(int data) {
    Node newHead = new Node(data); // 새 노드를 생성하고, 헤드로 설정
    newHead.next = head;
    head = newHead;
}

 

deleteWithValue 메서드

주어진 값을 가진 첫 번째 노드를 삭제하는 메서드입니다.

public void deleteWithValue(int data) {
    if (head == null) return; // 리스트가 비어 있으면 아무 것도 하지 않음

    if (head.data == data) { // 헤드 노드가 삭제하려는 값인 경우
        head = head.next;
        return;
    }

    Node current = head;
    while (current.next != null) { // 삭제할 값을 가진 노드를 찾음
        if (current.next.data == data) {
            current.next = current.next.next; // 노드를 삭제
            return;
        }
        current = current.next;
    }
}

printList 메서드

리스트의 모든 노드를 출력하는 메서드입니다.

public void printList() {
    Node current = head;
    while (current != null) { // 리스트의 모든 노드를 순차적으로 출력
        System.out.print(current.data + " -> ");
        current = current.next;
    }
    System.out.println("null"); // 마지막 노드를 출력
}

main 메서드

위에서 정의한 LinkedList 클래스의 메서드들을 호출하는 부분입니다.

public static void main(String[] args) {
    LinkedList list = new LinkedList(); // 새로운 링크드 리스트 생성
    list.append(1); // 리스트의 끝에 1 추가
    list.append(2); // 리스트의 끝에 2 추가
    list.append(3); // 리스트의 끝에 3 추가
    list.prepend(0); // 리스트의 앞에 0 추가
    list.printList();  // 출력: 0 -> 1 -> 2 -> 3 -> null

    list.deleteWithValue(2); // 값이 2인 첫 번째 노드 삭제
    list.printList();  // 출력: 0 -> 1 -> 3 -> null
}