Data Structures through C++ : Video Lecture 4 and 5

Department: MCA
Semester    : II

Subject       : Data Structures through C++

Paper          : CCMCA 203

Faculty       : Avinash Kumar

Data Structures Session 4 Linked List Insertion part 1

Data Structures Session 4 Linked List Insertion part 2

Data Structures: Video Lecture 3

Department: MCA
Semester    : II

Subject       : Data Structures through C++

Paper          : CCMCA 203

Faculty       : Avinash Kumar


Introduction to Linked Lists

Linked Lists : Lecture 5

Department: MCA
Semester    : II

Subject       : Data Structures through C++

Paper          : CCMCA 203

Faculty       : Avinash Kumar

Syllabus covered in  this blog

Linked Lists (Singly, Doubly & Circular)

Linked List

A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers as shown in the below image:

In simple words, a linked list consists of nodes where each node contains a data field and a reference (link) to the next node in the list.

Linked List and Array

Both Arrays and Linked List can be used to store linear data of similar types, but they both have some advantages and disadvantages over each other.

Key Differences between Array and Linked List

• An array is a data structure that contains a collection of similar type data elements whereas the Linked list is considered as non-primitive data structure contains a collection of unordered linked elements known as nodes.
• In array the elements belong to indexes, i.e., if you want to get into the fourth element you have to write the variable name with its index or location.
• In a linked list though, you have to start from the head and work your way through until you get to the desired element.
• Accessing an element in an array is fast, while Linked list takes linear time, so it is quite slower.
• Operations like insertion and deletion in arrays consume a lot of time. On the other hand, the performance of these operations in Linked lists is fast.
• Arrays are of fixed size. In contrast, Linked lists are dynamic and flexible and can expand and contract its size.
• In an array, memory is assigned during compile time while in a Linked list it is allocated during execution or runtime.
• Elements are stored consecutively in arrays whereas it is stored randomly in Linked lists.
• In addition memory utilization is inefficient in the array. Conversely, memory utilization is efficient in the linked list.
• Linked list provides the following two advantages over arrays
• Dynamic size
• Ease of insertion/deletion
• Linked lists have following drawbacks:
• Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do a binary search with linked lists.
• Extra memory space for a pointer is required with each element of the list.

Types of Linked List

• Singly Linked List.
• Doubly Linked List.
• Circular Linked List. 

Singly Linked List

A Singly-linked list is a collection of nodes linked together in a sequential way where each node of the singly linked list contains a data field and an address field that contains the reference of the next node.

The structure of the node in the Singly Linked List is:

class Node

{

            int Data;

            Node * Next;

};

The nodes are connected to each other in this form where the value of the next variable of the last node is NULL i.e. next = NULL, which indicates the end of the linked list.

Doubly Linked List

A Doubly Linked List contains an extra memory to store the address of the previous node, together with the address of the next node and data which are there in the singly linked list. So, here we are storing the address of the next as well as the previous nodes.

The following is the structure of the node in the Doubly Linked List(DLL):

class Node

{

            int Data;

            Node * Next;

 Node * Prev;

};

The nodes are connected to each other in this form where the first node has

 prev = NULL and the last node has next = NULL

Advantages over Singly Linked List

• It can be traversed both forward and backward direction.
• The delete operation is more efficient if the node to be deleted is given.
• The insert operation is more efficient if the node is given before which insertion should take place.

Disadvantages over Singly Linked List

• It will require more space as each node has an extra memory to store the address of the previous node.
• The number of modification increase while doing various operations like insertion, deletion, etc.

Circular Linked List

A circular linked list is either a singly or doubly linked list in which there are no NULL values. We can implement the Circular Linked List by making the use of Singly or Doubly Linked List.

In the case of a singly linked list, the next of the last node contains the address of the first node and in case of a doubly-linked list, the next of last node contains the address of the first node and prev of the first node contains the address of the last node.

Advantages of a Circular linked list

• The list can be traversed from any node.
• Circular lists are the required data structure when we want a list to be accessed in a circle or loop.
• We can easily traverse to its previous node in a circular linked list, which is not possible in a singly linked list.

Disadvantages of Circular linked list

• If not traversed carefully, then we could end up in an infinite loop because here we don't have any NULL value to stop the traversal.
• Operations in a circular linked list are complex as compared to a singly linked list and doubly linked list like reversing a circular linked list, etc. 

Basic Operations on Linked List

• Traversal: To traverse all the nodes one after another.
• Insertion: To add a node at the given position.
• Deletion: To delete a node.
• Searching: To search an element(s) by value.
• Updating: To update a node.

Linked List Traversal

The idea here is to step through the list from beginning to end. For example, we may want to print the list or search for a specific node in the list.

The algorithm for traversing a list

• Start with the head of the list. Access the content of the head node if it is not null.
• Then go to the next node(if exists) and access the node information
• Continue until no more nodes (that is, you have reached the null node)

