C++ Ch. 16 Notes, page 1

Computer Science Using C++

Ch. 16 Notes, page 1

Objective #1: Understand the difference between static and dynamic data structures.

Static structures like built-in C++ arrays and variables use a certain amount of memory (RAM) for their lifetime in a program. Dynamic data structures such as linked lists are flexible regarding size. They only consume as much memory as necessary to store data that has been specifically assigned to them.
Dynamic data structures are stored in the heap. The heap is the part of the computer's RAM that has not been assigned to open applications or the operating system itself. First you must reserve memory in the heap in order to use it for a dynamic data structure. The process of reserving memory from the heap is called allocating.
When you are finished using a portion of the heap associated with a dynamic data structure you must deallocate or free that memory so that it goes back to the heap. Otherwise, the operating system will think that your program still needs that memory. Memory leakage occurs if you do not deallocate this chunk of memory. Memory leakage could cause a computer to crash.
The new operator is used to allocate memory on the heap and the delete operator deallocates (frees) memory. For example, ptrStudent = new Person; could be used to allocate enough memory for a Person struct. The pointer, ptrStudent, is set to point to that chunk of memory. The statement delete ptrStudent; would be used later in the program to deallocate that portion of memory.

Objective #2: Add nodes to the end of a linked list.

To add a node to the end of a linked list, you must first create the new node. Furthermore, when you create the new node you must use a temporary pointer to keep track of it. Remember we are not naming specific variables so using a pointer to mark its address is important.
Next, you must attach the new node to the end of the linked list by having a pointer (such as the next pointer from the textbook's example) from the last node in the list point to the new node.
The new node's "next" pointer should point to NULL.

Objective #3: Move through the nodes of a linked list.

When you visit EVERY node in a linked list you are traversing the list. Sometimes you may only need to find a certain node and don't care to visit EVERY node however.
To move through a linked list, you would follow the "next" pointer of each node to the node it points to. This process would occur in a do loop until you either found what you are looking for or until you have reached the end of the list. Note that if you have reached the end of the list, you have traversed the list.

Objective #4: Dispose of a linked list.

To dispose a linked list you must traverse the list (that is, visit every node of the list) and use the delete operator to free the memory being used to store each node.
In order to dispose of the list, you must use a temporary pointer variable to keep track of where the next node is located as you delete the previous node. Since we are not naming each struct variable or node item with an identifier, the only way that we can reference a node is with a pointer. If a node is deleted with that reference pointer, we will have lost it's "next" pointer and no longer know where the next node is located. That is why a temporary pointer variable needs to be used.

Objective #5: Insert nodes from a linked list.

There are three general places that a node can be inserted into a linked list. You can insert a new node at the head (beginning) of the list. You can insert a node in the middle of the list. Or, you can insert a new node at the end of the list.
To insert a node at the head of the list, you must point it's "next" pointer to the original node that was located at the head of the list. You must then reassign the linked list's head pointer to point to this new node.
To insert a node in the middle of the list, you must find the location where you wish to insert the new node. Then, you set the "next" pointer of the node that needs to come directly before the new node to point to the new node. You must also set the new node's "next" pointer to point to the node which will directly follow the new node in the linked list.
To insert a node at the end of the list, you simply point the "next" pointer of the previous last node to this new node. The "next" pointer of the new node must point to NULL.

Objective #6: Delete nodes from a linked list.

To delete a node from a linked list, you must first find the node that you wish to delete.
Then, you must set the "next" pointer of the node that comes before the node you wish to delete to point to the node that follows the soon-to-be-deleted node.
To actually delete the node, you use the delete operator to free the memory being used by the node.

Objective #7: Save a linked list to disk.

Since a linked list is a dynamic data structure that is stored in the memory (RAM) of the computer, you will need to save the data (nodes and arrangement) to a file if you wish to use it after your program's execution.
You do not need to save any pointers to the file though. You only need to save the actual information in each node. The "next" pointers will be recreated when you run the program again if wish to store the data into another linked list at that time.

Objective #8: Understand doubly-linked lists.

In a doubly-linked list you assign two pointers to each node. In addition to a "next" pointer, you will use a "previous" pointer to point to the node which comes before the current node in the list.
Double-linking a list allows you to traverse the list in both directions. Otherwise, you can only traverse the list from its head to its end.

Objective #9: Understand circularly-linked lists.

Circularly-linked lists are similar to singly-linked lists with "next" pointers. However, the last node's "next" pointer points back to the head (first) not NULL.
You may or may not have a head pointer associated with a circularly-linked list.