링크드 리스트의 이해

소개글

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

본문내용

용한다.
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;
}
}
Ⅲ. 결론
이상 링크드리스트와 링크드리스트 데이타 추상에 대해서 알아보았다. 이로써 기본자료구조인 스택,큐,링크드리스트에 대한 기본적인 내용을 모두 다루었다. 다음번부터는 이것들의 응용과 함께 기본적인 자료구조에 관련된 알고리즘들을 알아보게 될 것이다.

키워드

링크드 리스트의 이해,   링크드 리스트의 이해.