자료구조 - 연결 리스트(2)

[원형 연결 리스트]

원형 연결 리스트란 마지막 노드가 첫 번째 노드를 가리키는 리스트입니다.

즉, 마지막 노드의 링크 필드가 NULL 이 아닌 첫 번째 노드의 주소를 가리키는 리스트입니다.

또한 리스트의 어떤 위치에서 시작하더라도 모든 노드를 순회할 수 있습니다.

 

 

원형 연결 리스트는 리스트의 처음과 끝에 노드를 삽입하는 경우에 단순 연결 리스트보다 간단할 수 있습니다.

헤드 포인터를 제일 마지막 노드를 가리키게 설정하면 마지막과 끝에 원소를 삽입하는 것이 상수 시간안에 가능합니다.

 

 

 

원형 연결 리스트의 앞에 원소를 삽입하는 경우

 

 

 

 

(1) 삽입할 노드의 링크 필드를 기존 원형 연결 리스트의 제일 앞 요소를 가리키게 한다.

(2) 마지막 요소의 링크 필드를 새로운 노드를 가리키게 한다.

 

    void insertFront(int value) 
    {
        Node* newNode = new Node(value);

        if (head == nullptr) 
        {
            // 리스트가 비어 있는 경우
            head = newNode;
            newNode->next = head;
        }
        else
        {
            Node* temp = head;
            // 마지막 노드를 찾음
            while (temp->next != head) 
            {
                temp = temp->next;
            }
            
            // 새로운 노드를 head로 설정하고 마지막 노드의 next를 새로운 노드로 설정
            newNode->next = head;
            head = newNode;
            temp->next = head;
        }
    }

 

 

 

원형 연결 리스트의 끝에 원소를 삽입하는 경우

 

 

(1) 끝에 있는 노드의 링크 필드를 새로운 노드로 설정한다.

(2) 새로운 노드의 링크 필드를 제일 앞 노드를 가리키도록 한다.

(3) 헤드 포인터가 마지막 노드를 가리키게 설정한다.

void insertEnd(int value)
{
        Node* newNode = new Node(value);

        if (head == nullptr) 
        {
            // 리스트가 비어 있는 경우
            head = newNode;
            newNode->next = head;
        } 
        else 
        {
            Node* temp = head;
            // 마지막 노드를 찾음
            while (temp->next != head)
            {
                temp = temp->next;
            }
            temp->next = newNode;
            newNode->next = head;
        }
    }

 

 

 

 

 

 

 

[이중 연결 리스트]

이중 연결 리스트는 각 노드가 두 개의 포인터를 갖는 연결 리스트로 하나는 다음 노드를 가리키고 다른 하나는 이전 노드를 가리킵니다.

이를 통해 리스트를 양방향으로 순회할 수 있습니다.

 

 

이중 연결 리스트의 노드 구조

#include <iostream>
using namespace std;

struct Node 
{
    int data;      // 데이터 필드
    Node* next;    // 다음 노드를 가리키는 포인터
    Node* prev;    // 이전 노드를 가리키는 포인터

    Node(int val)
    {
        data = val;
        next = nullptr;
        prev = nullptr;
    }
};

 

 

 

[이중 연결 리스트의 삽입과 삭제 연산]

 

 

이중 연결 리스트의 앞에 노드를 삽입하는 경우

void insertFront(int value)
{
    Node* newNode = new Node(value);
    if (head == nullptr)
    {
        head = newNode;
    } 
    else 
    {
        newNode->next = head;
        head->prev = newNode;
        head = newNode;
    }
}

 

(1) 새로운 노드를 생성합니다.

(2) 리스트가 비어 있는 경우, 새 노드를 head로 설정합니다.

(3) 리스트가 비어 있지 않은 경우, 새 노드의 next를 현재 head로 설정하고,

     현재 head의 prev를 새 노드로 설정한 후,

      head를 새 노드로 업데이트합니다.

 

 

 

이중 연결 리스트의 끝에 노드를 삽입하는 경우

void insertEnd(int value) 
{
    Node* newNode = new Node(value);
    if (head == nullptr) 
    {
        head = newNode;
    } 
    else 
    {
        Node* temp = head;
        while (temp->next != nullptr) 
        {
            temp = temp->next;
        }
        temp->next = newNode;
        newNode->prev = temp;
    }
}

 

