CMPT 135语言代写、代做C++编程、c/c++程序调试

日期：2021-04-06 11:25

CMPT 135 - FIC 202101– Assignment 2 Supplementary Material– Dr. Yonas T. Weldeselassie (Ph.D.) Page 1

CMPT 135 –FIC 202101 - Assignment 2

Supplementary Material: Linked List Data Structure

Instructor: Dr. Yonas T. Weldeselassie (Ph.D.)

In this supplementary material, we will describe the linked list data structure and discuss the typical

operations that we can perform on linked lists.

Linked List Data Structure

Definition: A linked list data structure is a container whose size can expand (by inserting new objects into

the container) or shrink (by removing objects from the container) and that stores its objects in sequence such

that each object knows the object in the container that comes after it. Fig 1 below shows a linked list with four

objects.

Fig 1. Linked List Data Structure

Terminologies

? Each object in a linked list is called a node. Thus the linked list in fig 1 above has four nodes.

? A node has two parts: a data part where we store data and a pointer part which points to the next

node in the linked list.

? The last node in the linked list points to a special pointer value that indicates the end of the linked list.

A convenient value that we can easily use will be the nullptr value.

? A linked list also requires a pointer that points to the first node in the linked list. This pointer is usually

referred to as the head of the linked list.

? A linked list with no nodes is known as an empty linked list. Thus a linked list is empty if its head

pointer has a nullptr value.

Representing a Node of a linked list

Since a node is an object, we may use either a C++ struct or a C++ class to represent it. A node will have two

member variables; namely a data member variable (where we will store some data of our choice) and a

pointer member variable of type node pointer (where we will store the memory address of the next node in

the linked list). The data member variable can be any data type depending on what kind of information we are

interested to store in our linked list.

The following class demonstrates a C++ class named Node that represents a node of a linked list whose data

member variable is an integer data type and whose pointer member variable is a Node* data type.

Observe that it is a good programming habit to have typedef names whenever we work with pointers so that

to minimize coding and debugging time. Thus since we will be working quite a lot with Node*, it is a good idea

to have a typedef name for it. We see that we can specify a typedef name inside a class right at the beginning

in order to use the typedef inside the class block but not outside the class block. We will then need to specify

the typedef name again outside the class in order to use it in the remaining part of our program. The best

place to specify the typedef again is right after the class declaration but before the class definition as shown

below. We also provide a test program to demonstrate how to use the Node class in our applications.

head nullptr

Data Data Data Data

CMPT 135 - FIC 202101– Assignment 2 Supplementary Material– Dr. Yonas T. Weldeselassie (Ph.D.) Page 2

#include<iostream>

using namespace std;

class Node

{

typedef Node* NodePtr;

private:

int data;

NodePtr link;

public:

Node();

Node(const int &);

Node(const Node &);//Deep copy of the node but not any other node linked to it

int getData() const;

NodePtr getLink() const;

void setData(const int &);

void setLink(const NodePtr &);

friend ostream& operator << (ostream &, const Node &);

};

typedef Node* NodePtr;

Node::Node() : data(0), link(nullptr) {}

Node::Node(const Node &n) : data(n.data), link(nullptr) {}

Node::Node(const int &d) : data(d), link(nullptr) {}

int Node::getData() const { return data; }

NodePtr Node::getLink() const { return link; }

void Node::setData(const int &d) { data = d; }

void Node::setLink(const NodePtr &p) { link = p; }

ostream& operator << (ostream &out, const Node &n)

{

out << n.data;

return out;

}

int main()

{

//Create three nodes and print them

Node n1; //n1 data is 0 and n1 link is nullptr

Node n2(5); //n2 data is 5 and n2 link is nullptr

Node n3(n2); //n3 data is 5 and n3 link is nullptr

cout << "Node 1 is "<< n1 << endl;

cout << "Node 2 is "<< n2 << endl;

cout << "Node 3 is "<< n3 << endl;

system("Pause");

return 0;

}

Representing a linked list

In order to represent a linked list, all we need is the head pointer of the linked list. Then the head pointer will

