[자료구조] linked list 를 구현해보자-.

  Linked List는 대학교 과정부터 지겹게(??;;) 들어온 자료구조입니다.
  학교 다닐 때 과제로 간단하게 만들어보고 난 이후에는 개발하면서 직접 구현해서 사용한 적은 거의 없었죠...
  C++에는 이미 잘 만들어진 stl 이라는 녀석도 있고,  java에도 물론 있으니.. 
   게다가 취업하고 나니..회사에서 만들어놓은 라이브러리도 있고...

  그런식으로 개발을 몇년간 하다보니 이러한 간단한 자료구조들(하지만 중요한!)에 대해서 실제 안다고 생각은 하지만, 지금 당장 코딩하라고 하면 몇분 안에 코딩할 수 있나? 라는 의문이 들었습니다. 그리고 예전에 배울 때 느꼈던 것과 지금 다시 보면 무엇인가 또 다른것을 느낄 수 있을꺼라는 기대감이 기초부터 다시 공부하자는 결심을 하는데 한몫했습니다.
 
  요즘들어 제 자신이 발전하고 있다는 느낌보다는 어디서간 꽉 막혀있다는 느낌을 많이 받았거든요.. 예전 C언어를 배울 때 포인터라는 녀석 앞에서 좌절했던 것 처럼.....



  요즘 한참 프로젝트 기간이라 바빠서 할 시간은 별로 없지만....틈틈히 머리 식힐겸 하나씩 만들어보려고 합니다..

  오늘은 그 첫번째로 가장 많이 사용되는 Linked List !

  그리고 최근에 관심을 가지게 된 TDD(test driven development)를 적용해보았습니다..(업무에 바로 적용해보려고 노력해봤지만, 생각보다 적용하기가 어렵더라구요.)

  경고! 학교 리포트로 제출하지 마세요-_-....
  버그가 있을 가능성도 많으니 참고만 하세요..-_-

list.h

#define TRUE 1
#define FALSE 0
#include <stdio.h>

typedef struct ListItem {
	int no;
} ListItem;

typedef struct Node {
	struct Node *prev;
	struct Node *next;
	struct ListItem item;
} Node;

typedef struct list {
	struct Node *head;
	struct Node *tail;
	int		nodeCnt;
} LinkedList;

LinkedList* initList();
void freeList(LinkedList *list);
char* listLog(LinkedList *list);
int push_front(LinkedList *l, ListItem item);
int push_back(LinkedList *l, ListItem item);
int insert(LinkedList *l, int postion, ListItem item);
int pop_front(LinkedList *l, ListItem *item=NULL);
int pop_back(LinkedList *l, ListItem *item=NULL);
int get_front(LinkedList *l, ListItem *item);
int get_back(LinkedList *l, ListItem *item);
int get_item(LinkedList *l, int position, ListItem *item);
int remove_item(LinkedList *l, int position, ListItem *item=NULL);

list.c

#include "list.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

LinkedList* initList()
{
	LinkedList *newlist = (LinkedList*)malloc(sizeof(LinkedList));
	newlist->head = NULL;
	newlist->tail = NULL;
	newlist->nodeCnt = 0;

	return newlist;
}

void freeList(LinkedList *list)
{
	if ( list != NULL ) {
		Node *node = list->head;
		while(node) {
			Node *nextNode = node->next;
			free(node);
			node = nextNode;
		}
		free(list);
	} else {
		printf("ERROR!!!\n");
		return;
	}
}

/**
 * for debug
 */
char* listLog(LinkedList *list)
{
	static char log[256];
	memset(log, 0, sizeof(log));

	if ( list != NULL ) {
		Node *node = list->head;
		while(node) {
			sprintf(log,"%s%d ",log, node->item.no);
			node = node->next;
		}
	} else {
		printf("ERROR!!!\n");
		return NULL;
	}

	return log;
}

/**
 * list의 가장 앞부분에 추가된다.
 */
int push_front(LinkedList *l, ListItem item)
{
	Node *newNode = (Node*)malloc(sizeof(Node));
	newNode->item = item;
	newNode->next = NULL;
	newNode->prev = NULL;

	if ( l->nodeCnt == 0 ) { 	// empty
		l->head = newNode;
		l->tail = newNode;
	} else {
		l->head->prev = newNode;
		newNode->next = l->head;
		l->head = newNode;
	}

	l->nodeCnt++;

	return TRUE;
}

/**
 * list의 가장 마지막에 추가된다.
 */
