[자료구조] 링크드 리스트(C++)

C++ 역시 C언어로 구현한 링크드리스트와 비슷하다. 

이전에도 말했듯이 아주 중요한 구조이다.

typedef struct Node {
    int val;
    Node *next;
}node;
 

그렇다면 C++클래스로 어떻게 적용시킬까? 이전 게시물에서 간단하게 표현하였지만, 실제 적용되는 구조를 알아보자

typedef struct Node {
    int val;
    Node *next;
}node;
 
class list {
private:
    node* head; // 첫 노드 
    node* tail; // 마지막 노드
    node* New; // 노드 생성용
    node* pos; // 확인용(이동)

이렇게 클래스 맴버변수에 node포인터 타입을 가지도록 한다. 각 node포인터의 역할을 주석으로 표현하였다.

그리고 이전에서 진행한 노드 생성과 출력을 포함하여 삽입과 삭제연산을 수행해보자

이와같이 구조체를 맴버변수로 갖는 클래스를 형성하여 관리한다면 쉽게 연결리스트를 활용할 수 있다.

삭제연산에서 꼭 2개의 node포인터를 사용해서 연산을 이용해야 한다.

#include<iostream>
 
using namespace std;
 
typedef struct Node {
    int val;
    Node *next;
}node;
 
class list {
private:
    node* head; // 첫 노드 
    node* tail; // 마지막 노드
    node* New; // 노드 생성용
    node* pos; // 확인용(이동)
public:
    list() {
        head = tail = New = pos = NULL;
    }
 
    void create(int val) {
        New = new node;
        New->val = val;
        New->next = NULL;                //노드생성
        if (head == NULL) head = New;    //초기 노드
        else tail->next = New;           
 
        tail = New;
    }
 
    void display() {
        pos = head;    //head는 첫번째 노드
        while (pos->next != NULL) {
            cout << pos->val << " ";
            pos = pos->next;
        }
        cout << pos->val << endl;
    }
 
    int last() {
        int cnt = 1;
        if (head == NULL) return 0;
        pos = head;
        while (pos->next != NULL) {
            cnt++;
            pos = pos->next;
        }
        return cnt;
    }
 
    void insert(int cur, int n) {//몇번째 위치에 값을 삽입
        int cnt = 0;
        int L = last();
        if (L < 2) return;
        if (cur < 1) return;
        if (L - 1 < cur) return;         //삽입 안되는 경우
        pos = head;
        for (cnt = 0; cnt < cur; cnt++) {
            if (cnt == (cur - 1)) {      //삽입할 위치라면
                New = new node;          //노드생성
                New->val = n;
                New->next = pos->next;
                pos->next = New;
                return;                   
            }
            pos = pos->next;
        }
    }
    
    void insert2(int bal,int n) {  //해당 값을 찾으면 그 노드오른쪽에 삽입
        pos = head;
        //cout << pos << "  " << pos->val << "  " << pos->next << endl;
        while (pos->next != NULL) {
            //pos = pos->next;
            if (pos->val == bal) {
                New = new node;
                New->next = pos->next;
                New->val = n;
                pos->next = New;
                return;
            }
            pos = pos->next;
        }
    }
 
    void Delete(int n) { // 값을 기준으로 값 찾으면 삭제
        node *data = head;
        node *data_nx = head->next; // 두번째 노드!!  head->next가 가리키는것은 2번째 노드임
        node *remove = NULL;
 
        if (data->val == n) { // 첫번째 값을 지우는 경우
            delete[] data; // 메모리해제
            head = data_nx; // head포인터가 다음노드를 가지도록 함
            return;
        }
 
        while (data->next != NULL) { // 첫 노드가 가리키는 것이 NULL이 아니라면  
            data = data_nx;         // data는 첫 노드가 아닌 두번째 노드
            data_nx = data->next;   // data_nx(두번째 노드) 는 다음 노드
            if (data->val == n) {    //값을 찾음
                remove->next = data_nx; // remove가 가리키는 것은 data_nx노드
                delete[] data;
                return;
            }
            remove = data;        // remove포인터는 data포인터와 같은 값 가리킴
        }
    }
    
    ~list() {
        node *data = head;
        node *data_nx = head->next;
 
        delete[] data;
        while (data_nx != NULL) {
            data = data_nx;
            data_nx = data->next;
            delete[] data;
        }
    }
 
};
 
int main()
{
    list p;
    for (int i = 1; i <= 5; i++) p.create(101 * i);
 
    p.display();
    cout << p.last() << endl;
    p.insert(3, 1000);
    p.insert(5, 5000);
    p.insert2(303,98765);
    p.display();
    p.Delete(404);
    p.display();
    return 0;
}