have information where to find the first node in the linked list. Why? Because it will be assigned the memory

address of the first node in the linked list and therefore will be pointing to the first node in the linked list.

Similarly the first node will know where to find the second node. Why? Because the link pointer of the first

node will be assigned the memory address of the second node and thus it will be pointing to it. Similarly, the

second node also will know where to find the third node, the third node will know where to find the fourth

node, and so on so forth. Thus given the Node class shown above, the following program demonstrates the

CMPT 135 - FIC 202101– Assignment 2 Supplementary Material– Dr. Yonas T. Weldeselassie (Ph.D.) Page 3

creation of a linked list and traversal of the linked list in order to print the nodes in the order they are

arranged in the linked list.

int main()

{

//Create three nodes

Node n1; //n1 data is 0 and n1 link is nullptr

Node n2(5); //n2 data is 5 and n2 link is nullptr

Node n3(n2); //n3 data is 5 and n3 link is nullptr

//Create a linked list with the sequence head-->n1-->n2-->n3-->nullptr

NodePtr head = &n1; //head is pointing to n1 node

n1.setLink(&n2); //n1 link is pointing to n2 node

n2.setLink(&n3); //n2 link is pointing to n3 node

//Traverse the linked list to print the nodes in the linked list

cout <<"Printing the linked list" << endl;

while (head != nullptr)

{

cout << *head << " ";

head = head->getLink(); //Now head will point to the next node

}

cout << endl;

system("Pause");

return 0;

}

Observation: Observe that traversal of a linked list is possible only in the forward direction but not in the

backward direction. Neither does a linked list data structure allow random access of its nodes. If we want to

access a node, then the only way is to start from the head pointer and traverse in a forward direction until we

find the node of our interest.

Caution 1: Observe that we must always test if any node pointer (including the head pointer) is a nullptr

before we dereference the pointer or before calling the getLink() member function. Otherwise dereferencing

or calling the getLink() member function on a node pointer with a nullptr value will cause a runtime error. In

general, we should always consider the nullptr value as a special case whenever we work with node pointers.

Caution 2: Observe that after traversing through the linked list during the printing of the nodes in the

program above, at the end the value of the head pointer will become nullptr; which means it is no more

pointing to the first node in the linked list and therefore it is no more the head of the linked list. This means in

essence we have lost our linked list. Thus, if we want to perform more traversals of the linked list afterwards

then we can't because we have lost the head of the linked list. This shortcoming will be fixed in our next

example program.

Constructing linked lists: Empty linked list

A linked list is constructed starting with an empty linked list; that is where there are no nodes in it. An empty

linked list is constructed by assigning its head pointer a nullptr value. Then new nodes are inserted to the

linked list either at the beginning of the linked list, in the middle of the linked list, or at the end of the linked

list as we desire.

Moreover, typically nodes of a linked list are stored on the heap memory so that to be able to expand or

shrink the linked list at run time as we desire.

CMPT 135 - FIC 202101– Assignment 2 Supplementary Material– Dr. Yonas T. Weldeselassie (Ph.D.) Page 4

Inserting nodes in a linked list: head_insert algorithm

The easiest way to insert a new node into a linked list is to insert the new node as a first node in the linked list.

Inserting a new node as a first node is usually referred to as head_insert operation. The diagram below shows

a linked list before and after a new node (shown in red color) is inserted using head_insert algorithm.

Given linked list

The same linked list after a new node is inserted with head_insert

The following program demonstrates the creation of an empty linked list, inserting new nodes (created on the

heap memory) with head_insert algorithm, traversal of the linked list in order to print the nodes, and finally

traversal of the linked list in order to delete the nodes of the linked list from the heap memory.

int main()

{

//Create an empty linked list

NodePtr head = nullptr;

//Insert five nodes in the linked list using head_insert operation

for (int i = 0; i < 5; i++)

{

NodePtr n = new Node(i);

n->setLink(head);

head = n;

}

//Print the linked list

cout << "Printing the linked list." << endl;

NodePtr temp = head;

while (temp != nullptr)

{

cout<< *temp << endl;

temp = temp->getLink();

}

//Delete the nodes from the heap

cout << "Deleting the linked list." << endl;

while (head != nullptr)

{

temp = head;

head = head->getLink();

delete temp;

}

system("Pause");

return 0;

}

