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

insert_after와 erase_after, ListBeforeBegin을 사용한 버전.

dummy하나와 노드 뿐이라 만들어놓고 보니 만들기 간편하다 (근데 오래걸렸음)

코드를 이해하기도 쉽다는건 버그를 발견하기도 편이하다는 뜻이기에 괜찮은 것 같다.

main.cpp

#include "linked.h"

bool checkFunc(LDATA data)

{

if (data % 2 == 0) return true;

return false;

}

void test1()

{

LIST list;

NODE* pos;

pos = L_insert_after(ListBeforeBegin(&list),11);

pos = L_insert_after(pos, 22);

pos = L_insert_after(pos, 33);

pos = L_insert_after(pos, 44);

L_insert_after(pos, 55);

L_insert_after(pos, 66);

NODE* another = ListAdvance(ListBeforeBegin(&list), 2);

L_insert_after(another, 99);

for (NODE* iter = ListBeforeBegin(&list); ListNext(iter); iter = ListNext(iter))

{

cout << ListNext(iter)->_data << endl;

}

cout << "==========================================================================\n";

for (NODE* iter = ListBeforeBegin(&list); ListNext(iter); )

{

if(! L_erase_after_if(iter, checkFunc)) 

iter = ListNext(iter);

}

cout << "==========================================================================\n";

for (NODE* iter = ListBeforeBegin(&list); ListNext(iter); iter = ListNext(iter))

{

cout << ListNext(iter)->_data << endl;

}

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

}

void main()

{

test1();

}

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 };

} LIST;

//void Push_back(LIST* list, LDATA data);

NODE* L_insert_after(NODE* target, LDATA data);

NODE* L_erase_after(NODE* target);

bool L_erase_after_if(NODE* target, bool(*pred)(LDATA data));

NODE* ListBegin(LIST* list);

NODE* ListEnd();

NODE* ListBeforeBegin(LIST* list);

NODE* ListNext(NODE* node);

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

NODE* _MakeNode(LDATA data);

bool ListDestroy(LIST* list);

linked.cpp

#include "linked.h"

NODE* L_insert_after(NODE* target, LDATA data)

{

if (!target) return nullptr;

NODE* newNode = _MakeNode(data);

newNode->_next = target->_next;

target->_next = newNode;

return newNode;

}

NODE * L_erase_after(NODE * target)

{

if (!target || !target->_next) return nullptr;

NODE* temp = target->_next;

target->_next = target->_next->_next;

free(temp);

return target->_next;

}

bool L_erase_after_if(NODE * target, bool(*pred)(LDATA data))

{

if (!target || !target->_next) return nullptr;

if (pred(target->_next->_data))

{

L_erase_after(target);

return true;

}

else

return false;

}

NODE * ListBegin(LIST* list)

{

return list->_head->_next;

}

NODE * ListEnd()

{

return nullptr;

}

NODE * ListBeforeBegin(LIST * list)

{

return list->_head;

}

NODE * ListNext(NODE * node)

{

if (!node) return nullptr;

return node->_next;

}

NODE * ListAdvance(NODE * node, int n)

{

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

{

if (!node) break;

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;

}