連結リストを実装する時get_Nth_node_from関数を使おう

When implementing a linked list, 最後のノードをゲットしないとダメな時がよくある。例えばpushBackとかpopBackなど。There’s also a time where we need to get Nth number of node to insert or delete.

僕はいつも普通にloopを使って実装してきた。例えばpopBackの場合はこうなる。

void popBack() {
	if (head == nullptr) return;
	
	if (size == 1) {
		delete head;
		head = nullptr;
		size = 0;
	} else {
		Node *temp = head;
		while (temp->next && temp->next->next) {
			temp = temp->next;
		}
		delete temp->next;
		temp->next = nullptr;
		--size;
	}
}

だが、今回 Nth node from Start/End という関数を練習として追加してもらったけど、その後色んな関数のlogicがすごく簡単になったの気づいた。

void popBack() {
	if (head == nullptr) return;
	
	if (size == 1) {
		delete head;
		head = nullptr;
		size = 0;
	} else {
		Node *temp = getNthFromTail(2);
		delete temp->next;
		temp->next = nullptr;
		--size;
	}
}

コードの量としてはあんまりdifferenceがないかもしらんけど、理解やすくなった。これ以外にも、色々簡単に書くのができる。

void pushBack(int val) {
	Node *newNode = new Node(val);

	if (!head) {
		head = newNode;
	} else {
		Node *temp = getNthFromTail(1);
		temp->next = newNode;
	}
}

void insert(int pos, int val) {
	/* ... */

	Node *newNode = new Node(val);
	Node *temp = getNthFromHead(pos);

	newNode->next = temp->next;
	temp->next = newNode;
}

void deleteAt(int pos) {
	/* ... */

	Node *temp = getNthFromHead(pos);
	Node *deleteNode = temp->next;
	temp->next = temp->next->next;
	
	delete deleteNode;
}

Nothing bigでも僕は今度からもこの関数を使用すると思う。

Node* getNthFromHead(int n) const {
	if (!head) return nullptr;
	if (n < 0 || n > size) return nullptr;

	Node *temp = head;
	for (int i=1; i<n; ++i) {
	   temp = temp->next;
	}

	return temp;
}

Node* getNthFromTail(int n) const {
	if (!head) return nullptr;
	if (n < 0 || n > size) return nullptr;

	Node *mainPtr = head;
	Node *refPtr = head;

	for (int i=0; i<n; ++i) {
		refPtr = refPtr->next;
	}

	while(refPtr) {
		mainPtr = mainPtr->next;
		refPtr = refPtr->next;
	}

	return mainPtr;
}