[자료구조] 비정렬 리스트 Array based vs Linked List

비정렬 리스트

비정렬 리스트는 말 그대로 리스트가 정렬되지 않는 상태로, 그냥 들어가면 들어가는대로 저장되는 자료구조이다. 쉽기 때문에 나머지 설명은 생략하고 구현 설명에 좀 더 초점을 두겠다.

---

 

Array based implement

class unsorted {
public:
    unsorted();
    void get(int &item); //currentpos에 있는 데이터를 돌려줌
    void reset(); // currentpos를 초기화 시킴
    void insert(int item);
    void deleted(int item);
    int length();
    bool full() const;
    void retrieve(int& item, bool& find); // 아이템이 리스트에 있는지 확인

private:
    int currentpos; // 리스트에서 현재 보고있는 위치를 알려줌
    int items[MAX];
    int len; // 데이터의 길이

};

 

• unsorted 생성자

    unsorted() {
        len = 0;
    }

길이를 0으로 초기화한다.

 

• get(int &item)

    void get(int& item) {
        currentpos++;
        item = items[currentpos];
    }

currentpos 위치에 있는 데이터를 item에 넣어준다. item은 레퍼런스로 받기 때문에 값이 바뀐다. 

필요없다고 느낄 수 있지만 클라이언트 함수에서 items의 값을 전부 확인할 때 필요함

 

• reset

    void reset() {
        currentpos = -1;
    }

현재 보고 있는 currentpos를 초기화 시킨다.

 

• insert(int item)

    void insert(int item) {
        items[len] = item;
        ien++;
    }

현재 인덱스는 len-1이므로 items[len] 에 데이터를 넣고 len을 1 증가시킨다.

 

• deleted

    void deleted(int item) {
        len--;
    }

쉽다.. 설명 생략

 

• length

    int length() {
        return len;
    }

마찬가지로 설명 pass

 

• full

    bool full() const {
        return (len == MAX);
    }

pass

 

• retrieve

    void retrieve(int& item, bool& find) {
        find = 0;
        int idx = 0;
        while (!found && idx < len) {
            if (items[i] == item) {
                find = 1;
                item = items[i];
                break;
            }
            else {
                idx++;
            }
        }
    }

리스트안에 값이 있는지 확인해준다. 값이 있으면 find=1을 넣어주고 레퍼런스로 돌려준다. 

 

---

Linked List implement

연결리스트로 구현했을 때 포인트는 다른 자료구조들과 마찬가지로, 소멸자에서 heap영역에 생긴 데이터들을 다 없애줌으로써 메모리 leak이 발생하지 않도록 하는 것이다. 항상 포인터를 사용할 때 주의해야할 점이다.

또 한가지는 deleted(int item)이다. 이 함수를 구현할 때 주의할 점은 리스트간의 연결을 유지하는 것인데 자세한 것은 함수 파트에서 설명하도록 하겠다.

class unsorted {
public:
    unsorted();
    ~unsorted();
    bool full() const;
    void get(int& item);
    void reset();
    void insert(int input);
    void deleted(int input);
    void retrieve(int& item, bool& find);
    int length();

private:
    int len;
    Node* currentpos;
    Node* data;
};

struct Node{
    int item;
    Node* next;
}

 

• unsorted 생성자

    unsorted() {
        len = 0;
        currentpos = NULL;
        data = NULL;
    }

모든 데이터들을 초기화 시켜준다. 포인터는 NULL으로, int형 변수는 0으로

 

• ~unsorted 소멸자

    ~unsorted() {
        while (data != NULL) {
            Node* node;
            node = data;
            data = data->next;
            delete node;
        }
        currentpos = NULL;
        len = 0;
    }

소멸자에서 중요한 점은 heap영역에서 메모리 leak이 발생하지 않도록 하는 것이다. 따라서 data가 NULL이 될 때까지 Node 객체를 만들어서 현재 data를 넣고 data는 다음 노드를 가리키도록 한 후 Node 객체를 할당 해제해주는 작업을 반복한다. 그 후에 중요한 점은  currentpos=NULL 을 통해 댕글링 포인터가 되지 않도록 하는 것이다. 길이도 0으로 초기화 시켜준 것은 그냥 내 마음. 이 작업은 앞의 자료구조에서 배운 소멸자와 같다.

 