int push_back(LinkedList *l, ListItem item)
{
	Node *newNode = (Node*)malloc(sizeof(Node));
	newNode->item = item;
	newNode->next = NULL;
	newNode->prev = NULL;

	if ( l->nodeCnt == 0 ) {	// empty
		l->head = newNode;
		l->tail = newNode;
	} else {
		newNode->prev = l->tail;
		l->tail->next = newNode;
		l->tail = newNode;
	}

	l->nodeCnt++;
	return TRUE;
}

Node* getNodeByPos(LinkedList *l, int position)
{
	if ( position < 0 || position > l->nodeCnt ) {
		return NULL;
	}

	Node *currNode = l->head;
	int i = 0;

	while(currNode != NULL ) {
		if ( position == i ) {
			return currNode;
		}
		currNode = currNode->next;
		i++;
	}

	return NULL;
}

/**
 * position 자리에 item을 삽입한다.
 * 기존 position에 있던 item의 앞으로 추가된다.
 */
int insert(LinkedList *l, int position, ListItem item)
{
	if ( l->nodeCnt == position ) {
		return push_back(l, item);
	} else if ( position == 0 ) {
		return push_front(l, item);
	} else if ( position < 0 || position > l->nodeCnt ) {
		return FALSE;
	} else {
		Node *currNode = getNodeByPos(l, position);
		if ( currNode == NULL ) {
			return FALSE;
		}

		Node *prevNode = currNode->prev;

		Node *newNode = (Node*)malloc(sizeof(Node));
		newNode->item = item;
		newNode->next = NULL;
		newNode->prev = NULL;

		prevNode->next = newNode;
		newNode->prev = prevNode;

		newNode->next = currNode;
		currNode->prev = newNode;

		l->nodeCnt++;
	}

	return TRUE;
}

void freeNode(Node *node)
{
	free(node);
}

int pop_front(LinkedList *l, ListItem *item)
{
	Node *head = l->head;

	if ( l->nodeCnt == 0 || head == NULL ) {
		return FALSE;
	}
	if ( item != NULL )
		memcpy(item, &head->item, sizeof(ListItem));

	Node *nextNode = head->next;

	if ( nextNode == NULL ) { // 마지막 Node 일 때
		l->head = NULL;
		l->tail = NULL;
	} else {					// 그 외의 경우
		l->head = nextNode;
		nextNode->prev = NULL;
	}

	freeNode(head);
	l->nodeCnt--;

	return TRUE;
}

int pop_back(LinkedList *l, ListItem *item)
{
	Node *tail = l->tail;

	if ( l->nodeCnt == 0 || tail == NULL ) {
		return FALSE;
	}

	if ( item != NULL ) 
		memcpy(item, &tail->item, sizeof(ListItem));

	Node *prevNode = tail->prev;

	if ( prevNode == NULL ) {	// 마지막 Node 일 경우 
		l->head = NULL;
		l->tail = NULL;
	} else {
		l->tail = prevNode;
		prevNode->next = NULL;
	}

	freeNode(tail);
	l->nodeCnt--;

	return TRUE;
}

int get_front(LinkedList *l, ListItem *item)
{
	Node *head = l->head;

	if ( l->nodeCnt == 0 || head == NULL ) {
		return FALSE;
	}
	memcpy(item, &head->item, sizeof(ListItem));

	return TRUE;
}

int get_back(LinkedList *l, ListItem *item)
{
	Node *tail = l->tail;

	if ( l->nodeCnt == 0 || tail == NULL ) {
		return FALSE;
	}

	memcpy(item, &tail->item, sizeof(ListItem));

	return TRUE;
}

int get_item(LinkedList *l, int position, ListItem *item)
{
	Node *node =  getNodeByPos(l, position);

	if ( node == NULL ) {
		return FALSE;
	}

	memcpy(item, &node->item, sizeof(ListItem));

	return TRUE;
}

int remove_item(LinkedList *l, int position, ListItem *item)
{
	if ( l->nodeCnt == position+1 ) {
		return pop_back(l, item);
	} else if ( position == 0 ) {
		return pop_front(l, item);
	}

	Node *node =  getNodeByPos(l, position);
	if ( node == NULL ) {
		return FALSE;
	}

	if ( item != NULL )
		memcpy(item, &node->item, sizeof(ListItem));

	Node *prev = node->prev;
	Node *next = node->next;

	prev->next = node->next;
	next->prev = node->prev;

	l->nodeCnt--;

	return TRUE;
}

