:: 행복하기 :: :: [자료구조] linked list 를 구현해보자-.

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

2009/10/12 20:20 : 컴퓨터 이야기

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

그런식으로 개발을 몇년간 하다보니 이러한 간단한 자료구조들(하지만 중요한!)에 대해서 실제 안다고 생각은 하지만, 지금 당장 코딩하라고 하면 몇분 안에 코딩할 수 있나? 라는 의문이 들었습니다. 그리고 예전에 배울 때 느꼈던 것과 지금 다시 보면 무엇인가 또 다른것을 느낄 수 있을꺼라는 기대감이 기초부터 다시 공부하자는 결심을 하는데 한몫했습니다.

요즘들어 제 자신이 발전하고 있다는 느낌보다는 어디서간 꽉 막혀있다는 느낌을 많이 받았거든요.. 예전 C언어를 배울 때 포인터라는 녀석 앞에서 좌절했던 것 처럼.....

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

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

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

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

list.h

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(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(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>

'컴퓨터 이야기' 카테고리의 다른 글

유용한 크롬 확장 프로그램들.. (3)	2010/02/28
serial port를 logging 하자- (0)	2009/10/27
[자료구조] linked list 를 구현해보자-. (4)	2009/10/12
AOP(Aspect Oriented Programming) 그리고.. aspect C++ 에 대해서.. (3)	2009/07/04
vi에서 현재 작업중인 함수이름 출력하기 (0)	2009/06/20
ASCII Generator (0)	2009/03/17

TAGC, linkedlist, 링크드리스트, 자료구조, 프로그래밍

Posted by heestory.kr Trackback 0 Comment 4

Trackback : http://heestory.kr/trackback/326

댓글을 달아 주세요

댓글주소 수정/삭제 댓글쓰기 청하 2009/10/13 10:48
으흐흐~ 열혈공부맨~ㅋㅋ
- 댓글주소 수정/삭제 heestory.kr 2009/10/13 10:49
  청하씨 따라가려면 멀었죠..-ㅋㅋㅋㅎㅎ
댓글주소 수정/삭제 댓글쓰기 sozu 2009/10/14 12:00
에이~~ 나도 언능 껴주삼!ㅋ
- 댓글주소 수정/삭제 heestory.kr 2009/10/14 13:49
  청하씨는 이거 다 아니까 할필요없삼-ㅋㅋ

<이전 1 ... 10 11 12 13 14 15 16 17 18 ... 304 다음>

:: 행복하기 ::

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

'컴퓨터 이야기' 카테고리의 다른 글

Trackback : http://heestory.kr/trackback/326

댓글을 달아 주세요

카테고리

달력

공지사항

태그목록

최근에 올라온 글

최근에 달린 댓글

최근에 받은 트랙백

글 보관함

링크

< 2010.07 >
일	월	화	수	목	금	토
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30	31