nullptr

nullptr

head

head

CMPT 135 - FIC 202101– Assignment 2 Supplementary Material– Dr. Yonas T. Weldeselassie (Ph.D.) Page 5

The output of the program will be 4 3 2 1 0. We note that when using the head_insert algorithm, the last

node that has been inserted will be printed first. This is known as last in first out (LIFO) ordering.

Some remarks about the program:

? We observe that the head pointer should never be used for traversal except when deleting the nodes.

Otherwise if we had used the head pointer for traversal (say for example for printing the nodes) then

after printing the nodes the head pointer would have had a nullptr value which means it would not

know where the first node is located in the heap memory. Moreover we wouldn't be able to re-assign

the head pointer the memory address of the first node because we don't have not stored in another

variable. This means we would have lost the first node. Then that would mean we wouldn't be able to

locate the second node either because the only way to locate the second node is by going through the

first node. It means we would also lose the third node and so on so forth. That is, we would have lost

the entire linked list.

? When deleting a linked list however, it is perfectly fine to use the head pointer for traversal because

we don't need to locate the nodes after they are deleted. Once all the nodes are deleted, we see that

the head pointer will have a nullptr value which indicates the linked list has become empty which is

correct.

Typically, we perform the head_insert, printing, and other operations of a linked list using functions. Thus the

program given above modified to use functions for its head_insert, printing, and deleting the linked list

operations would look like as follows.

void head_insert(NodePtr &head, const int &value)

{

NodePtr n = new Node(value);

n->setLink(head);

head = n;

}

void print_linkedlist(const NodePtr &head)

{

NodePtr temp = head;

while (temp != nullptr)

{

cout << *temp << " ";

temp = temp->getLink();

}

cout << endl;

}

void delete_linkedlist(NodePtr &head)

{

NodePtr temp;

while (head != nullptr)

{

temp = head;

head = head->getLink();

delete temp;

}

}

int main()

{

//Create an empty linked list

NodePtr head = nullptr;

//Insert five nodes in the linked list using head_insertalgorithm

for (int i = 0; i < 5; i++)

CMPT 135 - FIC 202101– Assignment 2 Supplementary Material– Dr. Yonas T. Weldeselassie (Ph.D.) Page 6

head_insert(head, i);

//Print the linked list

cout << "Printing the linked list." << endl;

print_linkedlist(head);

//Delete the nodes of the linked list from the heap memory

cout << "Deleting the linked list." << endl;

delete_linkedlist(head);

system("Pause");

return 0;

}

Some remarks about the functions:

? The head argument must pass by reference to the head_insert and delete_linkedlist functions because we

want to modify its value in these functions and have the modification reflected on the main program as

well. This means we will be passing a pointer by reference. The typedef name will make the syntax easier

to understand.

? However it is not necessary to pass the head argument by reference to the print_linkedlist function;

although we still do so for efficiency purposes and use const modifier to make sure the value of the head

argument is not modified in the function.

Searching for a node in a linked list: search_node algorithm

We may also be interested to search if there exists a node in a linked list that satisfies some condition. For

example, we could search for a node whose data is equal to a given value.

The search_node function given below takes the head pointer of a linked list and an integer value as its

arguments and returns a pointer to a node in the linked list whose data is equal to the integer value argument.

If there is no any node in the linked list that satisfies the condition then the function will return nullptr.

Moreover if there are two or more nodes that satisfy the condition then the function will return a pointer to

the first node it finds that satisfies the condition.

NodePtr search_node(const NodePtr &head, const int &value)

{

NodePtr temp = head;

while (temp != nullptr)

{

if (temp->getData() == value)

return temp;

else

temp = temp->getLink();

}

return nullptr;

}

int main()