tdd.c

#include <stdio.h>
#include <gtest/gtest.h>
#include "list.h"

class listPushtest : public testing::Test {
public:
	LinkedList *testList;

	virtual void SetUp()
	{
		testList = initList();
	}

	virtual void TearDown()
	{
		freeList(testList);
	}
};

TEST_F(listPushtest, push_front_add_test)
{
	ListItem pushItem;
	pushItem.no = 1;

	EXPECT_EQ(push_front(testList, pushItem), TRUE);
	EXPECT_EQ(testList->nodeCnt, 1);
	EXPECT_EQ(testList->head->item.no, 1);
	EXPECT_EQ(testList->tail->item.no, 1);

	pushItem.no = 2;
	EXPECT_EQ(push_front(testList, pushItem), TRUE);
	EXPECT_EQ(testList->nodeCnt, 2);
	EXPECT_EQ(testList->head->item.no, 2);
	EXPECT_EQ(testList->tail->item.no, 1);

	EXPECT_EQ(strcmp("2 1 ", listLog(testList)), 0);
}

TEST_F(listPushtest, push_back_add_test)
{
	ListItem pushItem;
	pushItem.no = 1;

	EXPECT_EQ(push_back(testList, pushItem), TRUE);
	EXPECT_EQ(testList->nodeCnt, 1);
	EXPECT_EQ(testList->head->item.no, 1);
	EXPECT_EQ(testList->tail->item.no, 1);

	pushItem.no = 2;
	EXPECT_EQ(push_back(testList, pushItem), TRUE);
	EXPECT_EQ(testList->nodeCnt, 2);
	EXPECT_EQ(testList->head->item.no, 1);
	EXPECT_EQ(testList->tail->item.no, 2);


	EXPECT_EQ(strcmp("1 2 ", listLog(testList)), 0);
}

TEST_F(listPushtest, insert_outofindex_test)
{
	ListItem pushItem;
	pushItem.no = 1;

	EXPECT_EQ(insert(testList, -1, pushItem), FALSE);
	EXPECT_EQ(insert(testList, 1, pushItem), FALSE);
	EXPECT_EQ(insert(testList, 3, pushItem), FALSE);


	EXPECT_EQ(insert(testList, 0, pushItem), TRUE);
	EXPECT_EQ(testList->nodeCnt, 1);
	EXPECT_EQ(testList->head->item.no, 1);
	EXPECT_EQ(testList->tail->item.no, 1);
	EXPECT_EQ(strcmp("1 ",listLog(testList)), 0);


	pushItem.no = 2;
	EXPECT_EQ(insert(testList, 0, pushItem), TRUE);
	EXPECT_EQ(strcmp("2 1 ",listLog(testList)), 0);


	pushItem.no = 3;
	EXPECT_EQ(insert(testList, 1, pushItem), TRUE);
	EXPECT_EQ(strcmp("2 3 1 ",listLog(testList)), 0);


	pushItem.no = 4;
	EXPECT_EQ(insert(testList, 3, pushItem), TRUE);
	EXPECT_EQ(strcmp("2 3 1 4 ",listLog(testList)), 0);

	pushItem.no = 5;
	EXPECT_EQ(insert(testList, 2, pushItem), TRUE);
	EXPECT_EQ(strcmp("2 3 5 1 4 ",listLog(testList)), 0);
}

class listPopTest : public testing::Test {
public:
	LinkedList *testList;

	// initial list status : 3 2 1
	virtual void SetUp()
	{
		testList = initList();
		ListItem pushItem;
		pushItem.no = 1;
		push_front(testList, pushItem);
		pushItem.no = 2;
		push_front(testList, pushItem);
		pushItem.no = 3;
		push_front(testList, pushItem);
	}

	virtual void TearDown()
	{
		freeList(testList);
	}
};

TEST_F(listPopTest, pop_front_test) 
{
	ListItem popItem;

	EXPECT_EQ(pop_front(testList,&popItem), TRUE);
	EXPECT_EQ(popItem.no, 3);
	EXPECT_EQ(testList->nodeCnt, 2);

	EXPECT_EQ(pop_front(testList,&popItem), TRUE);
	EXPECT_EQ(popItem.no, 2);
	EXPECT_EQ(testList->nodeCnt, 1);

	EXPECT_EQ(pop_front(testList,&popItem), TRUE);
	EXPECT_EQ(popItem.no, 1);
	EXPECT_EQ(testList->nodeCnt, 0);

	EXPECT_EQ(pop_front(testList,&popItem), FALSE);
}

