Updating before template node branch

1 files changed, 256 insertions, 0 deletions

diff --git a/CST 126/Homework 3/SinglyLinkedList.hpp b/CST 126/Homework 3/SinglyLinkedList.hpp
new file mode 100644
index 0000000..e28c142
--- /dev/null
+++ b/CST 126/Homework 3/SinglyLinkedList.hpp
@@ -0,0 +1,256 @@
+#ifndef SINGLY_LINKED_LIST_HPP
+#define SINGLY_LINKED_LIST_HPP
+
+struct ListNode
+{
+	int _data{ 0 };
+	ListNode* _next{ nullptr };
+};
+
+struct SinglyLinkedList
+{
+	size_t _size{ 0 };
+	ListNode* _head{ nullptr };
+};
+
+bool Append(SinglyLinkedList* list, ListNode* node);
+bool Prepend(SinglyLinkedList* list, ListNode* node);
+bool RemoveFirst(SinglyLinkedList* list);
+bool RemoveLast(SinglyLinkedList* list);
+bool InsertAfter(SinglyLinkedList* list, const int data, ListNode* node);
+bool InsertBefore(SinglyLinkedList* list, const int data, ListNode* node);
+bool Clear(SinglyLinkedList* list);
+ListNode* Extract(SinglyLinkedList* list, const int data);
+bool Empty(SinglyLinkedList* list);
+bool Remove(SinglyLinkedList* list, ListNode* node);
+
+//code
+bool Append(SinglyLinkedList* list, ListNode* node )
+{
+	//we have a list
+	//we need to add a node to the end of the list
+
+	//empty
+	if (Empty(list)) 
+	{
+		list->_head = node;
+		list->_size++;
+		return true;
+	}
+	//Append head
+	if(list->_size == 1)
+	{
+		list->_head->_next = node;
+		list->_size++;
+		return true;
+	}
+	//Down the list
+	ListNode* travel = nullptr;
+	for(travel = list->_head; travel->_next != nullptr;)
+	{
+		travel = travel->_next;
+	}
+	travel->_next = node;
+	list->_size++;
+	return true;
+}
+
+bool Prepend(SinglyLinkedList* list, ListNode* node) 
+{
+	if (Empty(list))
+	{
+		list->_head = node;
+		list->_size++;
+		return true;
+	}
+
+	node->_next = list->_head;
+	list->_head = node;
+
+	list->_size++;
+	return true;
+}
+
+bool RemoveFirst(SinglyLinkedList* list)
+{
+	//check if zero size
+	if (Empty(list)) return true;
+
+	if(list->_size == 1)
+	{
+
+		list->_head = nullptr;
+	}
+	else
+	{
+		ListNode* prev = list->_head;
+		list->_head = list->_head->_next;
+		prev->_next = nullptr;
+	}
+
+	list->_size--;
+
+	return true;
+}
+
+bool RemoveLast(SinglyLinkedList* list)
+{
+	if (Empty(list)) return true;
+
+	if (list->_size == 1)
+	{
+		list->_head = nullptr;
+		return true;
+	}
+	
+	ListNode* travel = list->_head;
+	while(travel->_next->_next != nullptr)
+	{
+		travel = travel->_next;
+	}
+	travel->_next = nullptr;
+	list->_size--;
+	return true;
+	
+}
+
+bool InsertAfter(SinglyLinkedList* list, const int data, ListNode* node)
+{
+	//first to find data
+	//thoughts? What if we are inserting at after end.
+	ListNode* travel;
+	for (travel = list->_head; travel->_data != data && travel->_next != nullptr; )
+	{
+		travel = travel->_next;
+	}
+
+	if (travel->_next == nullptr) 
+	{
+		return Append(list, node);
+	}
+
+	node->_next = travel->_next;
+	travel->_next = node;
+	list->_size++;
+
+	//then insert after data
+	return true;
+}
+
+bool InsertBefore(SinglyLinkedList* list, const int data, ListNode* node)
+{
+	if (list->_head->_data == data)
+		return Prepend(list, node);
+
+	ListNode* travel;
+	for (travel = list->_head; travel->_next->_data != data;)
+	{
+		travel = travel->_next;
+	}
+
+	node->_next = travel->_next;
+	travel->_next = node;
+	list->_size++;
+
+	return true;
+	
+}
+
+bool Clear(SinglyLinkedList* list)
+{
+	//consider the head
+	//consider the size
+	//We have to detach every node from each other
+	//start at the head
+	//use a node* to track our position
+
+	if (list->_size == 0) return true;
+
+	ListNode* travel = list->_head;
+	ListNode* prev = travel;
+
+	do
+	{
+		prev = travel;
+		travel = travel->_next;
+		prev->_data = 0;
+		prev->_next = nullptr;
+		
+	} while (travel != nullptr && travel->_next != nullptr);
+
+	list->_size = 0;
+	list->_head = nullptr;
+
+	return true;
+}
+
+ListNode* Extract(SinglyLinkedList* list, const int data)
+{
+	//check if empty, shortcut return
+	ListNode* temp = new ListNode{0, nullptr};
+	ListNode* travel = nullptr;
+
+	if (Empty(list))
+	{
+		return temp;
+	}
+	//Read through list
+	for (travel = list->_head; travel->_data != data && travel->_next != nullptr; )
+	{
+		travel = travel->_next;
+	}
+	//find the data
+		//pointer to the node
+	temp->_data = travel->_data;
+		//remove node from list
+	if(Remove(list, travel))
+	{
+		return temp;
+	}
+	//or don't find data
+
+	return nullptr;
+}
+
+bool Remove(SinglyLinkedList* list, ListNode* node)
+{
+	//find the node
+	//Read through list
+	ListNode* travel = list->_head;
+	ListNode* prev = travel;
+
+	while(travel != node)
+	{
+		prev = travel;
+
+		travel = travel->_next;
+	}
+	//if first, remove first
+	if(travel == list->_head)
+	{
+		return RemoveFirst(list);
+	}
+	//if last, remove last
+	if(travel->_next == nullptr)
+	{
+		return RemoveLast(list);
+	}
+	//else in middle
+	//remove travel's node
+	//will need previous node
+		//to set previous's next to travel's next
+	prev->_next = travel->_next; //fixing pointer between nodes
+									//removes dangling pointer from prev to travel
+
+	//delete travel
+	travel->_next = nullptr;
+	travel->_data = 0;
+	list->_size--;
+}
+
+bool Empty(SinglyLinkedList* list)
+{
+	return (list->_size == 0 && list->_head == nullptr);
+}
+
+#endif // !SINGLY_LINKED_LIST_HPP
\ No newline at end of file