Post-class 02/04

17 files changed, 316 insertions, 0 deletions

diff --git a/02-02.md b/02-02.md
index 73a51d6..8db9558 100644
--- a/02-02.md
+++ b/02-02.md
@@ -546,3 +546,7 @@ const node *link() const {return link_field;};
 	- An ordinary version that return an ordinary pointer to a node
 - When both a const and non-const version of a function are present:
 	- The **compiler automatically chooses the correct version** depending on whether the function was activated by a constant node (such as `const node *c`) or by an ordinary node
+
+---
+
+[02/04 ->](02-04.md)
diff --git a/02-04.md b/02-04.md
new file mode 100644
index 0000000..6f8cf25
--- /dev/null
+++ b/02-04.md
@@ -0,0 +1,312 @@
+[\<- 02/02](02-02.md)
+
+---
+
+## Linked List (cont.)
+
+### Dynamic Array to Linked List
+
+```
+class bag{
+	public:
+		//...
+	private:
+		value_type *data;
+		size_type used;
+		size_type capacity;
+};
+
+//linked list bag
+class workout_songs{ //aka bag
+	public:
+		//...
+	private:
+		node *head_ptr;
+		size_type many_nodes;
+};
+```
+
+- Value semantics of `workout_songs`
+	- assignment and copy constructors will be overwritten
+
+- Invariance of `workout_songs`
+	- `head_ptr` always points to the beginning of the list (or null if the list is empty)
+	- `many_nodes` always represents the number of nodes in the list
+
+### Constructor
+
+```
+bag::bag(){
+	head_ptr = NULL;
+	many_nodes = 0;
+}
+
+//copy constructor
+bag::bag(const bag& source){
+	Node *tail_ptr;
+	list_copy(source.head_ptr, head_ptr, tail_ptr);
+	many_nodes = source.many_nodes;
+}
+```
+
+### Do We need a Destructor?
+
+- Yes!
+
+```
+bag::~bag(){
+	list_clear(head_ptr);
+	many_nodes = 0;
+}
+```
+
+### Member Functions
+
+```
+//MODIFICATION MEMBER FUNCTIONS
+size_type erase(const value_type& target);
+bool erase_one(const value_type& target);
+void insert(const value_type& entry);
+void operator +=(const bag& addend);
+void operator =(const bag& source);
+
+//CONSTANT MEMBER FUNCTIONS
+size_type size() const {return many_nodes;};
+size_type count(const value_type& target) const;
+value_type grab() const;
+```
+
+### Assignment Operator
+
+- **Note**: When the assignment operator begins, the bag already has a linked list, and this linked list must be returned to the heap
+
+```
+void bag::operator =(const bag& source){
+	node *tail_ptr; //needed for argument to list_copy
+
+	if(this == &source) return; //check for self assignment
+	
+	list_clear(head_ptr); //to return the existing linked list to the heap
+	many_nodes = 0; //we want the bag to be valid before calling list_copy
+	list_copy(source.head_ptr, head_ptr, tail_ptr);
+	many_nodes = source.many_nodes;
+}
+```
+
+### Container Class with Linked List
+
+- When a data structure uses a linked list, the assignment operator is important
+- Two important aspects:
+	- We need to check for "**self-assignment**" such as `b = b`
+		- The easiest way to handle self-assignment is to check for it at the start of the assignment operator and simply return with no work if self-assignment is discovered
+	- In addition, before calling a function that allocates dynamic memory, **make sure that the invariant of your class is valid**
+
+### erase_one Implementation
+
+- Find the target
+- Copy data from `head_ptr` to target
+- Remove the head node
+
+![diagram](02-04_1.png)
+
+### += Operator
+
+- The implementation starts by making a copy of the linked list of the addend
+- The copy is then attached at the front of the linked list for the bag that's being addend to
+
+```
+void bag::operator +=(const bag& addend){
+	node *copy_head_ptr;
+	node *copy_tail_ptr;
+
+	if(addend.many_nodes > 0){
+		list_copy(addend.head_ptr, copy_head_ptr, copy_tail_ptr);
+		copy_tail_ptr->set_link(head_ptr);
+		head_ptr = copy_head_ptr;
+		many_nodes += addend.many_nodes;
+	}
+}
+```
+
+### Linked List Toolkit
+
+- These are the utility functions 
+	- If you don't have them, you will to implement them over and over
+
+```
+//FUNCTIONS for the linked list toolkit
+std::size_t list_length(const node *head_ptr);
+void list_head_insert(node *& head_ptr, const node::value_type& entry);
+void list_insert(node *previous_ptr, const node::value_type& entry);
+node *list_search(node *head_ptr, const node::value_type& target);
+const node* list_search(const node* head_ptr, const node::value_type& target);
+node *list_locate(node *head_ptr, std::size_t position);
+const node *list_locate(const node *head_ptr, std::size_t position);
+void list_head_remove(node *& head_ptr);
+void list_remove(node *previous_ptr);
+void list_clear(node *& head_ptr);
+void list_copy(const node *source_ptr, node *& head_ptr, node *& tail_ptr);
+```
+
+### Parameters for Linked Lists
+
+1. Parameters that are pointers with the const keyword
+	- Example: The `list_length` function has such a parameter
+		`size_t list_length(const node* head_ptr);`
+	- The function uses the head pointer to access the list's nodes, but the function does not change any part of the list
+	- A pointer to a constant node should be used when the function needs access to the linked list and the function will not make any changes to any of the list's nodes
+
+2. Value Parameters that are pointers to a node
+	- The second sort of node pointer parameter is a value parameter without the `const` keyword
+	- Example: One of the toolkit's functions will add a new node after a specified node in the list
+	- A node pointer should be a value parameter when the function needs access to the linked list, and the function might change the linked list, but the function does not need to make a pointer point to a new node
+
+```
+void list_insert(node *p, const node::value_type& entry);
+//Precondition: p points to a node in a linked list
+//Postcondition: A new node containing the given entry has been added after the node that p points to
+```
+
+3. Reference parameters that are pointers to a node
+	- Sometimes a function must make a pointer point to a new node
+	- Example: Add a new node at the front of a linked list
+	- The `head_ptr` is a reference parameter, since the function creates a new head node and makes the head pointer point to this new node
+	- When the function needs access to the linked list and the function makes the pointer point to a new node, this change to the pointer will make the actual argument point to a new node
+
+```
+void list_head_insert(node *& head_ptr, const node::value_type& entry);
+//Precondition: head_ptr is the head pointer of a linked list
+//Postcondition: A new node containing the given entry has been added at the head of the list
+//Postcondition: head_ptr now points to the head of the new, longer linked list
+```
+
+### Inserting a Node at the Front
+
+```
+void list_head_insert(node *& head_ptr, const node::value_type& entry);
+```
+
+- We want to add a new entry, 13, to the **front** of the linked list shown here:
+
+![diagram](02-04_2.png)
+
+- Create a new node, pointed to by a local variable `insert_ptr`
+
+![diagram](02-04_3.png)
+
+- `insert_ptr = new_node`
+	- Place the data in the new node's `data_field`
+
+![diagram](02-04_4.png)
+
+- Connect the new node to the front of the list
+
+![diagram](02-04_5.png)
+
+- `insert_ptr = new node(entry, head_ptr);`
+	- The correct new node can be completely created in one step by calling an appropriate node constructor
+
+![diagram](02-04_6.png)
+
+- Make the old head pointer to the new node
+
+![diagram](02-04_7.png)
+
+- `head_ptr = insert_ptr`
+- When the function returns, the linked list has a new node at the front
+
+```
+void list_head_insert(node *& head_ptr, const node::value_type& entry){
+	node *insert_ptr;
+
+	insert_ptr = new node(entry, head_ptr);
+	head_ptr = insert_ptr;
+}
+```
+
+- Does the function work correctly for the empty list?
+	- Yes
+
+### Caution!
+
+- Always make sure that your linked list functions work correctly with an empty list
+
+### Pseudocode for Inserting Nodes
+
+- Nodes are often inserted at places other than the front of a linked list
+- There is a general pseudocode that you can follow for any insertion function...
+- Determine whether the new node will be the first node in the linked list. If so, then there is only one step:
+	- `list_head_insert(head_ptr, entry);`
+- Otherwise, (if the new node will not be first):
+	- Start by setting a pointer named `previous_ptr` to point to the node which is just **before** the new node's position
+
+![diagram](02-04_8.png)
+
+- Look at the pointer which is **in the node** `*previous_ptr`
+	- What is the name of this orange pointer?
+
+![diagram](02-04_9.png)
+
+- The pointer is called `previous_ptr->link_field` (although this name may be private to the node)
+- `previous_ptr->link_field` points to the head of a small linked list, with 10 and 7
+
+![diagram](02-04_10.png)
+
+- The new node must be inserted at the front of this small linked list
+	- Write one C++ statement which will do the insertion
+
+![diagram](02-04_11.png)
+
+- `list_head_insert(previous_ptr->link_field, entry);`
+- What might cause this statement to fail to compile?
+
+- `list_head_insert(previous_ptr->link(), entry);`
+	- Use a node member function to get the link field if needed
+
+- Determine whether the new node will be the first node in the linked list. If so, then there is only one step:
+	- `list_head_insert(head_ptr, entry);`
+- Otherwise (if the new node will not be first):
+	- Set a pointer named `previous_ptr` to point to the node which is just before the new node's position
+	- Make the function call:
+		- `list_head_insert(previous_ptr->link(), entry);`
+- The process of adding a new node in the middle of a list can also be incorporated as a separate function. The function is called `list_insert` in the linked list toolkit
+
+### Pseudocode for Removing Nodes
+
+- Nodes often need to be removed from a linked list
+- As with insertion, there is a technique for removing a node from the front of a list, and a technique for removing a node from elsewhere
+- We'll look at the pseudocode for removing a node from the front of a linked list
+
+### Removing the Head Node
+
+- Start by setting a temporary pointer named `remove_ptr` to the head node
+
+![diagram](02-04_12.png)
+
+- Set up `remove_ptr`
+- `head_ptr = remove_ptr->link();`
+
+![diagram](02-04_13.png)
+
+- `delete remove_ptr; //Return the node's memory to heap`
+
+![diagram](02-04_14.png)
+
+- Here's what the linked list looks like after the removal finishes:
+
+![diagram](02-04_15.png)
+
+### How to Use Linked-List
+
+- **Node Class + Toolkit**
+	- Allow a container class to store elements on a basic linked list with the simplicity and clarity of using an array
+- Any programmer can use our node and the toolkit
+	- programmers define the `value_type` according to their need
+	- Places the `#include "node.h"` in the program
+
+## Summary
+
+- It is easy to insert a node at the front of a list
+- The linked list toolkit also provides for inserting a new node elsewhere
+- It is easy to remove a node at the front of a list
+- The linked list toolkit also provides a function for removing a node elsewhere - you should read about this function and the other functions of the toolkit
diff --git a/02-04_1.png b/02-04_1.png
new file mode 100644
index 0000000..6db793b
--- /dev/null
+++ b/02-04_1.png
diff --git a/02-04_10.png b/02-04_10.png
new file mode 100644
index 0000000..d52a373
--- /dev/null
+++ b/02-04_10.png
diff --git a/02-04_11.png b/02-04_11.png
new file mode 100644
index 0000000..f9aac0b
--- /dev/null
+++ b/02-04_11.png
diff --git a/02-04_12.png b/02-04_12.png
new file mode 100644
index 0000000..1db4b07
--- /dev/null
+++ b/02-04_12.png
diff --git a/02-04_13.png b/02-04_13.png
new file mode 100644
index 0000000..ac65407
--- /dev/null
+++ b/02-04_13.png
diff --git a/02-04_14.png b/02-04_14.png
new file mode 100644
index 0000000..9c5a91f
--- /dev/null
+++ b/02-04_14.png
diff --git a/02-04_15.png b/02-04_15.png
new file mode 100644
index 0000000..a249e2c
--- /dev/null
+++ b/02-04_15.png
diff --git a/02-04_2.png b/02-04_2.png
new file mode 100644
index 0000000..e9cac2b
--- /dev/null
+++ b/02-04_2.png
diff --git a/02-04_3.png b/02-04_3.png
new file mode 100644
index 0000000..71cac82
--- /dev/null
+++ b/02-04_3.png
diff --git a/02-04_4.png b/02-04_4.png
new file mode 100644
index 0000000..e0fead8
--- /dev/null
+++ b/02-04_4.png
diff --git a/02-04_5.png b/02-04_5.png
new file mode 100644
index 0000000..65f71cc
--- /dev/null
+++ b/02-04_5.png
diff --git a/02-04_6.png b/02-04_6.png
new file mode 100644
index 0000000..e58a784
--- /dev/null
+++ b/02-04_6.png
diff --git a/02-04_7.png b/02-04_7.png
new file mode 100644
index 0000000..1fcc849
--- /dev/null
+++ b/02-04_7.png
diff --git a/02-04_8.png b/02-04_8.png
new file mode 100644
index 0000000..55eaecf
--- /dev/null
+++ b/02-04_8.png
diff --git a/02-04_9.png b/02-04_9.png
new file mode 100644
index 0000000..efb4062
--- /dev/null
+++ b/02-04_9.png