void traverseLL(Node *head)

{

    while(head != NULL)

    {

        cout<<head->data;

        head = head->next;

    }

}

Linked List node Insertion

• There can be three cases that will occur when we are inserting a node in a linked list.
• Insertion at the beginning
• Insertion at the end. (Append)
• Insertion after a given node

Insertion at the beginning

If the list is empty, we make the new node as the head of the list. Otherwise, we have to connect the new node to the current head of the list and make the new node, the head of the list.

Node insertAtBegin(Node *head, int val)

{

    newNode = new Node(val);

    if(head == NULL)

        return newNode;

    else

    {

        newNode->next = head;

        return newNode;

    }

}

Insertion at end

• We will traverse the list until we find the last node.
• Then we insert the new node to the end of the list.
• Note that we have to consider special cases such as list being empty.

In case of a list being empty, we will return the updated head of the linked list because in this case, the inserted node is the first as well as the last node of the linked list.

Node insertAtEnd(Node *head, int val)

{

    if( head == NULL )

    {

        newNode = new Node(val);

        head = newNode;

        return head;

    }

    Node *temp = head;

    while( temp->next != NULL )

    {

        temp = temp->next;

    }

    newNode = new Node(val);

    temp->next = newNode;

    return head;

}

Insertion after a given node

We are given the reference to a node, and the new node is inserted after the given node.

void insertAfter(Node *prevNode, int val)

{

    newNode = new Node(val);

   

    newNode->next = prevNode->next;

    prevNode->next = newNode;

}

Linked List node Deletion

To delete a node from a linked list, we need to do these steps:

• Find the previous node of the node to be deleted.
• Change the next pointer of the previous node
• Free the memory of the deleted node.

In the deletion, there is a special case in which the first node is deleted. In this, we need to update the head of the linked list.

Node deleteLL(Node *head, Node *del)

{

    if(head == del)

    {

        return head->next;

    }

    Node *temp = head;

   

    while( temp->next != NULL )

    {

        if(temp->next == del)

        {

            temp->next = temp->next->next;

            delete del;

        }

        temp = temp->next;

    }

    return head;

}

Linked List node Searching

To search any value in the linked list, we can traverse the linked list and compares the value present in the node.

bool searchLL(Node *head, int val)

{

    Node *temp = head;

    while( temp != NULL)

    {

        if( temp->data == val )

            return true;

        temp = temp->next;

    }

    return false;

}

Evolutionary Models : Lecture 6

Department : MCA

Semester     : IV

Subject        : Principles of Software Engineering                                             

Paper           : 21

Faculty        : Avinash Kumar

Syllabus covered in  this blog

Evolutionary Models (Prototype & Spiral model)

Evolutionary Model

Evolutionary model is additionally spoken because of the successive versions model and sometimes because of the incremental model. In Evolutionary model, the software requirement is first counteracted into several modules (or functional units) which will be incrementally constructed and delivered.

The developer initially develops the core modules of the system. The core modules are people who don't need services from the opposite modules. The initial product sketch is upgraded into increasing levels of functional capability by adding new features in successive versions. Every evolutionary model can be developed by using the iterative model of development.

Each successive version of the product is fully functional software more capable than the previous versions.

This model is normally useful for huge products, where it is easier to find modules for incremental implementation.

Advantages of Evolutionary Model

• Evolutionary model is normally useful for very large products.
• User gets a chance to experiment with partially developed software much before the complete version of the system is released.
• Evolutionary model helps to accurately elicit user requirements during the delivery of different versions of the software.
• The core modules get tested thoroughly, thereby reducing the chances of errors in the core modules of the final products.
• Evolutionary model avoids the need to commit large resources in one go for development of the system.

Disadvantages of Evolutionary Model

• The delivery of full software can be late due to different changes by customers during development.
• It is difficult to divide the problem into several parts, that would be acceptable to the customer which can be incrementally implemented and delivered.

Types of Evolutionary Model 

• Prototype Model
• Spiral Model

 

 Prototype Model

 

A prototype is a simulation of the actual product or system. A prototype model usually exhibits limited functional capabilities, low reliability, and less efficient performance as compared to the actual software.

A prototype model is usually built using several shortcuts. The shortcuts might involve using inaccurate, inefficient or dummy functions. A prototype usually turns out to be a very crude version of the actual system.

In this model, prototyping starts with initial requirements gathering phase. Quick design is carried out and a prototype is built. The developed prototype is submitted to the customer for his assessment.

Based on the customer feedback, the requirements are refined and the prototype is suitably modified. This cycle of obtaining customer feedback and modifying the prototype continues until the customer approves the prototype.

Once the customer approves the prototype, the actual system is developed using the iterative waterfall approach.

Need for a Prototype Model in Software Development