{

//Create an empty linked list

NodePtr head = nullptr;

//Insert five nodes in the linked list using head_insertalgorithm

for (int i = 0; i < 5; i++)

{

CMPT 135 - FIC 202101– Assignment 2 Supplementary Material– Dr. Yonas T. Weldeselassie (Ph.D.) Page 7

head_insert(head, i);

}

//Print the linked list

cout << "Printing the linked list." << endl;

print_linkedlist(head);

int search_value = 2;

NodePtr n = search_node(head, search_value);

if (n != nullptr)

cout << "A node whose data is equal to "<< n->getData() << " is found." << endl;

else

cout << "A node whose data us equal to " << search_value << " is not found." << endl;

search_value = 8;

n = search_node(head, search_value);

if (n != nullptr)

cout << "A node whose data is equal to " << n->getData() << " is found." << endl;

else

cout << "A node whose data us equal to " << search_value << " is not found." << endl;

//Delete the linked list

cout << "Deleting the linked list." << endl;

delete_linkedlist(head);

system("Pause");

return 0;

}

Inserting nodes in a linked list: insert_after algorithm

We may also insert a new node after a specified node. For example, we may use the search_node function to

search for a specific node and then insert a new node after that specified node.

The diagram below shows a given linked list with three nodes and the same linked list after a new node

(shown in red color) has been inserted after the second node (that is between the second the third nodes).

Such insertion operation is commonly known as insert_after operation.

Given linked list

The same linked list after inserting a new node after the second node in the linked list

In order to implement the insert_after function, we first note the following subtle points about the operation

head nullptr

head nullptr

CMPT 135 - FIC 202101– Assignment 2 Supplementary Material– Dr. Yonas T. Weldeselassie (Ph.D.) Page 8

? The function takes two arguments; namely a node pointer and an integer value.

? If the node pointer argument is a nullptr value then this function should return without inserting any

new node because it doesn't make sense to insert after a nullptr.

? The new node's data will be the integer value argument and it will be inserted after the node pointed

by the node pointer argument.

? This function does not require the head pointer of the linked list.

The following program demonstrates the insert_after algorithm. Please note that it is not necessary to pass

the node pointer argument to the function by reference because we will not modify its value. Instead we are

dereferencing it and therefore even if we use parameter passing by value then it would still be fine.

void insert_after(const NodePtr &n, const int &value)

{

if (n == nullptr)

return;

else

{

NodePtr temp = new Node(value);

temp->setLink(n->getLink());

n->setLink(temp);

}

}

int main()

{

//Create an empty linked list

NodePtr head = nullptr;

//Insert five nodes in the linked list using head_insert operation

for (int i = 0; i < 5; i++)

{

head_insert(head, i);

}

//Print the linked list. This will print 4,3,2,1,0

cout << "Printing the linked list." << endl;

print_linkedlist(head);

//Insert a new node with data equal to -4 after the node whose data is equal to 2

int search_value = 2;

NodePtr n = search_node(head, search_value);

insert_after(n, -4);

//Print the linked list. This will print 4,3,2,-4,1,0

cout << "Printing the linked list." << endl;

print_linkedlist(head);

//Insert a new node with data equal to -6 after the node whose data is equal to 8

search_value = 8;

n = search_node(head, search_value);

insert_after(n, -6); //This will not insert because n will be nullptr

//Print the linked list. This will still print 4,3,2,-4,1,0

cout << "Printing the linked list." << endl;

print_linkedlist(head);

//Delete the nodes from the heap

cout << "Deleting the linked list." << endl;

delete_linkedlist(head);

CMPT 135 - FIC 202101– Assignment 2 Supplementary Material– Dr. Yonas T. Weldeselassie (Ph.D.) Page 9

Inserting nodes in a linked list: tail_insert algorithm

We may also be interested to insert a new node as a last node in a given linked list. Then we will have two

cases to consider:

? If the linked list is empty then this function will insert the new node as the first node of the linked list

(which will also be the last node in the linked). Thus the insertion will be performed using the

head_insert function.

? Otherwise we will first find the last node of the linked list and then we will insert after the last node

using the insert_after function.

The following program demonstrates the tail_insert algorithm.

void tail_insert(NodePtr &head, const int &value)

{

if (head == nullptr)

head_insert(head, value);

else

{

//Find the last node in the linked list

NodePtr b = head; //Here b is guaranteed to be not nullptr

while (b->getLink() != nullptr)

b = b->getLink();

//Now insert after b

insert_after(b, value);

}

}

int main()

{

srand(time(0));

//Create an empty linked list

NodePtr head = nullptr;

//Insert ten random integers using insert_increasing function

for (int i = 0; i < 5; i++)

tail_insert(head, i);

//Print the linked list. This will still print 0,1,2,3,4

cout << "Printing the linked list." << endl;

print_linkedlist(head);

//Delete the nodes from the heap

cout << "Deleting the linked list." << endl;

delete_linkedlist(head);

system("Pause");

return 0;

}

The output of the program will be 0 1 2 3 4.

system("Pause");

return 0;

}

