summaryrefslogtreecommitdiff
path: root/02-04.md
diff options
context:
space:
mode:
Diffstat (limited to '02-04.md')
-rw-r--r--02-04.md312
1 files changed, 312 insertions, 0 deletions
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