[자료구조] List - 연결리스트

연결리스트

---

List - 연결리스트

연결 리스트(Linked List)는 데이터를 저장하는 방식 중 하나로, 각각의 노드가 데이터와 함께 다음 노드에 대한 참조(주소)를 가지고 잇어 데이터를 연결하는 방식. Java에서도 각각의 노드를 참조하는 연결 리스트를 구현 할 수 잇는데, 주로 단순 연결 리스트, 이중 연결 리스트, 원형 연결 리스트의 세 종류가 많이 사용됨.

---

1. 단순 연결 리스트 (Singly Linked List)

- 구조 : 각 노드는 데이터와 다음 노드를 가리키는 참조(포인터)를 가짐. 노드는 오직 한 방향으로만 연결되어 있음

- 구성 : Node 클래스는 data와 next 필드를 가지며, next는 다음 노드를 참조함.

class Node {
    int data;
    Node next;

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

---

2. 이중 연결 리스트 (Doubly Linked List)

- 구조 : 각 노드는 데이터와 함게 이전 노드와 다음 노드에 대한 참조를 가짐.즉, 양방향으로 연결된 리스트임.

- 구성 : Node클래스는 data, next, prev 필드를 가지며, next는 다음 노드를, prev는 이전 노드를 참조함.

- 특징 
1. 양방향으로 탐색이 가능하므로, 리스트의 중간에서 삽입과 삭제가 단순 연결 리스트보다 효율적
2. 메모리 사용이 단순 연결 리스트보다 더큼.  각 노드가 두 개의 참조(이전과 다음)을 저장해야 하기 때문
3. 삽입과 삭제 시, 이전 노드와 다음 노드의 참조를 모두 업데이트해야함

class Node {
    int data;
    Node next;
    Node prev;

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

---

3. 원형 연결 리스트 (Circular Linked List)

- 구조 : 원형 연결 리스트는 마지막 노드가 다시 첫 번째 노드를 가리키는 순환 구조로 되어 있음.

- 종류 
1. 단순 원형 리스트 : 단순 연결 리스트와 같지만, 마지막 노드의 next가 null이 아닌, 첫 번째 노드를 가리킴
2. 이중 원형 연결 리스트 : 이중 연결 리스트와 같지만, 마지막 노드의 next는 첫 번째 노드를, 첫 번재 노드의 prev는 마지막 노드를 가리킴.

- 특징
1. 끝이 없기 때문에 리스트의 처음과 끝을 쉽게 순환할 수 있음
2. 주로 원형 대기열 (Circular Queue) 같은 곳에서 사용됨
3. 삽입과 삭제는 리스트의 어느 지점에서나 효율적으로 수행될 수 있음

class Node {
    int data;
    Node next;

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

핵심

- 단순 연결 리스트는 한 방향으로만 연결되어 있으며, 기본적인 연결 리스트 형태

- 이중 연결 리스트는 양방향으로 탐색 할 수 있으며, 중간에서의 삽입 및 삭제가 용이

- 원형 연결 리스트는 리스트의 끝이 처음과 연결된 순환 구조로, 반복적으로 데이터를 처리할 때 유용함