Node.h
|
class Node { public: // 넥스트 설정 void setNext(Node* n) { next = n; } // 넥스트 불러오기 Node* getNext() { return next; } // 데이타 설정 void setData(int d) { data = d; } // 데이타 불러오기 int getData() { return data; } private: int data; Node* next; }; |
LinkedList.cpp
|
#include <iostream> #include <stdio.h> #include <stdlib.h> #include "Node.h" using namespace std; /* *node HEAD */ Node* list;
/* *초기화 */ void init() { /* * 리스트가 비어있는 경우와 아닌 경우를 찾는다 */ if (list == NULL) { return; } /* * linked list가 비어있지 않았을때 */ else { /* * cur: 노드를 참조하고 바꾸기 위해 사용 *HEAD의 다음 노드를 찾기 위해 cur에 HEAD값이 들어간다. */ Node* cur; cur = list;
/* * HEAD가 HEAD가 가리키는 노드로 바뀌고 * HEAD였던 노드를 제거한다 * 이 루프를 반복함으로써 앞에서부터 모든 노드를 하나씩 끊는다. */ while (cur != NULL) { list = cur->getNext(); // -> getNext(): 노드가 가리키는 노드를 불러온다 free(cur); cur = list; } } }
/* * 맨앞에 추가 */ void add(int key) { /* * Node 포인터 초기화 */ Node* new_node = (Node*)malloc(sizeof(Node));
/* * new_node에 데이터와 넥스트 설정 * 리스트가 비어있어서 추가되는 노드가 HEAD인지 아닌지 확인이 한다 * 리스트가 비어있는 경우 * 첫번째 들어가는 노드는 tail이 되므로 넥스트 값을 가지지 않는다 */ new_node->setData(key); new_node->setNext(NULL);
if (list == NULL) { list = new_node; }
/* * 리스트에 뭔가 들어있는 경우 * HEAD와 신규 노드를 연결 */ else { /* * 신규 노드의 다음노드를 HEAD로 지정하고 * 신규 노드가 HEAD로 된다 * 이로서 HEAD와 신규 노드가 연결된다 */ new_node->setNext(list); list = new_node; } }
/* * 뒤에 추가 */ void add_back(int key) {
Node* new_node = (Node*)malloc(sizeof(Node)); new_node->setData(key); new_node->setNext(NULL);
if (list == NULL) { list = new_node; } else { /* * HEAD를 건드리지 않고 노드를 참조하고 바꾸기 위해 빈 노드를 만들어 줍니다 * cur: 현제 참조하고있는 노드 */ Node* cur = list;
/* * cur이 마지막 노드 즉 다음에 연결된 노드가 없을때까지 cur의 다음노드로 바뀐다 * cur = cur->getNext(); 현제 노드는 다음 노드로 바뀐다 */ while (cur->getNext() != NULL) { cur = cur->getNext(); } /* * 마지막 노드에다가 뉴 노드를 연결 */ cur->setNext(new_node); } } /* * 가운데에 추가 */ void add_mid(int key, int front, int back) { /* * 넣고자 하는 노드의 정확한 위치를 찾기위해 그 위치의 앞의 값과 뒤의 값을 받습니다. */ Node* new_node = (Node*)malloc(sizeof(Node)); new_node->setData(key); new_node->setNext(NULL);
if (list == NULL) { list = new_node; } else { /* * prev: 삽입할 노드의 앞 노드 */ Node* cur = list->getNext(); Node* prev = list;
while (cur != NULL && cur->getData() != back && prev->getData() != front) { prev = cur; cur = cur->getNext();
/* * | 노드(헤드) | -> | 노드 | -> | 노드 | -> | 노드 | -> ...... -> | 노드(테일) | * cur * prev cur * prev cur * . * . * . * 넣고자 하는 노드의 위치를 찾을때까지 prev와 cur이 뒤로 한칸씩 밀려납니다 */ } /* * 신규 노드는 현제 노드를 가리키고 * 이전 노드는 신규 노드를 가리킨다 * 이로서 두 노드 사이에 한 노드가 연결된다. */ if (cur != NULL) { new_node->setNext(cur); prev->setNext(new_node); } /* * 만약 넣고자 하는 노드의 위치를 찾지못할경우 에러 메시지를 보낸다 */ else { cout << "didn't found the location"; } } }
/* * 제거 */ bool remove(int key) { /* * 리스트가 비어있을 경우 함수를 끝낸다 */ if (list == NULL) { return false; } /* * 지워야 할 노드가 HEAD일경우 * HEAD는 그 다음 노드로 바뀐다. * 지워야 할 노드를 지운다 */ if (list->getData() == key) { Node* cur = list; list = list->getNext(); free(cur); return true; } /* * 지워야 할 노드가 노드와 노드 사이일경우 * 지워야 할 노드를 찾고 제거한다 * 만약 찾지 못할경우 함수를 끝낸다 */ else { Node* cur = list->getNext(); Node* prev = list;
while (cur != NULL && cur->getData() != key) { prev = cur; cur = cur->getNext(); }
if (cur == NULL) return false;
/* * 제거하는 방법은 * 제거할 노드를 가리키는 노드를 제거할 노드의 다음 노드와 연결하고 제거한다 */ prev->setNext(cur->getNext()); free(cur); return true; } } /* * 노드 출력 */ void traverse() { Node* cur = list; while (cur != NULL) { printf("%d ", cur->getData()); cur = cur->getNext(); } printf("\n"); }
int main() { /* * menu: 값에따라 해당하는 기능의 함수를 호출한다 * number: 노드의 값 - 추가 혹은 삭제 시 모두 사용 * front, back:중간에 추가할 경우 앞뒤 노드의 위치 */ int menu = 0; int number = 0; int front = 0; int back = 0; init();
/* * Menu에 값이 5 일경우 루프를 종료한다 * switch: 해당하는 menu 값에따라 밑에 코드가 실행된다. */ while (menu != 5) { cout << "1.Add Before Head" << endl << "2.Add Middle" << endl << "3.Add Tail" << endl << "4.Remove" << endl << "5.Exit" << endl << "Enter Menu Number:"; cin >> menu;
switch (menu) { case 1: cout << "Enter Node Value(Data):"; cin >> number; add(number); traverse(); cout << endl; break;
case 2: cout << "Enter Node Value(Data):"; cin >> number; cout << "Enter Front Node Value(data):"; cin >> front; cout << "Enter Back Node Value(data):"; cin >> back; add_mid(number, front, back); traverse(); cout << endl; break;
case 3: cout << "Enter Node Value(Data):"; cin >> number; add_back(number); traverse(); cout << endl; break;
case 4: cout << "Enter Node Value(Data):"; cin >> number; remove(number); traverse(); cout << endl; break; } } } |
이 프로그램은 struct로 되어 있는 LinkedList 소스를 class를 이용하는 것으로 바꾼 것입니다.
이 프로그램의 수정은 저의 지도하에 송현고등학교 김준석학생이 하였습니다.