Linked List

전체구조

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

Node 구조

class Node
{
    public:
        string num;
        Node* nextNode;
};

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

Linked List 구조

멤버변수

private:
    Node* firstNode = NULL;
    Node* tailNode = NULL;

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

 

Node 추가 함수 

void add(string data){

    Node* node = new Node();
    node->data = data;

    if (firstNode == NULL || tailNode == NULL){
        firstNode = node;
        tailNode = node;
    }
    else{
        tailNode->nextNode = node;
        tailNode = node;
    }
}

Node를 추가하는 멤버 함수 입니다. 새로운 Node 객체를 생성하고 매개변수로 받은 string num 값을 넣어서 Node를 세팅 합니다. firstNode와 tailNode가 둘다 NULL이면 처음 Node를 추가하는 것 이므로 firstNode = tailNode = node로 하고 처음 Node를 추가하는것이 아니라면 기존 마지막 노드 tailNode의 nextNode 변수를 새로운 node에 연결시켜 주고 tailNode를 node로 설정하여 추가합니다.

 

Node 찾기 함수

vector<int> Find(string data)
{
    Node* temp = firstNode;
    int index = 0;
    vector<int> vecIndex;

    while (temp != NULL)
    {
        if (temp->data == data)
        {
            vecIndex.push_back(index);
        }
        temp = temp->nextNode;
    }
    return vecIndex;
}

첫번째 노드의 주소를 Node* temp에 담고 temp가 NULL이 아닌 동안 하나씩 순회 하면서 Node의 데이터를 매개변수로 받은 string data와 비교하여 일치할때마다 index값을 indexList 변수에 push 하여 저장하고 리스트 변수를 리턴합니다.

 

마지막 Node 제거 함수

 void deleteLastNode() {
    Node* temp = firstNode;
    Node* preTemp = NULL;

    if (firstNode == NULL)return;

    while (temp->nextNode != NULL) {
        preTemp = temp;
        temp = temp->nextNode;
    }

    temp->data.clear();

    if (temp->data.empty() && preTemp != NULL) {
        preTemp->nextNode = NULL;
    }
    temp = NULL;
}

이동하는 변수 temp와 이동하기 전 변수인 perTemp를 선언합니다. while문을 통해 마지막 노드까지 이동 한 후 Node의 멤버변수와 객체의 할당을 해지하고 마지막 노드 전의 노드의 nextNode 값을 NULL로 합니다.

 

Node 데이터 출력 함수

void print(){
    Node* temp = firstNode;

    while (temp != NULL){
        cout << temp->data << " ";
        temp = temp->nextNode;
    }
}

첫번째 노드부터 널이 아닐때까지 하나씩 순회하면서 출력합니다.