TEST_F(listPopTest, pop_back_test)
{
	ListItem popItem;

	EXPECT_EQ(pop_back(testList,&popItem), TRUE);
	EXPECT_EQ(popItem.no, 1);
	EXPECT_EQ(testList->nodeCnt, 2);

	EXPECT_EQ(pop_back(testList,&popItem), TRUE);
	EXPECT_EQ(popItem.no, 2);
	EXPECT_EQ(testList->nodeCnt, 1);

	EXPECT_EQ(pop_back(testList,&popItem), TRUE);
	EXPECT_EQ(popItem.no, 3);
	EXPECT_EQ(testList->nodeCnt, 0);

	EXPECT_EQ(pop_back(testList,&popItem), FALSE);
}

TEST_F(listPopTest, get_front_test)
{
	ListItem frontItem;

	EXPECT_EQ(get_front(testList,&frontItem), TRUE);
	EXPECT_EQ(frontItem.no, 3);
	EXPECT_EQ(testList->nodeCnt, 3);

	EXPECT_EQ(get_front(testList,&frontItem), TRUE);
	EXPECT_EQ(frontItem.no, 3);
	EXPECT_EQ(testList->nodeCnt, 3);

	EXPECT_EQ(strcmp("3 2 1 ",listLog(testList)), 0);
}

TEST_F(listPopTest, get_back_test)
{
	ListItem backItem;

	EXPECT_EQ(get_back(testList,&backItem), TRUE);
	EXPECT_EQ(backItem.no, 1);
	EXPECT_EQ(testList->nodeCnt, 3);

	EXPECT_EQ(get_back(testList,&backItem), TRUE);
	EXPECT_EQ(backItem.no, 1);
	EXPECT_EQ(testList->nodeCnt, 3);

	EXPECT_EQ(strcmp("3 2 1 ",listLog(testList)), 0);
}


TEST_F(listPopTest, get_item_test)
{
	ListItem item;

	EXPECT_EQ(get_item(testList, 1, &item), TRUE);
	EXPECT_EQ(item.no, 2);

	EXPECT_EQ(get_item(testList, 2, &item), TRUE);
	EXPECT_EQ(item.no, 1);

	EXPECT_EQ(get_item(testList, 3, &item), FALSE);
}

TEST_F(listPopTest, remove_item_test)
{
	ListItem item;

	EXPECT_EQ(remove_item(testList, 1, &item), TRUE);
	EXPECT_EQ(remove_item(testList, 1, &item), TRUE);
	EXPECT_EQ(remove_item(testList, 0, &item), TRUE);
}


int main(int argc, char *argv[])
{
	testing::InitGoogleTest(&argc, argv);
	return RUN_ALL_TESTS();
}

실행결과

dino-laptop:~/hcWorld/LinkedList> ./listTest.exe
[==========] Running 9 tests from 2 test cases.
[----------] Global test environment set-up.
[----------] 3 tests from listPushtest
[ RUN      ] listPushtest.push_front_add_test
[       OK ] listPushtest.push_front_add_test (0 ms)
[ RUN      ] listPushtest.push_back_add_test
[       OK ] listPushtest.push_back_add_test (0 ms)
[ RUN      ] listPushtest.insert_outofindex_test
[       OK ] listPushtest.insert_outofindex_test (0 ms)
[----------] 3 tests from listPushtest (0 ms total)

[----------] 6 tests from listPopTest
[ RUN      ] listPopTest.pop_front_test
[       OK ] listPopTest.pop_front_test (1 ms)
[ RUN      ] listPopTest.pop_back_test
[       OK ] listPopTest.pop_back_test (0 ms)
[ RUN      ] listPopTest.get_front_test
[       OK ] listPopTest.get_front_test (0 ms)
[ RUN      ] listPopTest.get_back_test
[       OK ] listPopTest.get_back_test (0 ms)
[ RUN      ] listPopTest.get_item_test
[       OK ] listPopTest.get_item_test (0 ms)
[ RUN      ] listPopTest.remove_item_test
[       OK ] listPopTest.remove_item_test (0 ms)
[----------] 6 tests from listPopTest (1 ms total)

[----------] Global test environment tear-down
[==========] 9 tests from 2 test cases ran. (3 ms total)
[  PASSED  ] 9 tests.
dino-laptop:~/hcWorld/LinkedList>