Linked List

• Linked List는 data를 저장하는 node를 가지고 있다.
• Linked List는 data와 다음 node에 대한 포인터를 가지고 있다.
• Double Linked List는 data와 다음 node, 이전 node에 대한 포인터를 가지고 있다.

1) Node 구현

다양한 data 유형을 저장하기 위해서 template로 정의된 Node class를 생성한다.

template <class Item>
class node {
public:
	node(const Item& init_data = Item(),
			node* init_pre_link = NULL, node* init_after_link = NULL);

	void set_data(const Item& new_data) { data_field = new_data; }
	void set_pre_link(node* new_pre_link) { pre_link_field = new_pre_link; }
	void set_after_link(node* new_after_link) { after_link_field = new_after_link; }
	
	Item data() const { return data_field; }
	node* pre_link() { return pre_link_field; }
	node* after_link() { return after_link_field; }
	const node* pre_link() const { return pre_link_field; }
	const node* after_link() const { return after_link_field; }

private:
	Item data_field;
	node* pre_link_field;
	node* after_link_field;
};

Double Linked List의 Node

1. Item data: 해당 노드에 저장된 데이터
2. node* pre_link: 현재 노드의 이전 노드를 가리킵니다.
3. node* after_link: 현재 노드의 다음 노드를 가리킵니다.

Node 생성자

Node의 데이터, 이전 노드 포인터, 다음 노드 포인터를 초기화하여 생성한다.
(매개변수들은 각각 초기화를 할 수 있으며, 초기화하지 않는 경우에는 NULL 포인터로 초기화)

template <class Item>
node<Item>::node(const Item& init_data, node* init_pre_link, node* init_after_link)
{
	data_field = init_data;
	pre_link_field = init_pre_link;
	after_link_field = init_after_link;
}

head_ptr와 tail_ptr

template <class Item>
node<Item>* head_ptr;

template <class Item>
node<Item>* tail_ptr;

• head_ptr을 사용하여 Double Linked List의 첫번째 Node에 접근
• tail_ptr을 사용하여 Double Linked List의 마지막 Node에 접근

Node 멤버 함수 정의

1. 데이터를 노드의 데이터에 할당
2. 해당 포인터를 노드의 포인터에 할당
3. 노드의 데이터를 반환 (데이터 멤버를 수정 불가)
4. 노드의 이전과 다음 노드를 가리키는 포인터 반환
5. const node*
   • 반환하는 값을 상수로 취급
   • node 객체의 상태 변경 불가