(1) 새로운 노드를 생성합니다.

(2) 리스트가 비어 있는 경우, 새 노드를 head로 설정합니다.

(3)  리스트가 비어 있지 않은 경우, 마지막 노드를 찾고,

      새 노드를 마지막 노드의 next로 설정한 후,

      새 노드의 prev를 마지막 노드로 설정합니다.

 

 

 

이중 연결 리스트에서 특정 값을 가진 노드를 삭제하는 경우

void deleteNode(int value) 
{
    if (head == nullptr) return;  // 리스트가 비어 있는 경우

    Node* temp = head;
    while (temp != nullptr && temp->data != value) 
    {
        temp = temp->next;
    }

    if (temp == nullptr) return;  // 값을 가진 노드를 찾지 못한 경우

    if (temp->prev != nullptr) 
    {
        temp->prev->next = temp->next;
    }
    else 
    {
        head = temp->next;  // 삭제할 노드가 head인 경우
    }

    if (temp->next != nullptr) 
    {
        temp->next->prev = temp->prev;
    }

    delete temp;
}

 

(1) 리스트가 비어 있는 경우 아무 것도 하지 않습니다.

(2) 리스트에서 해당 값을 가진 노드를 찾습니다.

(3) 해당 노드를 찾으면, 이전 노드의 next를 삭제할 노드의 next로 설정하고,

     다음 노드의 prev를 삭제할 노드의 prev로 설정합니다.

(4) 삭제할 노드가 head인 경우, head를 다음 노드로 업데이트합니다.

(5) 노드를 삭제합니다.

 

 

 

 

삽입과 삭제를 사용하는 예제

int main()
{
    DoublyLinkedList dlist;

    // 앞에 노드 삽입
    dlist.insertFront(10);
    dlist.insertFront(20);
    dlist.insertFront(30);

    // 리스트 출력
    dlist.display();  // 출력: 30 20 10

    // 끝에 노드 삽입
    dlist.insertEnd(40);
    dlist.insertEnd(50);

    // 리스트 출력
    dlist.display();  // 출력: 30 20 10 40 50 

    // 노드 삭제
    dlist.deleteNode(20);
    dlist.display();  // 출력: 30 10 40 50 

    dlist.deleteNode(30);
    dlist.display();  // 출력: 10 40 50 

    dlist.deleteNode(50);
    dlist.display();  // 출력: 10 40

    return 0;
}

 

 

 

[이중 연결 리스트 클래스 구현]

class DoublyLinkedList 
{
    private:
        Node* head;

    public:
        DoublyLinkedList()
        {
            head = nullptr;
        }

        // 리스트의 앞에 노드를 삽입하는 메서드
        void insertFront(int value)
        {
            Node* newNode = new Node(value);
            if (head == nullptr)
            {
                head = newNode;
            }
            else 
            {
                newNode->next = head;
                head->prev = newNode;
                head = newNode;
            }
        }    

        // 리스트의 끝에 노드를 삽입하는 메서드
        void insertEnd(int value)
        {
            Node* newNode = new Node(value);
            if (head == nullptr) 
            {
            head = newNode;
            } 
            else 
            {
                Node* temp = head;
                while (temp->next != nullptr) 
                {
                    temp = temp->next;
                }
                temp->next = newNode;
                newNode->prev = temp;
            }
        }

        // 특정 값을 가진 노드를 삭제하는 메서드
        void deleteNode(int value) 
        {
            if (head == nullptr) return;  // 리스트가 비어 있는 경우

            Node* temp = head;
            while (temp != nullptr && temp->data != value) 
            {
                temp = temp->next;
            }

            if (temp == nullptr) return;  // 값을 가진 노드를 찾지 못한 경우

            if (temp->prev != nullptr) 
            {
                temp->prev->next = temp->next;
            } 
            else 
            {
                head = temp->next;  // 삭제할 노드가 head인 경우
            }

            if (temp->next != nullptr) 
            {
                temp->next->prev = temp->prev;
            }

            delete temp;
        }

        // 리스트를 출력하는 메서드
        void display() 
        {
            Node* temp = head;
            while (temp != nullptr) 
            {
                cout << temp->data << " ";
                temp = temp->next;
            }
            cout << endl;
        }
};