링크드 리스트의 이해

소개글

링크드 리스트의 이해 에 대한 보고서 자료입니다.

목차

1절. 개요
1. 링크드 리스트의 종류

2절. 링크드리스트의 구현
1. 삽입,삭제
1). 노드 삽입
2). 노드 삭제
3). 데이타 보여주기
4). 링크드 리스트 데이타추상 구현

본문내용

용한다.
Node *SNode; // 시작노드를 포인트한다.
Node *NNode; // 다음노드를 포인트한다.
Node *ENode; // 마지막노드를 포인트한다.
public:
// 생성자
List()
{
node_num = 0;
};
// 삽입관련 메서드 ------------------------
// 가장뒤에 노드를 추가한다.
// 마지막 노드 정보를 가지고 있음으로
// 새로운 노드를 할당하고 기존의 마지막노드가
// NULL대신 새로할당된 노드를 가리키게 하면 된다.
void push_back(T data)
{
mNode = new Node;
mNode->Data = data;
mNode->NextNode = NULL;
if (node_num == 0)
{
SNode = mNode;
ENode = mNode;
}
else
{
ENode->NextNode = mNode;
ENode = mNode;
}
node_num++;
};
// 가장앞에 노드를 추가한다.
// 만약 처음으로 노드가 추가되는거라면
// 이 노드는 다음노드로 NULL을 가리키게 된다.
// 그렇지 않을경우 기존에 가장 처음에 있던 노드를
// 가리키게 된다.
void push_front(T data)
{
mNode = new Node;
mNode->Data = data;
mNode->NextNode = NULL;
if (node_num == 0)
{
SNode = mNode;
}
else
{
mNode->NextNode = SNode;
SNode = mNode;
}
node_num++;
};
// 임의의 위치에 노드를 삽입한다.
int insert(T data, int position)
{
Node *PNode;
int i = 0;
if (position > node_num)
{
return -1;
}
// 처음과 마지막 위치에
// 삽입할때는 이미 만들어진 메서드를
// 활용한다.
if (position == 0)
{
push_front(data);
return 1;
}
if (position == node_num)
{
push_back(data);
return 1;
}
mNode = new Node;
mNode->Data = data;
mNode->NextNode = NULL;
NNode = SNode;
while(NNode)
{
if (i == position)
{
mNode->NextNode = NNode;
PNode->NextNode = mNode;
node_num++;
break;
}
PNode = NNode;
NNode = NNode->NextNode;
i++;
}
return 1;
}
// 삭제 관련 메서드 -------------------------
// 가장앞에 있는 노드를 삭제
void pop_front()
{
NNode = SNode->NextNode;
delete SNode;
SNode = NNode;
node_num--;
}
// 가장뒤에 있는 노드를 삭제
// 싱글 링크드 리스트라서 가장뒤에 있는 노드를
// 지울경우 어쩔수 없이 처음부터 노드를 검색하는 수
// 밖에 없다.
// 더블링크드 리스트라면 좀더 쉽게 삭제 가능할것이다.
void pop_back()
{
int i = 0;
Node *PNode;
NNode = SNode;
while(1)
{
if(i == node_num - 1)
{
PNode->NextNode = NULL;
delete(NNode);
break;
}
PNode = NNode;
NNode = NNode->NextNode;
i++;
}
node_num--;
}
// 값 가져오기 메서드 -----------------------
// 가장앞의 노드에서 데이타를 가져온다.
T front()
{
return SNode->Data;
}
// 가장뒤의 노드에서 데이타를 가져온다.
T back()
{
return ENode->Data;
}
// 노드를 순환하면서 모든 데이타를 출력한다.
void show()
{
NNode = SNode;
while(NNode)
{
cout << NNode->Data << endl;
NNode = NNode->NextNode;
}
}
// 임의의 위치에 있는 노드의 데이타를
// 가져온다.
// 이 메서드는 비효율적이고 깔끔하지 못하다.
// 바꿔보자.
T get(int num)
{
int i = 0;
if (num > node_num)
{
return NULL;
}
NNode = SNode;
while(i < num)
{
NNode = NNode->NextNode;
i++;
}
return NNode->Data;
}
// 부가 메서드 -----------------------------
int size()
{
return node_num;
}
};
int main()
{
List list;
// 테스트
list.push_back("A");
list.push_back("B");
list.push_back("C");
list.push_front("D");
list.insert("100", 1);
list.push_front("101");
cout << "Size " << list.size() << endl;
cout << "First Data is " << list.front() << endl;
cout << "Last Data is " << list.back() << endl;
list.show();
list.pop_front();
list.show();
list.pop_back();
list.show();
cout <<"GET DATA" << list.size() << endl;
for (int i =0; i < list.size(); i++)
{
cout << list.get(i) << endl;
}
}
3절. 결론
이상 링크드리스트와 링크드리스트 데이타 추상에 대해서 알아보았다. 이로써 기본자료구조인 스택,큐,링크드리스트에 대한 기본적인 내용을 모두 다루었다. 다음번부터는 이것들의 응용과 함께 기본적인 자료구조에 관련된 알고리즘들을 알아보게 될것이다.

키워드

링크드 리스트,   링크,   노드