JAVA Linked List

-리스트의 개념

리스트(Linked List)는 자료를 순서대로 연결하여 저장하는 자료구조이며, 주로 포인터를 이용하여 리스트를 연결한다.

 

단순 연결리스트

단순 연결 리스트는 data와 Link를 갖는 Node로 구성한다.

 

- 강사님

중간 삽입,삭제 할때 배열보다는 linked list가 유리하다.

1. 단일 링크드 리스트

2. 환형 단일 링크드 리스트

3. 더블 링크드 리스트

4. 환형 더블 링크드 리스트

연결리스트 예제

// 연결 리스트의 노드 클래스 정의
class Node {
    int data;
    Node next;

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

// 연결 리스트 클래스 정의
class LinkedList {
    Node head;

    public LinkedList() {
        this.head = null;
    }

    // 연결 리스트의 끝에 새로운 노드를 추가하는 메서드
    public void append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }

        Node current = head;
        while (current.next != null) {
            current = current.next;
        }

        current.next = newNode;
    }

    // 연결 리스트의 모든 노드를 출력하는 메서드
    public void display() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
}

public class Main {
    public static void main(String[] args) {
        // 연결 리스트 객체 생성
        LinkedList linkedList = new LinkedList();

        // 노드 추가
        linkedList.append(10);
        linkedList.append(20);
        linkedList.append(30);

        // 연결 리스트 출력
        linkedList.display();
    }
}

Q, 링크드 리스트의 종류의 정의

 

단일 링크드 리스트 (Singly Linked List):

단일 링크드 리스트는 각 노드가 다음 노드를 가리키는 포인터(주소)만을 가지고 있는 자료구조입니다.
각 노드는 데이터와 다음 노드를 가리키는 포인터로 구성됩니다.
리스트의 첫 번째 노드를 가리키는 헤드(Head) 포인터를 가지고 있습니다.
마지막 노드의 다음 노드를 null로 표시하여 리스트의 끝을 나타냅니다.

 

환형 단일 링크드 리스트 (Circular Singly Linked List):

환형 단일 링크드 리스트는 단일 링크드 리스트와 유사하지만, 마지막 노드가 첫 번째 노드를 가리키는 순환 구조를 가집니다.
따라서 마지막 노드의 다음 노드가 첫 번째 노드를 가리키게 되며, 리스트의 끝을 나타내는 null이 없습니다.
보통 원형 큐와 같은 순환적인 자료구조를 구현할 때 사용됩니다.

 

더블 링크드 리스트 (Doubly Linked List):

더블 링크드 리스트는 각 노드가 이전 노드와 다음 노드를 모두 가리키는 포인터(주소)를 가지고 있는 자료구조입니다.
각 노드는 데이터와 이전 노드를 가리키는 포인터(prev)와 다음 노드를 가리키는 포인터(next)로 구성됩니다.
리스트의 첫 번째 노드를 가리키는 헤드(Head) 포인터와 마지막 노드를 가리키는 테일(Tail) 포인터를 가지고 있습니다.
이전 노드를 가리키는 포인터로 양방향 탐색이 가능하므로, 탐색과 삭제 연산이 더욱 효율적입니다.

 

환형 더블 링크드 리스트 (Circular Doubly Linked List):

환형 더블 링크드 리스트는 더블 링크드 리스트와 환형 단일 링크드 리스트를 결합한 형태의 자료구조입니다.
각 노드는 이전 노드와 다음 노드를 가리키는 포인터를 가지며, 마지막 노드의 다음 노드가 첫 번째 노드를 가리키게 됩니다.
마지막 노드의 이전 노드도 첫 번째 노드를 가리키게 됩니다.
따라서 순환 구조를 가지면서 양방향 탐색이 가능합니다.

---

Q. 각각의 주의할점

단일 링크드 리스트 (Singly Linked List):

