Lab 18 - Memory, Pointers, and Linked Lists

1 int* pNum1, *pNum2; //pNum1 and pNum2 are integer pointers 2 double* pNum3; //pNum3 is a pointer to a double 3 char* pWord; //pWord is a pointer to a char 4 struct BankRec 5 { 6 double balance; 7 double credit; 8 }; 9 BankRec* pBank; //pBank is a pointer to a BankRec struct 10 struct Node 11 { 12 BankRec data; 13 Node* next; // members of a struct can be a pointer to the current struct 14 };

Address Memory Contents Variable Allocations 2000 4040 p1 2004 3020 p2 ... ... ... 3020 1004 ... ... 4040 8040

Address Memory Contents Variable Allocations 2000 2020 p1 2004 2024 p2 ... ... ... 2020 100 2024 55

Address Memory Contents Variable Allocations 2000 ? p1 2004 ? p2 ... ... ... 2016 ? ... ... ... 3020 ?

Address Memory Contents Variable Allocations 2000 3020 p1 2004 2016 p2 ... ... ... 2016 2 ... ... ... 3020 2 A. p1 = new int; p2 = new int; *p1 = 2; *p2 = *p1; B. *p1 = new int; *p2 = new int; *p1 = 2; *p2 = 2; C. p2 = new int; p1 = new int; *p1 = 2; *p2 = 2; D. *p1 = new int; *p2 = new int; *p1 = 2; *p2 = p1;

creates the variable head, that can be used to point to the first node in the list. Like other uninitialized variables, it is undefined. To what value should you initialize head to indicated that the list is empty? It should be set to nullptr (or equivalently NULL) to indicate that it does not point to any node.

Adding a node to the list

To insert a node into the list, first memory has to be dynamically allocated, data has to be inserted (i.e., payload must be loaded) into the node, and a pointer must be changed to add the node. For example, the following code will add a new node to the beginning of the list.

head = new Node; //dynamically allocate a new node head->data.acctNum = 1112; //place a value in the acctNum head->data.balance = 450; //place a value in the balance head->next = NULL; //place NULL in the next field

Graphically, the list would now look like:

To add a second node at the beginning of the list, the following code might be used:


		Node* p;                  //create a node pointer
		p = new Node;             //dynamically allocate space for a new node
		p->data.acctNum = 1113;   //place a value into the acctNum field
		p->data.balance = 380.00; //place a value into the balance field
		p->next = head;           //make p point to the node that head points to
		head = p;                 //update head to point to the new node

Graphically, the list would now appear as:

Make sure you understand each statement in the code above before continuing with this section.

Examining each node in the list

Now that we know how to add nodes to a list, we need to learn how to move from the head pointer to each node in the list and examine each node. For example, we might wish to search for a particular node, or count the nodes in the list, or print all the nodes in the list. Consider the following code that prints all the nodes in the list.

Node* cur = head; //start a pointer at the beginning of the list while (cur != NULL) //as long as we haven't reached the list's end { //print the account number and balance cout << "Account # = " << cur->data.acctNum << endl; cout << "Balance = " << cur->data.balance << endl; //move to the next node cur = cur->next; }

Exercise 28: Copy the files structs.h, inlab18.h, inlab18.cpp, and main18a.cpp to your account. Modify inlab18.cpp to implement the print method to print out the items in the list. Each node is printed on a line with the account number, then a tab, and finally the balance. To output a tab character, use cout << "\t"; Do not output any labels. Just print the contents (payload) of the node. For instance

1114    395.67

Using the script command, create the lab18ex28.log file containing a print out (pr -n -t -e4 ...) of inlab18.cpp, a compile, and four runs with the $CLA data files Ex28_data.0, Ex28_data.1, Ex28_data.2, and Ex28_data.3. When you run your program, use redirection to read from the various files (e.g., a.out < $CLA/Ex28_data.0).

Deleting a node from the list

Often, it is necessary to delete an item from the list. For example, consider the list below:

Suppose we wish to delete the node pointed to by p and we know that q is pointing to the node previous to p. The following code will accomplish the necessary delete.


  		q->next = p->next;     //take p out of the linked list
		delete p;              //deallocate p's memory

F. The C++ Class Destructor

In C++, normally a class type is used to encapsulate the data and functions that are associated with a linked list. Member functions that are normally provided include constructors, a function that allows one to print all of the nodes in a list, one or more functions to insert nodes into the list and functions that allow nodes to be removed from the list. Previously we learned that the C++ class has special member functions (methods) called constructors. Constructors are methods that can be used to initialize data members as discussed previously. We say that constructors are used for the creation of objects. In the preceding exercise you should have realized the need for the deallocation of memory when records are no longer needed in a linked list. Noting this need for deallocation will help you to recognize the need for another special method called a destructor. A destructor is a special member function (method) that "frees" up or deallocates memory and we say that it is used for the destruction of objects. It can do other tasks as well, such as close a file.

Let's say that we have a class called ListClass that contains data members and methods to allow us to create and maintain an ordered linked list of banking customers. Then a destructor for the ListClass object would be used to deallocate all records found in the list. The following comments regarding destructors are appropriate at this time:

A class may have many constructors but only one destructor.
Destructors are called (activated) when the function that created the desired object is terminated.
Destructors do not have arguments.
The prototype for a destructor is written as (note the tilde prefix):
~NameOfClass();
For example, if we have a class called ListClass, then the prototype for the class destructor would be:
~ListClass();

