Double Linked List

전체 구조

Double Linked List의 전체적인 구조는 그림과 같습니다. Node 구조체 안에는 데이터를 담는 int data변수와 다음 노드의 위치를 가르키는 Node* nextNode와 이전 노드의 위치를 가르키는 Node* preNode가 있습니다. 그럼 이제부터 코드를 하나씩 설명드리겠습니다.

Node 구조

class Node
{
    public:
        int data;
        Node* nextNode = NULL;
        Node* preNode = NULL;
};

Node 클래스 입니다. int num은 데이터를 의미하며 변수 선언을 통해 추가로 데이터를 저장 할 수 있습니다 Node* nextNode는 다음 Node의 주소를 담고 있는 포인터 변수 입니다. 이 값을 통해 다음 Node로 하나씩만 이동 가능하며 첫번째 Node에서 네번째 Node로 가는것은 불가능합니다. 또한 nextNode 값이 NULL이면 마지막 노드(tailNode)를 의미합니다. Node* preNode는 이전 Node의 주소를 담고 있는 포인터 변수 입니다. 이 값을 통해 이전 Node로 하나씩만 이동 가능하며 네번째 Node에서 첫번째 Node로 가는것은 불가능합니다. 또한 preNode 값이 NULL이면 첫번째 노드(firstNode)를 의미합니다.

Double Linked List 구조

멤버변수

private:
    Node* firstNode = NULL;

멤버변수는 첫번째 시작 노드의 주소를 저장하는 Node* firstNode로 구성되어 있습니다.

 

Node 추가 함수 

void insert(int data)
    {
        Node* node = new Node();
        node->data = data;
 
        Node* st_node = firstNode;
 
        if (st_node == NULL) {
            firstNode = node;
        }
        else {
            while (st_node->nextNode != NULL) {
                st_node = st_node->nextNode;
            }
            st_node->nextNode = node;
            node->preNode = st_node;
        }
    }

1. 새로 삽입 할 노드를 생성 후 데이터를 넣습니다.

2.1 firstNode가 비어있다면 firstNode(첫번째 노드)의 값을 생성한 노드로 설정합니다.

2.2 firstNode가 비어있지 않다면 firstNode부터 시작해서 노드를 한칸씩 이동하여 마지막 노드까지 도달 후 마지막 노드의 nextNode 값에 새로 생성한 node를 대입하고 새로 생성한 node의 preNode 값에 마지막 노드를 대입합니다.

Node 찾기 함수

int find(int data)
{
    Node* temp = firstNode;
    int index = 0;
 
    while (temp != NULL)
    {
        if (temp->data == data)
        {
            cout << index << endl;
            break;
        }
        temp = temp->nextNode;
        index++;
    }
    return index;
}

첫번째 노드(firstNode)부터 시작하여 순회하며 찾고자 하는 매개변수로 받은 data 값을 가지고 있는 node를 찾아서 인덱스 값을 반환합니다.

Node 제거 함수

void del(int data)
{
    Node* st_node = firstNode;
 
    while (st_node->nextNode != NULL) {
        if (st_node->data == data) {
            if (st_node == firstNode) {
                if (st_node->nextNode != NULL) {
                    firstNode = st_node->nextNode;
                    st_node->nextNode->preNode = NULL;
                }
            }
            else if (st_node->preNode != NULL) {
                st_node->preNode->nextNode = st_node->nextNode;
                st_node->nextNode->preNode = st_node->preNode;
            }
        }
 
        st_node = st_node->nextNode;
    }
 
    if (st_node->data == data) {
        if (st_node->preNode != NULL) {
            st_node->preNode->nextNode = NULL;
        }
        st_node = NULL;
    }
}

매개변수로 받은 data의 값을 가지고 있는 노드를 전부 삭제하는 함수 입니다.

1. 첫번째 노드부터 시작해서 data 값을 가지고 있는 노드를 찾습니다.

2. 노드를 삭제 할 경우 현재 노드->preNode의 nextNode를 현재 노드의 nextNode 값을 대입하고 현재 노드->nextNode의 preNode를 현재 노드의 preNode 값을 대입합니다.

3. 첫번째 노드를 삭제하거나 마지막 노드를 삭제 해야 할 경우도 고려합니다.

Node 출력 함수

void print()
{
    Node* temp = firstNode;
 
    while (temp != NULL)
    {
        cout << temp->data << " ";
        temp = temp->nextNode;
    }
    cout << endl;
}

첫번째 노드부터 순회하면서 data 값을 출력합니다.