삽입과 삭제 연산 시에는 해당 노드의 이전 노드를 찾기 어렵기 때문에, 해당 노드를 삭제하려면 해당 노드 이전의 노드를 찾는 추가적인 연산이 필요합니다.
역방향 탐색이 불가능하므로 리스트의 끝에서부터 탐색해야 할 경우 효율이 떨어질 수 있습니다.

 

환형 단일 링크드 리스트 (Circular Singly Linked List):

무한 루프에 빠질 수 있으므로 순환 구조를 잘 처리해야 합니다.
리스트가 비어있을 때에도 null을 사용하지 않기 때문에, 빈 리스트와 노드가 한 개인 리스트를 처리하는 방법을 구현해야 합니다.

 

더블 링크드 리스트 (Doubly Linked List):

각 노드가 이전 노드와 다음 노드를 가리키는 포인터를 가지므로 메모리 사용량이 더 많습니다.
삽입과 삭제 연산 시에는 이전 노드와 다음 노드의 포인터를 업데이트해야 하므로 추가적인 작업이 필요합니다. 이때 주의해야 할 것은 모든 포인터를 정확하게 업데이트하는 것입니다.

 

환형 더블 링크드 리스트 (Circular Doubly Linked List):

순환 구조이므로 무한 루프에 빠질 수 있습니다. 순환을 제대로 처리해야 합니다.
더블 링크드 리스트와 마찬가지로 모든 포인터를 정확하게 업데이트하는 것이 중요합니다.

---

Q. 각각의 삽입 삭제하는 방법

 

단일 링크드 리스트 (Singly Linked List):

 

삽입:
리스트의 맨 앞에 노드를 삽입하고자 할 때:
새로운 노드를 생성합니다.
새로운 노드의 next 포인터를 현재의 헤드 노드를 가리키게 합니다.
헤드 포인터를 새로운 노드로 업데이트합니다.
리스트의 특정 위치에 노드를 삽입하고자 할 때:
새로운 노드를 생성합니다.
이전 노드의 next 포인터를 새로운 노드를 가리키게 합니다.
새로운 노드의 next 포인터를 이전 노드가 가리키던 다음 노드를 가리키게 합니다.

 

 

삭제:
리스트에서 특정 노드를 삭제하고자 할 때:
이전 노드의 next 포인터를 삭제하려는 노드의 다음 노드를 가리키게 합니다.

환형 단일 링크드 리스트 (Circular Singly Linked List):

단일 링크드 리스트와 동일한 방법으로 삽입과 삭제를 수행하면 됩니다.
다만, 끝을 나타내는 null이 없기 때문에 노드를 삽입할 때 빈 리스트와 노드가 한 개인 리스트를 따로 처리해주어야 합니다.

 

더블 링크드 리스트 (Doubly Linked List):

삽입:
리스트의 맨 앞에 노드를 삽입하고자 할 때:
새로운 노드를 생성합니다.
새로운 노드의 next 포인터를 현재의 헤드 노드를 가리키게 합니다.
헤드 노드의 prev 포인터를 새로운 노드를 가리키게 합니다.
헤드 포인터를 새로운 노드로 업데이트합니다.
리스트의 특정 위치에 노드를 삽입하고자 할 때:
새로운 노드를 생성합니다.
이전 노드의 next 포인터를 새로운 노드를 가리키게 합니다.
새로운 노드의 prev 포인터를 이전 노드를 가리키게 합니다.
새로운 노드의 next 포인터를 이전 노드가 가리키던 다음 노드를 가리키게 합니다.
다음 노드의 prev 포인터를 새로운 노드를 가리키게 합니다.

삭제:
리스트에서 특정 노드를 삭제하고자 할 때:
이전 노드의 next 포인터를 삭제하려는 노드의 다음 노드를 가리키게 합니다.
다음 노드의 prev 포인터를 삭제하려는 노드의 이전 노드를 가리키게 합니다.

 

환형 더블 링크드 리스트 (Circular Doubly Linked List):

더블 링크드 리스트와 동일한 방법으로 삽입과 삭제를 수행하면 됩니다.
단, 순환 구조를 잘 처리해야 하며 무한 루프에 빠지지 않도록 주의해야 합니다.