• To illustrate the input data formats, messages, reports, and interactive dialogues to the customer.
• To gain a better understanding of the customer’s needs
• To examine the technical issues associated with product development.
• It is not possible to get the perfect product in the first attempt.
• If we want to develop a good product we must plan to throw away the first version.
• The experience acquired in developing the prototype can be used to develop the final product.

Advantages of Prototype Model

• Demo working model: Customer get demo working model of actual product which help them to give a better understanding and attain a high level of satisfaction.
• New requirement: Based on the customer feedback, the requirements are redefined and the prototype is suitably modified till final approval.
• Missing functionality: can be easily established.
• Easy error detection: It saves time and cost in developing the prototype and enhances the quality of the final product.
• Flexibility: in the development phase.

Disadvantages of Prototype Model

• Time-consuming: As the prototype is being modified time to time according to customer requirement which usually increases the time of completion of the product.
• Complexity: Change in the requirement usually expands the scope of the product beyond its original plan and thus increase the complexity.
• Poor Documentation: Continuous changing of requirement can lead to poor documentation.
• Unpredictability of no of iteration: It is difficult to determine the no of iteration required before the prototype is finally accepted by the customer.
• Confusion: Customer can confuse between the actual product and prototype.

Spiral Model

 

The spiral model is a software process model that couples the iterative nature of prototyping with the controlled and systematic aspects of the linear sequential model. The spiral model is also known as meta-model since it encompasses all other life cycle models.

It is one of the most important Software Development Life Cycle models, which provides support for Risk Handling. In its diagrammatic representation, it looks like a spiral with many loops. The exact number of loops of the spiral is unknown and can vary from project to project. Each loop of the spiral is called a Phase of the software development process. 

The exact number of phases needed to develop the product can be varied by the project manager depending upon the project risks. As the project manager dynamically determines the number of phases, so the project manager has an important role to develop a product using spiral model.

The Radius of the spiral at any point represents the expenses (cost) of the project so far, and the angular dimension represents the progress made so far in the current phase.

The diagram below shows different phases of the Spiral Model:

Each phase of Spiral Model is divided into four quadrants as shown in the above figure. The functions of these four quadrants are discussed below-

1. Objectives determination and identify alternative solutions: Requirements are gathered from the customers and the objectives are identified, elaborated and analyzed at the start of every phase. Then alternative solutions possible for the phase are proposed in this quadrant.
2. Identify and resolve Risks: During the second quadrant all the possible solutions are evaluated to select the best possible solution. Then the risks associated with that solution is identified and the risks are resolved using the best possible strategy. At the end of this quadrant, Prototype is built for the best possible solution.
3. Develop next version of the Product: During the third quadrant, the identified features are developed and verified through testing. At the end of the third quadrant, the next version of the software is available.
4. Review and plan for the next Phase: In the fourth quadrant, the Customers evaluate the so far developed version of the software. In the end, planning for the next phase is started.

Risk Handling in Spiral Model

A risk is any adverse situation that might affect the successful completion of a software project. The most important feature of the spiral model is handling these unknown risks after the project has started. Such risk resolutions are easier done by developing a prototype. The spiral model supports coping up with risks by providing the scope to build a prototype at every phase of the software development.

Prototyping Model also support risk handling, but the risks must be identified completely before the start of the development work of the project. But in real life project risk may occur after the development work starts, in that case, we cannot use Prototyping Model. In each phase of the Spiral Model, the features of the product dated and analyzed and the risks at that point of time are identified and are resolved through prototyping. Thus, this model is much more flexible compared to other SDLC models.

Why Spiral Model is called Meta Model?

The Spiral model is called as a Meta Model because it subsumes all the other SDLC models. For example, a single loop spiral actually represents the Iterative Waterfall Model. The spiral model incorporates the step-wise approach of the Classical Waterfall Model.It  uses the approach of Prototyping Model by building a prototype at the start of each phase as a risk handling technique.

Also, the spiral model can be considered as supporting the evolutionary model – the iterations along the spiral can be considered as evolutionary levels through which the complete system is built.

Advantages of Spiral Model

• Risk Handling: Spiral Model is the best model to follow for development due to the risk analysis and risk handling at every phase.
• Good for large projects: It is recommended to use the Spiral Model in large and complex projects.
• Flexibility in Requirements: Change requests in the Requirements at later phase can be incorporated accurately by using this model.
• Customer Satisfaction: Customer can see the development of the product at the early phase of the software development and thus, they habituated with the system by using it before completion of the total product.

 Disadvantages of Spiral Model

• Complex: The Spiral Model is much more complex than other SDLC models.
• Expensive: Spiral Model is not suitable for small projects as it is expensive.
• Too much dependable on Risk Analysis: The successful completion of the project is very much dependent on Risk Analysis. Without highly experienced expertise, it is not possible to develop a project using this model.
• Difficulty in time management: As the number of phases is unknown at the start of the project, so time estimation is very difficult.