Linked List

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

2) Operations on a linked list

1. Linked List 길이

template <class Item>
size_t length(const node<Item>* head_ptr) {
	size_t count = 0;
	const node<Item>* cursor;
	for (cursor = head_ptr; cursor != NULL; cursor = cursor->after_link()) {
		count++;
	}
	return count;
}

• head_ptr과 동일한 포인터 cursor 선언
• 처음 노드부터 순차적으로 탐색
• 다음 노드로 이동 cursor = cursor->after_link()

2. Linked List 삽입

2-1. Linked List 맨 처음 삽입

template <class Item>
void head_insert(node<Item>*& head_ptr, const Item& entry) {
	head_ptr = new node<Item>(entry, NULL, head_ptr);
}

• Linked List의 head 포인터를 이중 포인터로 가져온다. (head_ptr이 바뀌기 때문)
• 다음 노드가 headptr이고 삽입할 데이터를 가지는 새로운 노드를 생성: _new node
• head_ptr 변경

2-2. Linked List 중간 삽입

template <class Item>
void list_insert(node<Item>* pre_ptr, const Item& entry) {
	node<Item>* insert_node = new node<Item>(entry, pre_ptr, pre_ptr->after_link());
	
    pre_ptr->set_after_link(insert_node);
	
	if (insert_node->after_link() != NULL) {
		insert_node->after_link()->set_pre_link(insert_node);
	}
}

• 삽입할 노드의 이전 위치를 가져온다.
• 삽입할 노드의 이전과 다음 노드를 설정하고, 데이터 값을 가지는 새로운 노드 생성
• 이전 노드의 다음 노드를 삽입할 노드로 변경
• 삽입한 노드의 다음 노드가 존재한다면, 다음 노드의 이전 노드 변경

3. Linked List 삭제

3-1. Linked List 맨 처음 삭제

template <class Item>
void head_remove(node<Item>*& head_ptr) {
	node<Item>* remove_ptr = head_ptr;

	head_ptr = head_ptr->after_link();
	head_ptr->set_pre_link(NULL);

	delete remove_ptr;
}

• Linked list의 head 포인터 변경
• Node 삭제

3-2. Linked List 중간 삭제

template <class Item>
void list_remove(node<Item>* pre_ptr) {
	node<Item>* remove_ptr = pre_ptr->after_link();

	pre_ptr->set_after_link(remove_ptr->after_link());
	if (remove_ptr->after_link() != NULL) {
		remove_ptr->after_link()->set_pre_link(pre_ptr);
	}

	delete remove_ptr;
}

• 삭제할 노드의 이전 노드의 다음 노드 변경
• 삭제할 노드의 다음 노드가 존재한다면, 다음 노드의 이전 노드 변경
• Node 삭제

4. Linked List 검색

template <class Item>
node<Item>* search(node<Item>* head_ptr, const Item& target) {
	node<Item>* cursor;
	for (cursor = head_ptr; cursor != NULL; cursor = cursor->after_link()) {
		if (cursor->data() == target) {
			return cursor;
		}
	}
	return NULL;
}

• Linked List의 처음부터 검색
• 동일한 데이터를 가지고 있는 노드를 찾으면 노드의 포인터 반환
• 데이터가 존재하지 않으면 NULL 반환

5. Linked List 위치

template <class Item>
node<Item>* location(node<Item>* head_ptr, size_t position) {
	node<Item>* cursor = head_ptr;

	for (int i = 0; i < position; i++) {
		cursor = cursor->after_link();
		if (cursor == NULL) {
			return NULL;
		}
	}
	return cursor;
}

• Linked List 위치의 노드 포인터 반환
• NULL 에러 발생