구현 - 싱글 링크드 리스트 ver1

헤드 더미를 두고 prev와 tail을 넣는 방식. tail은 push_back에서만 관리하면 된다지만, prev는 언제 설정해줘야하는지 생각해야한다.

이 insert로는 리스트의 맨 끝에 자료를 넣지 못하기에 push_back을 사용해야한다. 따라서 tail을 둬야한다.

tail과 prev를 관리해줘야 하기에 버그가 발생하기 좋다. 밑에 코드도 버그가 분명 있을 것이다.

linked.h

#pragma once

#include <iostream>

using namespace std;

typedef int LDATA;

typedef struct tagSingleNode

{

LDATA _data{};

tagSingleNode* _next{};

} NODE;

typedef struct tagList

{

NODE _dummy{};

NODE* _head{ &_dummy };

NODE* _tail{ &_dummy };

NODE* _prev{ };

} LIST;

void Push_back(LIST* list, LDATA data);

NODE* Insert(LIST* list, NODE* where, LDATA data);

NODE* Erase(LIST* list, NODE* n);

NODE* ListBegin(LIST* list);

NODE* ListEnd(LIST* list);

NODE* ListNext(LIST* list, NODE* node);

NODE* ListAdvance(LIST* list, NODE* node, int n);

NODE* _MakeNode(LDATA data);

bool ListDestroy(LIST* list);

linked.cpp

#include "linked.h"

void Push_back(LIST * list, LDATA data)

{

NODE* newNode = _MakeNode(data);

if (!list->_head->_next)

list->_head->_next = newNode;

list->_tail->_next = newNode;

list->_tail = newNode;

}

NODE* Insert(LIST* list, NODE* place, LDATA data)

{

NODE* newNode = _MakeNode(data);

newNode->_next = place;

list->_prev->_next = newNode;

return newNode;

}

NODE * Erase(LIST * list, NODE * target)

{

list->_prev->_next = target->_next;

if (list->_tail == target)

list->_tail = list->_prev;

free(target);

return list->_prev->_next;

}

NODE * ListBegin(LIST* list)

{

list->_prev = list->_head;

return list->_head->_next;

}

NODE * ListEnd(LIST * list)

{

return list->_tail->_next;

}

NODE * ListNext(LIST * list, NODE * node)

{

list->_prev = node;

return node->_next;

}

NODE * ListAdvance(LIST * list, NODE * node, int n)

{

for (int i = 0; i < n; ++i)

{

if (!node) break;

list->_prev = node;

node = node->_next;

}

if (!node) throw exception("list advance reached nullptr");

return node;

}

NODE * _MakeNode(LDATA data)

{

NODE* n = (NODE*)malloc(sizeof(NODE));

n->_data = data;

n->_next = nullptr;

return n;

}

bool ListDestroy(LIST * list)

{

NODE* curr = list->_head->_next;

while (curr)

{

NODE* temp = curr->_next;

free(curr);

curr = temp;

}

return true;

}

main.cpp

#include "linked.h"

void test1()

{

LIST list;

Push_back(&list, 20);

Push_back(&list, 40);

Push_back(&list, 50);

Push_back(&list, 60);

for (NODE* iter = ListBegin(&list); iter != ListEnd(&list); )

{

if (iter->_data <= 40)

{

iter = Erase(&list, iter);

}

else

iter = ListNext(&list, iter);

}

for (NODE* iter = ListBegin(&list); iter != ListEnd(&list); iter = ListNext(&list, iter))

{

cout << iter->_data << endl;

}

if(ListDestroy(&list)) cout << "des ok!\n";

}

void test2()

try{

LIST list;

Push_back(&list, 20);

Push_back(&list, 40);

Push_back(&list, 50);

Push_back(&list, 60);

for (NODE* iter = ListBegin(&list); iter != ListEnd(&list); iter = ListNext(&list, iter))

{

cout << iter->_data << endl;

}

NODE* iter = ListAdvance(&list, ListBegin(&list), 3);

cout << iter->_data << " 자리에 " << "999 넣기\n";

iter = Insert(&list, iter, 999);

iter = ListAdvance(&list, iter, 1);

Erase(&list, iter);

for (NODE* iter = ListBegin(&list); iter != ListEnd(&list); iter = ListNext(&list, iter))

{

cout << iter->_data << endl;

}

if(ListDestroy(&list)) cout << "des ok!\n";

}

catch (exception& e)

{

cerr << e.what() << endl;

}

void main()

{

test2();

}