CMPT 135 - FIC 202101– Assignment 2 Supplementary Material– Dr. Yonas T. Weldeselassie (Ph.D.) Page 10

Removig a specified node from a linked list: remove_node algorithm

We may also remove a specified node from a linked list. The following diagram shows a given linked list and

the same linked list after the second node (crossed in red color) is removed.

Given linked list

The same linked list after the second node has been removed from the linked list

We observe that in order to remove a node from a linked list, we first need to find the node that is just before

it in the linked list. The following program demonstrates the remove_node algorithm. The function will take

the head of a linked list and a node pointer pointing the node to be removed as arguments and it will remove

the node pointed by the node pointer from the linked list. Of course this function will not remove a node if

any of the following conditions is true

? The head of the linked list argument is nullptr (that is the linked list is empty), or

? The node pointer argument is nullptr, or

? The node pointer is not found in the linked list.

Moreover the function must pass the head pointer argument by reference because we need to modify the

head pointer if the node to be removed happens to be the first node.

void remove_node(NodePtr &head, const NodePtr &n)

{

if (head == nullptr || n == nullptr)//empty linked list or nullptr n

return;

else if (head == n)

{

head = head->getLink();

delete n;

return;

}

else

{

NodePtr b = head;

while (b != nullptr)

{

if (b->getLink() == n) //found the node before n

{

b->setLink(n->getLink());

delete n;

return;

}

b = b->getLink();

}

}

}

CMPT 135 - FIC 202101– Assignment 2 Supplementary Material– Dr. Yonas T. Weldeselassie (Ph.D.) Page 11

int main()

{

//Create an empty linked list

NodePtr head = nullptr;

//Insert five nodes in the linked list using head_insert operation

for (int i = 0; i < 5; i++)

{

head_insert(head, i);

}

//Print the linked list. This will print 4,3,2,1,0

cout << "Printing the linked list." << endl;

print_linkedlist(head);

//Remove the node in the linked list whose data is 2

int search_value = 2;

NodePtr n = search_node(head, search_value);

remove_node(head, n);

//Print the linked list. This will print 4,3,1,0

cout << "Printing the linked list." << endl;

print_linkedlist(head);

//Remove the node in the linked list whose data is 6

search_value = 6;

n = search_node(head, search_value);

remove_node(head, n);

//Print the linked list. This will still print 4,3,1,0

cout << "Printing the linked list." << endl;

print_linkedlist(head);

//Delete the nodes from the heap

cout << "Deleting the linked list." << endl;

delete_linkedlist(head);

system("Pause");

return 0;

}

We may also be interested to remove a node whose data is equal to a specified integer value. This can easily

be done by calling the search_node function in order to first find a node pointer pointing to the node to be

removed as follows.

void remove_node(NodePtr &head, const int &value)

{

NodePtr n = search_node(head, value);

remove_node(head, n);

}

Removig all nodes satisfying a condition from a linked list: remove_all

We may also be interested to remove all nodes from a linked list whose data is equal to some specified integer