The implementation for the destructor should deallocate dynamically allocated data members. Therefore, the destructor definition for the ListClass object may appear as:

ListClass::~ListClass() { //head is a private data member of ListClass that //points to the first node in the list // Traverse nodes in list, deleting nodes as you go Node* current = head; //pointer to node to be deleted Node* future; //pointer to node "following" current while (current != nullptr) { future = current->next; //remember where to go next delete current; //deallocate memory current = future; //move current to next node } head = nullptr; //indicate head no longer points to a node }

Exercise 29: Use the files inlab18.h and inlab18.cpp from Exercise 28. Copy the files main18b.cpp and insertInOrder.cpp to your account. Modify the file insertInOrder.cpp so that it finishes the implementation of the method insertInOrder. This method appends the record 'newData' into the correct sorted position in the linked list. If the list is empty, make the new node the head node of the list (i.e., have the head pointer point to it).
To compile the program, type:

c++ inlab18.cpp insertInOrder.cpp main18b.cpp

Create a script log, lab18ex29.log containing a print out (pr -n -t -e4 ...) of insertInOrder.cpp, a compile, and six runs with the $CLA data files Ex29_data.0, Ex29_data.1, Ex29_data.2, Ex29_data.3, Ex29_data.4, and Ex29_data.5. Use file redirection to read from each file.

Exercise 30: Use the files inlab18.h and inlab18.cpp from Exercise 28. Copy the files main18c.cpp and deleteIthNode.cpp to your account. Modify the file deleteIthNode.cpp so that it finishes the implementation of the method deleteIthNode. This method deletes the i^th item from a list of items. When you compile, you will need to include this file on the compile line as well as inlab18.cpp.
The compile line should be:

c++ inlab18.cpp deleteIthNode.cpp main18c.cpp

Create a script log, lab18ex30.log containing a print out (pr -n -t -e4 ...) of deleteIthNode.cpp , a compile, and four runs with the $CLA data files Ex30_data.0, Ex30_data.1, Ex30_data.2, Ex30_data.3. Use file redirection to read from each file.

Exercise 31: (Multiple Choice) Suppose we have a linked list of integers. Each node in the list is of type Node and contains an integer and a pointer to the next item in the list. The variable first points to the first node in the list. Which of the code segments below will add a new node containing the value 55 to the beginning of the list?


A.  first = new Node;
    first->value = 55;
    first->next = first;
B.  Node* temp = new Node;
    first->value = 55;
    temp->next = first;
C.  Node* temp = new Node;
    temp->value = 55;
    temp->next = first->next;
    first = temp;
D.  Node* temp = new Node;
    temp->value = 55;
    temp->next = first;
    first = temp;

Exercise 32: (Multiple Choice) Suppose we have a linked list of integers. Each node in the list is of type Node and contains an integer and a pointer to the next item in the list. The variable first points to the first node in the list. Which of the code segments below will properly delete the last node in the list?

A.  Node* cur=first;
    while(cur != NULL)
    {
        cur = cur->next;
    }
    delete cur;
    cur = NULL;
B.  Node* cur = first;
    while(cur->next != NULL)
    {
        cur = cur->next;
    }
    delete cur->next;
    cur->next = NULL;
C.  Node* cur = first->next;
    while (cur != NULL)
    {
        cur = cur->next;
    }
    delete cur;
    cur = NULL;
D.  None of the above.

You have reached the end of Lab 18!!

(Optional: Want to explore this topic further? For example, how do you use linked lists in languages, like BASIC and Fortran, that don't support pointers? The answer is to use Simulated Pointers (aka cursors) - follow link to learn more.

----- End of Lab 18 - Pointers and Linked Lists -----

Complete the Exercises on the Answer Sheet.

Submit the final Lab 18 Answer Sheet (AnswerSheet18.pdf) using the GUS web site with AssignmentID lab18ans.

Submit the required log files by using the command

$ handin lab18log lab18ex28.log lab18ex29.log lab18ex30.log

Return to the top of this lab
Return to the link page for all 2170 labs

ADDRESS	MEMORY CONTENTS	VARIABLE ALLOCATIONS
1000	?	pNum1
1004	?	pNum2
1008	?	num

ADDRESS	MEMORY CONTENTS	VARIABLE ALLOCATIONS
1000	2644	pNum1
1004	2400	pNum2
1008	?	num
.
2400	?
.
2644	?

ADDRESS	MEMORY CONTENTS	VARIABLE ALLOCATIONS
1000	2644	pNum1
1004	2400	pNum2
1008	?	num
.
2400	20
.
2644	31

ADDRESS	MEMORY CONTENTS	VARIABLE ALLOCATIONS
796	2160	bankPtr
.
2160	?	(Memory for one structure starting at 2160)

LAB 18
Memory, Pointers, and Linked Lists

A. The List ADT

C++ terminology review

B. Memory Allocation

Storage Classes

C. C++ Pointers

D. Linked Lists

E. Linked List Operations

Examining each node in the list

F. The C++ Class Destructor

----- End of Lab 18 - Pointers and Linked Lists -----

LAB 18Memory, Pointers, and Linked Lists

A. The List ADT

C++ terminology review

B. Memory Allocation

Storage Classes

C. C++ Pointers

D. Linked Lists

E. Linked List Operations

Examining each node in the list

F. The C++ Class Destructor

----- End of Lab 18 - Pointers and Linked Lists -----

LAB 18
Memory, Pointers, and Linked Lists