FIC - CMPT 135 202202 - Assignment 2 Linked List Data Structure

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

FIC - CMPT 135 202202 - Assignment 2

Supplementary Material: Linked List Data Structure

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) that stores its objects in sequence and only  allows sequential access of its elements which is achieved thanks to the fact that each object knows the object in the container that comes after it. Fig 1 below shows a linked list with four objects.

Data

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 pointer 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.

The first node in a linked list is known as the head node.

The last node in a linked list is known as the tail node.

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 main program to demonstrate how to use the Node class in our applications.

#include <iostream>

using namespace std;

class Node

{

typedef Node* NodePtr;

private:

int data;

NodePtr link;

public :

Node();//Construct ONE node whose data is 0 and link whose is nullptr

Node(const int&);//Construct ONE node whose data is given and whose link is nullptr

Node(const Node&);//Construct ONE node whose data is shallow copied and whose link is nullptr

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 int& d) : data(d), link(nullptr){}

Node::Node(const Node& n) : data(n.data), 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  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.












2022-07-09