value. This can easily be done using a loop and the search_node and remove_node functions as follows.

CMPT 135 - FIC 202101– Assignment 2 Supplementary Material– Dr. Yonas T. Weldeselassie (Ph.D.) Page 12

void remove_all(NodePtr &head, const int &value)

{

NodePtr n;

while (true)

{

n = search_node(head, value);

if (n == nullptr)

break;

remove_node(head, n);

}

}

int main()

{

//Create an empty linked list

NodePtr head = nullptr;

//Insert ten nodes in the linked list using head_insert operation

for (int i = 0; i < 10; i++)

{

head_insert(head, i/3);

}

//Print the linked list. This will print 3,2,2,2,1,1,1,0,0,0

cout << "Printing the linked list." << endl;

print_linkedlist(head);

//Remove all the nodes whose data is 2

remove_all(head, 2);

//Print the linked list. This will print 3,1,1,1,0,0,0

cout << "Printing the linked list." << endl;

print_linkedlist(head);

//Delete the nodes from the heap

cout << "Deleting the linked list." << endl;

delete_linkedlist(head);

system("Pause");

return 0;

}

Inserting nodes in a linked list: insert_before algorithm

We may also insert a new node before a specified node in a linked list. In this case, we first need to find the

node just before the specified node and then use insert_after function.

In order to mimic the insert member function in STL containers, we will design this function with the following

constraints

? If the linked list is empty and the specified node is nullptr then this function should do head_insert.

? If the linked list is empty and the specified node is not nullptr then the specified node cannot be

found in the linked list and therefore an error message should be printed and this function should

not insert any new node.

? If the linked list is not empty and the specified node is nullptr then this function should do

tail_insert.

? If the linked list is not empty and the first node in the linked list is equal to the specified node then

this function should do head_insert.

CMPT 135 - FIC 202101– Assignment 2 Supplementary Material– Dr. Yonas T. Weldeselassie (Ph.D.) Page 13

? If the linked list is not empty and the specified node is not nullptr but that it is not found in the

linked list then an error message should be printed and this function should not insert any new

node.

? Otherwise a node just before the specified node will be found and this function should insert after

it using the insert_after function.

The following program demonstrates the insert_before function with a test main program designed to test all

the above six different cases.

void insert_before(NodePtr &head, const NodePtr &n, const int &value)

{

//If the linked list is empty then insert only if n is nullptr too

if (head == nullptr)

{

if (n == nullptr)

head_insert(head, value);

else

cout << "Insertion failed. Bad node argument." << endl;

}

//If n is nullptr then tail_insert

else if (n == nullptr)

tail_insert(head, value);

//If head is equal to n then head_insert

else if (head == n)

head_insert(head, value);

//Find the node just before n and insert after it

else

{

NodePtr b = head;

while (b != nullptr)

{

if (b->getLink() == n)

break;

b = b->getLink();

}

if (b == nullptr)

cout << "Insertion failed. Bad node argument." << endl;

else

insert_after(b, value);

}

}

int main()

{

srand(time(0));

//Create an empty linked list

NodePtr head = nullptr;

NodePtr n = new Node(-3);

//Insert a node with data 0 before a non-existing node. This does nothing

insert_before(head, n, 0);

cout << "Printing the linked list." << endl;

print_linkedlist(head);//Prints empty linked list

//Insert a node with data 6 before nullptr. This does head_insert

insert_before(head, nullptr, 6);

cout << "Printing the linked list." << endl;

print_linkedlist(head); //Prints 6

CMPT 135 - FIC 202101– Assignment 2 Supplementary Material– Dr. Yonas T. Weldeselassie (Ph.D.) Page 14

//Insert a node with data 3 before nullptr. This does tail_insert

insert_before(head, nullptr, 3);

cout << "Printing the linked list." << endl;

print_linkedlist(head); //Prints 6, 3

//Insert a node with data 8 before 6. This does head_insert

insert_before(head, search_node(head, 6), 8);

cout << "Printing the linked list." << endl;

print_linkedlist(head); //Prints 8, 6, 3

//Insert a node with data 5 before 6. This inserts successfully

insert_before(head, search_node(head, 6), 5);

cout << "Printing the linked list." << endl;

print_linkedlist(head); //Prints 8, 5, 6, 3

//Insert a node with data 2 before a non-existing node. This does nothing

insert_before(head, n, 2);

cout << "Printing the linked list." << endl;

print_linkedlist(head); //Prints Prints 8, 5, 6, 3

//Delete the nodes from the heap

cout << "Deleting the linked list." << endl;

delete_linkedlist(head);

system("Pause");

return 0;

}