• full

    bool full() const {
        Node* node;
        try {
            node = new Node;
            delete node;
            return false;
        }
        catch (std::bad_alloc) {
            return true;
        }
    }

full도 마찬가지로 쉽다. bad_alloc을 처리하는 try catch 구문

 

• get(int &item)

    void get(int& item) {
        if (currentpos == NULL)
            currentpos = data;
        else
            currentpos = currentpos->next;
        
        item = currentpos->item;
    }

현재 currentpos가 NULL 상태, 즉 아무것도 가리키지 않는다면 data를 넣어주고 아니라면 다음 데이터를 가리키도록 next를 넣어준다. 그리고 item에 데이터를 레퍼런스로 반환한다. 언제 필요하냐면 리스트의 데이터를 처음부터 다 확인해볼 때 필요하다.

 

• reset

   void reset() {
        currentpos = NULL;
    }

현재 보고 있는 데이터의 위치를 초기화한다.

 

• insert(int input)

    void insert(int input) {
        if (!full()) {
            Node* node = new Node;
            node->item = input;
            node->next = data;
            data = node;
            len++;
        }
    }

input 함수도 쉽다. 중요한 것은 코드의 순서임을 기억하고 넘어가자

 

• deleted(int item) 

나왔다 오늘의 하이라이트

    void deleted(int input) {
        Node* location = data;
        bool find = false;
        
        if (input == data->item) {
            Node* node = data;
            data = data->next; // 맨 처음 노드와 비교
            delete node;
            len--;
        }
        else { 
            while (location->next != NULL && !find) {
                if ((location->next)->item == input) {
                    find = 1;
                    break;
                }
                else {
                    location = location->next;
                }
            }
            if (find == 1) {
                Node* node;
                node = location->next;
                location->next = (location->next)->next;
                delete node;
                len--;
            }
        }
        
    }

 

이 구현에서 중요한 점은 데이터를 삭제한 후 리스트간의 연결을 유지하는 것이다. 

이 함수를 구현할 때 고민할 점은 '한 노드를 삭제하고 나면 삭제한 노드의 전과 후를 연결해야 하는데 그 주소를 어떻게 알아낼 것인가' 이다.

그래서 현재 위치의 item과 비교하지말고 그 다음 노드의 item과 비교하는 것으로 해결할 수 있다. 이 때 발생하는 예외상황은 맨 처음 노드를 비교해야하는 것이다. 현재위치의 다음노드와 input을 비교 하면 맨 처음 노드의 item과 비교를 할 수 없기 때문에 if문으로 맨 처음노드와 input이 같은 경우를 예외처리 했다.

else문을 살펴보면 그 다음 노드의 item과 비교를 해야하기 때문에 location != NULL이 아닌 location->next != NULL으로 처리를 했다. while문 안에 있는 if문에서  (location->next)->item == input 를 발견할 수 있다. 이 부분이 현재위치의 다음노드와 input을 비교하는 구문이다. 그래서 같으면 find=1을 넣어서 while문을 탈출하고 if구문을 통해 삭제를 진행한다. 삭제 구문은 다른 자료구조와 동일하다. 읽어보면 이해 possible

 

• retrieve

    void retrieve(int& input, bool& find) {
        Node* location = data; 
        find = false;

        if (data->item == input) {
            find = true;
        }
        else {
            while (location->next != NULL && !find) {
                if ((location->next)->item == input) {
                    find = true;
                    break;
                }
                else {
                    location = location->next;
                }
            }
        }
    }

deleted 함수를 완벽하게 이해했다면 이 함수는 껌이다. input이 리스트안에 있는지 검사해준다. 결과값을 레퍼런스로 반환한다.

 

• length

    int length() {
        return len;
    }

easy to understand

---

비정렬 리스트 알아보기 끝! 덧붙이자면 insert 함수를 stack방식으로 구현한 것이라고도 할 수 있다. queue로도 구현할 수 있지만 굳이? 그럴려면 마지막을 알려주는 포인터가 또 필요하므로 안하는 편이 낫다.