[Data Structure] 배열을 이용한 Linked List(연결 리스트) 구현

- 배열을 이용한 연결 리스트 구현

 연결 리스트는 보통 메모리를 동적으로 할당 받아서 데이터와 주소값을 갖고 있는 노드를 만들고, 그 노드를 이용해서 연결 리스트를 구성합니다. 그러면 메모리의 동적 할당이 안되는 상황에서 연결 리스트를 구현해야 하는 상황이라면 어떻게 해야 될까요? 저는 2개의 배열을 선언해서 하나는 데이터를 담고 다른 하나는 배열의 인덱스(데이터의 임시 주소값)를 담도록 하겠습니다.

< 출처 : http://forum.codecall.net/topic/59060-structure-of-an-array-based-linked-list/ >

 위의 그림은 2차원 배열로 구성한 연결 리스트입니다. 여기서 행(가로 축, Row)은 하나의 노드로 표현됩니다. 노드에는 item과 next가 있습니다. item은 노드가 갖고 있는 데이터를 의미하고 next는 다음 노드의 주소값(배열의 인덱스)을 의미합니다. head의 값이 0이기 때문에 리스트의 시작은 0번 인덱스가 됩니다. 0번 인덱스 배열의 값은 item이 B, next가 3 입니다. 노드가 연결된 모습은 B -> D -> E -> J -> NULL 입니다.

 배열로 구현한 연결 리스트도 삽입, 삭제 연산을 할 수 있는데 기본적인 연결 리스트와 똑같은 방법으로 구성하면 됩니다. 삽입의 경우에는 삽입할 위치를 찾고 앞 노드의 next 값을 적절하게 수정해주면 됩니다. 이 경우에 배열에 빈 자리가 있는지 확인하는 예외 처리 과정을 해줘야 합니다. 삭제의 경우에도 앞 노드의 next 값을 적절하게 수정해주면 됩니다. 아래는 전체 코드입니다.

- header 파일

#include 
#include 
using namespace std;

class LinkedList{
private:
    int head;
    char* values;
    int* addresses;
    int size = 0;
    
public:
    LinkedList(int size);
    void initializeList(int size);
    int getEmptyLocation();
    void addNode(char newValue);
    void deleteNode(char garbageValue);
    void printList();
};

- cpp 파일

#include "LinkedList.hpp"

LinkedList::LinkedList(int size){
    head = -1;
    values = new char[size];
    addresses = new int[size];
    
    for(int i=0;i<size;i++){
        values[i] = '\0';
        addresses[i] = -1;
    }
}

int LinkedList::getEmptyLocation(){
    int length = sizeof(values)/sizeof(values[0]);
    
    for(int i=0;i<length;i++){
        if(values[i] == '\0'){
            return i;
        }
    }
    
    return -1;
}

void LinkedList::addNode(char newValue) {
    int now = head;
    int emptyLocation = -1;
    
    if(size == 0){
        values[0] = newValue;
        head = 0;
        size++;
        return;
    }
    
    emptyLocation = getEmptyLocation();
    if(emptyLocation == -1){
        cout << "List is Full\n";
        return;
    }
    
    while(addresses[now] != -1){
        now = addresses[now];
    }
    
    values[emptyLocation] = newValue;
    addresses[now] = emptyLocation;
    size++;
}

void LinkedList::deleteNode(char garbageValue){
    int priorIndex = -1;
    int now = head;
    bool isGarbageValue = false;
    
    while(addresses[now] != -1){
        priorIndex = now;
        now = addresses[now];
        if(values[now] == garbageValue){
            isGarbageValue = true;
            break;
        }
    }
    
    if(isGarbageValue == false){
        cout << "Garbage Value isn't in The List\n";
        return;
    }
    
    if(now == head){
        head = addresses[now];
    }else{
        addresses[priorIndex] = addresses[now];
    }
    
    values[now] = NULL;
    addresses[now] = -1;
    size--;
}

void LinkedList::printList(){
    int now = head;
    
    if(size == 0){
        cout << "List is Empty\n";
        return;
    }
    
    cout << values[now] << "->";
    while(addresses[now] != -1){
        now = addresses[now];
        cout << values[now] << "->";
    }
    cout << endl;
}