Inserting nodes in a linked list: insert_increasing algorithm

Given a linked list whose nodes are sorted in increasing order of their data, we would like to insert a new node

into the linked list at an appropriate position so that after the insertion operation is performed all the nodes

will still be sorted in increasing order of their data.

Please note that if the linked list is empty then this function must insert the new node as the first node in the

linked list.

We can easily implement this function by first finding the correct position and then inserting with the help of

the insert_before function.

Inserting nodes in a linked list: insert_grouped algorithm

Given a linked list whose nodes are grouped in such a way that all the nodes whose data are even numbers are

grouped together and all the remaining nodes whose data are odd numbers are grouped together, we would

like to insert a new node into the linked list at an appropriate position so that after the insertion operation is

performed all the nodes will still be grouped according to even/odd data values groups.

Please note that if the linked list is empty then this function must insert the new node as the first node in the

linked list.

We can easily implement this function by first finding the correct position and then inserting with the help of

the insert_before function.

CMPT 135 - FIC 202101– Assignment 2 Supplementary Material– Dr. Yonas T. Weldeselassie (Ph.D.) Page 15

Inserting nodes in a linked list: insert_grouped_sorted algorithm

Given a linked list whose nodes are grouped in even/odd groups and sorted in increasing order of their data,

we would like to insert a new node into the linked list at an appropriate position so that after the insertion

operation is performed all the nodes will still be grouped and sorted.

Please note that if the linked list is empty then this function must insert the new node as the first node in the

linked list.

We can easily implement this function by first finding the correct position and then inserting with the help of

the insert_before function.

Representing Linked Lists with C++ class

We may also design a C++ class in order to represent a linked list. From our discussion above, we observe that

a linked list class requires only one member variable which is the head pointer and then we could implement

all the functions discussed above as member functions.

Below isa linked list class declaration and a test program. The implementations of the member functions are

almost identical to the non member functions we discussed above. The only difference is that the head

pointer parameter of the non member functions above is removed from these member functions because the

head pointer is a member variable of the class and therefore each of these member functions has access to it

and doesn't need it as a parameter.

class LinkedList

{

private:

NodePtr head;

public:

LinkedList();//Assign the head pointer a nullptr value

LinkedList(const LinkedList &);//Deep copy of the linked list with its own new nodes

~LinkedList();//Destruct all the nodes and their data

LinkedList& operator = (const LinkedList &);//Deep copy assignment of the linked list

void head_insert(const int &);

NodePtr search_node(const int &) const;

void insert_after(const NodePtr &, const int &) const;

void remove_node(const NodePtr &);

void remove_node(const int &);

void remove_all(const int &);

void tail_insert(const int &);

void insert_before(const NodePtr &, const int &);

void insert_increasing(const int &);

void insert_grouped(const int &);

void insert_grouped_increasing(const int &);

friend ostream& operator<< (ostream &, const LinkedList &);

};

int main()

