자료구조 - 리스트

앞서 배열도 배우고, 연결리스트도 배워보았다. 이번에는 이를 좀더 심도있게 배워보는 시간을 가지도록 하겠다.

---

배열리스트

// ArrayList.h

#include <cstdio>
#define MAX_LIST_SIZE 100;

class ArrayList {
	int data[MAX_LIST_SIZE];
    int length;
public:
	ArrayList(void) { length = 0; }
    
    void insert(int pos, int e) {
    	if(!isFull() && 0 <= pos && pos <= length) {
        	for(int i = length; i>pos; i--){
            	data[i] = data[i-1];
                data[pos] = e;
                length++; }
        }
        else{ printf("포화상태 오류 또는 삽입위치 오류"); }
    }
    void remove(int pos) {
    	if(!isEmpty() && 0 <= pos && pos < length) {
        	for(int i = pos+1; i< length; i++){
            	data[i-1] = data[i];}
            length--;
        }
        else{ printf("공백상태 오류 또는 삭제위치 오류"); }
    }
    int getEntry(int pos) { return data[pos]; }
    bool isEmpty() { return length == 0; }
    bool isFull() { return length == MAX_LIST_SIZE; }
    bool find(int item) {
    	for(int i =0; i<length; i++){
        	if(data[i] == item) {return true;}
        return false;
        }
    }
    void replace(int pos, int e) { data[pos] = e; }
    int size() { return length; }
    void display() {
    	printf(" [배열로 구현한 리스트 전체 항목 수 = %2d] : ", size());
        for(int i = 0; i<size(); i++){
        	printf(" [%2d] ", data[i]}
        printf("\n");
   }
   void clear() {length = 0; }
};

---

연결리스트

// Node.h
#include <cstdio>

class Node {
	Node* link;
    int data;
 public:
 	Node( int val = 0) : data(val), link(NULL) { }
    Node* getLink() { return link; }
    void setLink(Node* next) { link = next; }
    void display() { printf(" <%2d>", data); }
    bool hasData(int val) { return data == val; }
    void insertNext(Node* n) {
    	if(n != NULL){
        	n->link = link;
            link = n;
        }
     }
     Node* removeNext() {
     	Node* removed = link;
        if(removed != NULL ) { link = removed->link; }
        return removed;
     }
};

// LinkedList.h

#include "Node.h"
#include <cstdio>

class LinkedList {
	Node org;
public:
	LinkedList() org(0) { }
    ~LinkedList() { clear(); }
    
    Node* getHead() { return org.getLink(); }
    bool isEmpty() { return getHead() == NULL; }
    
    void clear(){
    	while(!isEmpty()){
        	delete remove(0);}
    }
    Node* getEntry(int pos){
    	Node* n = &org;
        for(int i = -1; i <pos; i++, n=n->getLink()){
        	if( n == NULL) { break; }
        return n;
    }
    void insert(int pos, Node* n){
    	Node* prev = getEntry(pos -1);
        if(prev != NULL){
        	prev->insertNext(n);}
    }
    Node* remove(int post){
    	Node* prev = getEntry(pos-1);
        return prev->removeNext();
    }
    Node* find(int val){
    	for(Node* p=getHead(); p != NULL; p = p->getLink()){
        	if(p->hasData(val)) { return p; }
        return NULL;
    }
    void replace(int pos, Node* n){
    	Node* prev = getEntry(pos-1);
        if(prev != NULL){
        	delete prev->removeNext();
            prev->insertNext(n);
        }
     }
};