{

srand(time(0));

//Create an empty linked list

LinkedList LL1;

//Insert 10 nodes in increasing order

cout << "Testing insert_increasing function...." << endl;

for (int i = 0; i < 10; i++)

{

int x = rand() % 100 - 50;

CMPT 135 - FIC 202101– Assignment 2 Supplementary Material– Dr. Yonas T. Weldeselassie (Ph.D.) Page 16

cout << "Inserting " << x << endl;

LL1.insert_increasing(x);

cout << "The linked list is now: " << LL1 << endl;

}

cout << endl << "****************************************************" << endl << endl;

//No need to delete linked list.

//Destructor will take care of it.

//Create an empty linked list

LinkedList LL2;

//Insert 10 nodes in even/odd values grouped order

cout << "Testing insert_grouped function...." << endl;

for (int i = 0; i < 10; i++)

{

int x = rand() % 100 - 50;

cout << "Inserting " << x << endl;

LL2.insert_grouped(x);

cout << "The linked list is now: " << LL2 << endl;

}

cout << endl << "****************************************************" << endl << endl;

//No need to delete linked list.

//Destructor will take care of it.

//Create an empty linked list

LinkedList LL3;

//Insert 10 nodes in grouped and within group in increasing order

cout << "Testing insert_grouped_increasing function...." << endl;

for (int i = 0; i < 10; i++)

{

int x = rand() % 100 - 50;

cout << "Inserting " << x << endl;

LL3.insert_grouped_increasing(x);

cout << "The linked list is now: " << LL3 << endl;

}

cout << endl << "****************************************************" << endl << endl;

//No need to delete linked list.

//Destructor will take care of it.

system("Pause");

return 0;

}

A sample run output of the program is shown below.

Testing insert_increasing function....

Inserting -12

The linked list is now: -12

Inserting -5

The linked list is now: -12 -5

Inserting -41

The linked list is now: -41 -12 -5

Inserting 21

The linked list is now: -41 -12 -5 21

CMPT 135 - FIC 202101– Assignment 2 Supplementary Material– Dr. Yonas T. Weldeselassie (Ph.D.) Page 17

Inserting -48

The linked list is now: -48 -41 -12 -5 21

Inserting 47

The linked list is now: -48 -41 -12 -5 21 47

Inserting -11

The linked list is now: -48 -41 -12 -11 -5 21 47

Inserting -27

The linked list is now: -48 -41 -27 -12 -11 -5 21 47

Inserting -6

The linked list is now: -48 -41 -27 -12 -11 -6 -5 21 47

Inserting -15

The linked list is now: -48 -41 -27 -15 -12 -11 -6 -5 21 47

****************************************************************

Testing insert_grouped function....

Inserting -49

The linked list is now: -49

Inserting -32

The linked list is now: -49 -32

Inserting 18

The linked list is now: -49 18 -32

Inserting 37

The linked list is now: 37 -49 18 -32

Inserting 15

The linked list is now: 15 37 -49 18 -32

Inserting -8

The linked list is now: 15 37 -49 -8 18 -32

Inserting 19

The linked list is now: 19 15 37 -49 -8 18 -32

Inserting 34

The linked list is now: 19 15 37 -49 34 -8 18 -32

Inserting 38

The linked list is now: 19 15 37 -49 38 34 -8 18 -32

Inserting 31

The linked list is now: 31 19 15 37 -49 38 34 -8 18 -32

****************************************************************

Testing insert_grouped_increasing function....

Inserting 12

The linked list is now: 12

Inserting 27

The linked list is now: 12 27

Inserting 14

The linked list is now: 12 14 27

CMPT 135 - FIC 202101– Assignment 2 Supplementary Material– Dr. Yonas T. Weldeselassie (Ph.D.) Page 18

Inserting -33

The linked list is now: 12 14 -33 27

Inserting -21

The linked list is now: 12 14 -33 -21 27

Inserting -32

The linked list is now: -32 12 14 -33 -21 27

Inserting 42

The linked list is now: -32 12 14 42 -33 -21 27

Inserting -16

The linked list is now: -32 -16 12 14 42 -33 -21 27

Inserting 3

The linked list is now: -32 -16 12 14 42 -33 -21 3 27

Inserting 27

The linked list is now: -32 -16 12 14 42 -33 -21 3 27 27

****************************************************************

Press any key to continue . . .

Practice Work

Implement the LinkedList class and get the above test program to work without any syntax, linking, runtime,

or semantic errors. You may also add more test code to the program in order to test all the other member

functions such searching for a node, removing nodes, and etc.